Uprość sumę kombinacji o tym samym n, wszystkie możliwe wartości k

Czy istnieje sposób na uproszczenie tego równania?

(\binom{8}{1}) + (\binom{8}{2}) + (\binom{8}{3}) + (\binom{8}{4}) + (\binom{8}{5}) + (\binom{8}{6}) + (\binom{8}{7}) + (\binom{8}{8})

$\dbinom{8}{1} + \dbinom{8}{2} + \dbinom{8}{3} + \dbinom{8}{4} + \dbinom{8}{5} + \dbinom{8}{6} + \dbinom{8}{7} + \dbinom{8}{8}$

Lub bardziej ogólnie

\sum_{k = 1}^{n} (\binom{n}{k})

$\sum_{k=1}^{n}\dbinom{n}{k}$

combinatorics

— Idr
źródło

Lodziarnia produkuje lody bez smaku, a następnie dodaje jeden lub więcej 5 koncentratów smakowych (wanilia, czekolada, krówki, mięta, jamoca), aby stworzyć różne lody dostępne do sprzedaży w sklepie. Tak więc liczba różnych smaków to

\sum_{k = 1}^{5} (\binom{5}{k})

$\sum_{k=1}^5 \binom{5}{k}$ . Spróbuj ręcznie obliczyć liczbę smaków. Aby uzyskać dodatkowy kredyt, zidentyfikuj sklep.

— Dilip Sarwate,

Odpowiedzi:

Widzieć

http://en.wikipedia.org/wiki/Combination#Number_of_k-combinations_for_all_k

który mówi

\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}

$\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Możesz to udowodnić za pomocą twierdzenia dwumianowego, gdzie . $x=y=1$

Teraz, ponieważ dla dowolnego , wynika z tego $\binom{n}{0} = 1$ $n$

\sum_{k = 1}^{n} (\binom{n}{k}) = 2^{n} - 1

$\sum_{k=1}^{n} \binom{n}{k} = 2^n - 1$

W twoim przypadku , więc odpowiedź to . $n=8$ $2^8 - 1 = 255$

— Makro
źródło

Dzięki. Próbowałem wymyślić wszystkie możliwe zestawy cech wejściowych dla regresji, więc mój umysł zaczyna się od statystyk, ale przypuszczam, że to pytanie nie jest statystykami per se.

— Idr

Nie ma problemu. Proszę rozważyć głosowanie i / lub przyjmowanie odpowiedzi, które okazały się pomocne :)

— Makro

Oczywiście. Również uważam, że twoje ja powinno być k.

— Idr

masz rację - naprawiono.

— Makro

Łatwy sposób to zobaczyć: weźmiesz każdy element (1) lub nie (0). Możesz więc przedstawić całą liczbę binarną za pomocą n bitów: 2 ^ n. A to oznacza całą kombinację z usuniętym jednym przedmiotem plus wszystkie kombinacje z usuniętymi 2 przedmiotami itd. = Suma C (k / N).

— Snicolas,

Praca domowa?

Wskazówka:

Zapamiętaj twierdzenie dwumianowe:

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n - k}

$(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^ky^{n-k}$

Teraz, jeśli możesz po prostu znaleźć xiy, aby było stałe ... $x^ky^{n-k}$

— Erik
źródło