Liczba k-kombinacji z danego zbioru S o n elementach jest często oznaczana w tekstach z zakresu elementarnej kombinatoryki przez C ( n , k ) {displaystyle C(n,k)}
, lub przez odmianę taką jak C k n {displaystyle C_{k}^{n}}
, n C k {{displaystyle {}_{n}C_{k}}
, n C k {{displaystyle {}^{n}C_{k}}
, C n , k {displaystyle C_{n,k}}
lub nawet C n k {displaystyle C_{n}^{k}}
(ta ostatnia forma była standardem w tekstach francuskich, rumuńskich, rosyjskich, chińskich i polskich). Ta sama liczba występuje jednak w wielu innych kontekstach matematycznych, gdzie oznaczana jest przez ( n k ) {displaystyle {tbinom {n}{k}}}.
(często czytane jako „n wybiera k”); w szczególności występuje jako współczynnik we wzorze dwumianowym, stąd jej nazwa współczynnik dwumianowy. Można zdefiniować ( n k ) {{displaystyle {{tbinom {n}{k}}}
dla wszystkich liczb naturalnych k jednocześnie przez relację ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {displaystyle (1+X)^{n}}=suma _{k 0}{binom {n}{k}}X^{k}}
z czego wynika, że
( n 0 ) = ( n n ) = 1 , {displaystyle {{binom {n}{0}}={binom {n}{n}}=1,}
i dalej,
( n k ) = 0 {{displaystyle {{binom {n}{k}}=0}
dla k > n.
Aby przekonać się, że współczynniki te liczą k-kombinacji z S, można najpierw rozważyć zbiór n różnych zmiennych Xs oznaczanych przez elementy s z S i rozwinąć iloczyn po wszystkich elementach S:
∏ s ∈ S ( 1 + X s ) ; {displaystyle {prod _{s w S}(1+X_{s});}
ma on 2n różnych wyrażeń odpowiadających wszystkim podzbiorom S, z których każdy daje iloczyn odpowiednich zmiennych Xs. Teraz ustawiając wszystkie Xs równe nieoznaczonej zmiennej X, tak, że produkt staje się (1 + X)n, termin dla każdego k-kombinacji z S staje Xk, tak, że współczynnik tej potęgi w wyniku równa się liczbie takich k-kombinacji.
Współczynniki dwumianu mogą być obliczane jawnie na różne sposoby. Aby otrzymać je wszystkie dla rozwinięć do (1 + X)n, można skorzystać (oprócz podanych już podstawowych przypadków) z zależności rekurencyjnej
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) , { {{binom {n}{k}}={binom {n-1}{k-1}}+{binom {n-1}{k}},}
dla 0 < k < n, co wynika z (1 + X)n = (1 + X)n – 1(1 + X); prowadzi to do konstrukcji trójkąta Pascala.
Do wyznaczenia indywidualnego współczynnika dwumianowego praktyczniej jest skorzystać ze wzoru
( n k ) = n ( n – 1 ) ( n – 2 ) ⋯ ( n – k + 1 ) k ! {{displaystyle {{binom {n}{k}}={frac {n(n-1)(n-2)⋯ (n-k+1)}{k!}}.
.
Licznik podaje liczbę k-permutacji n, tzn, ciągów k różnych elementów S, natomiast mianownik podaje liczbę takich k-permutacji, które dają tę samą k-kombinację, gdy pominiemy kolejność.
Gdy k przekracza n/2, powyższy wzór zawiera czynniki wspólne dla licznika i mianownika, a ich anulowanie daje zależność
( n k ) = ( n n – k ) , {{{binom {n}{k}}={{binom {n}{n-k}},}
dla 0 ≤ k ≤ n. Wyraża to symetrię, która wynika ze wzoru dwumianowego i może być również zrozumiana w odniesieniu do k-kombinacji poprzez wzięcie dopełnienia takiej kombinacji, które jest (n – k)-kombinacją.
Wreszcie istnieje wzór, który wykazuje tę symetrię bezpośrednio i ma tę zaletę, że jest łatwy do zapamiętania:
( n k ) = n ! k ! ( n – k ) ! , {{binom {n}{k}}={frac {n!}{k!(n-k)!}},}
gdzie n! oznacza czynnik n. Otrzymuje się go z poprzedniego wzoru przez pomnożenie mianownika i licznika przez (n – k)!więc na pewno jest obliczeniowo mniej wydajny niż tamten wzór.
Ostatni wzór można zrozumieć bezpośrednio, rozważając n! permutacji wszystkich elementów S. Każda taka permutacja daje k-kombinację przez wybranie jej pierwszych k elementów. Istnieje wiele zduplikowanych wyborów: każda połączona permutacja pierwszych k elementów między sobą oraz końcowych (n – k) elementów między sobą daje tę samą kombinację; to wyjaśnia podział we wzorze.
Z powyższych wzorów wynikają relacje między sąsiednimi liczbami w trójkącie Pascala we wszystkich trzech kierunkach:
( n k ) = { ( n k – 1 ) n – k + 1 k, jeśli k > 0 ( n – 1 k ) n n – k, jeśli k < n ( n – 1 k – 1 ) n k, jeśli n , k > 0 {{displaystyle {{binom {n}{k}}}={begin{cases}{{binom {n}{k-1}}}{{frac {n-k+1}{k}}}&quad {{text{if }}k>0 {{binom {n-1}{k}}{}{frac {n}{n-k}}&quad {text{if }}k<n}{binom {n-1}{k-1}}{frac {n}{k}}&quad {text{if }}n,k>0\end{cases}}}
.
Wraz z podstawowymi przypadkami ( n 0 ) = 1 = ( n n ) {{displaystyle {{tbinom {n}{0}}}=1={tbinom {n}{n}}}
, pozwalają one na sukcesywne obliczanie odpowiednio wszystkich liczb kombinacji z tego samego zbioru (rzędu w trójkącie Pascala), k-kombinacji zbiorów o rosnących rozmiarach oraz kombinacji z dopełnieniem o stałym rozmiarze n – k.
Przykład liczenia kombinacjiEdit
Jako konkretny przykład, można obliczyć liczbę możliwych układów pięciokartowych ze standardowej talii pięćdziesięciu dwóch kart jako:
( 52 5 ) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311,875,200 120 = 2,598,960. {displaystyle {52 }={{frac {52 razy 51 razy 50 razy 49 razy 48}{5 razy 4 razy 3 razy 2 razy 1}}={{frac {311{,}875{,}200}{120}}=2{,}598{,}960.}
Alternatywnie można użyć wzoru na czynniki i anulować czynniki w liczniku względem części czynników w mianowniku, po czym wymagane jest tylko mnożenie pozostałych czynników:
( 52 5 ) = 52 ! 5 ! 47 ! = 52 × 51 × 50 × 49 × 48 × 47 ! 5 × 4 × 3 × 2 × 1 × 47 ! = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 = ( 26 × 2 ) × ( 17 × 3 ) × ( 10 × 5 ) × 49 × ( 12 × 4 ) 5 × 4 × 3 × 2 = 26 × 17 × 10 × 49 × 12 = 2,598,960. displaystyle {{begin{alignedat}{2}{52 \i0}&={{frac {52!}{5!47!}}} {{{frac {52}czas 51}czas 50}czas 49}czas 48}}}{5}czas 4}czas 3}czas 2}czas {{cancel {1}}}} {{cancel {47!}}}}={{frac {52}} 51}} 50}} 49}} 48}{5}}}}}}}}}}}}}}}}}}}}={{frac {(26}}}}} (17}} {{3}}}} (10}}} (10}} {{5}}} (2}}) {5}})}} 49 czasów (12 czasów {4})}}{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{}}}}}}}}}}}}}}}}}}}}}}}}}598{,}960.\end{alignedat}}
Inne alternatywne obliczenie, równoważne pierwszemu, opiera się na zapisie
( n k ) = ( n – 0 ) 1 × ( n – 1 ) 2 × ( n – 2 ) 3 × ⋯ × ( n – ( k – 1 ) k , {{displaystyle {n \u200}={{frac {(n-0)}{1}czas {{frac {(n-1)}{2}}czas {{frac {(n-2)}{3}}czas {{frac {(n-(k-1))}{k}},}
co daje
( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2,598,960 {{displaystyle {52 \i0}={{frac {52}{1}}}czasów {{frac {51}{2}}}czasów {{frac {50}{3}}}} czasów {{frac {49}{4}}} czasów {{frac {48}{5}}}=2{,}598{,}960}.
.
Po obliczeniu w następującej kolejności, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, można to obliczyć używając tylko arytmetyki całkowitej. Wynika to z faktu, że przy każdym dzieleniu otrzymany wynik pośredni jest współczynnikiem dwumianowym, więc nie występują reszty.
Użycie wzoru symetrycznego w postaci czynnikowej bez uproszczeń daje dość obszerne obliczenia:
( 52 5 ) = n ! k ! ( n – k ) ! = 52 ! 5 ! ( 52 – 5 ) ! = 52 ! 5 ! 47 ! = 80 , 658 , 175 , 170 , 943 , 878 , 571 , 660 , 636 , 856 , 403 , 766 , 975 , 289 , 505 , 440 , 883 , 277 , 824 , 000 , 000 , 000 , 000 120 × 258 , 623 , 241 , 511 , 168 , 180 , 642 , 964 , 355 , 153 , 611 , 979 , 969 , 197 , 632 , 389 , 120 , 000 , 000 , 000 = 2,598,960. Displaystyle {{begin{aligned}{52 \u005}&={frac {n!}{k!(n-k)!}}={frac {52!}{5!(52-5)!}}={frac {52!}{5!47!}}\\&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\&=2{,}598{,}960.\end{aligned}}
Enumerating k-combinationsEdit
One can enumerate all k-combinations of a given set S of n elements in some fixed order, which establishes a bijection from an interval of ( n k ) {{displaystyle {{tbinom {n}{k}}}.
liczb całkowitych do zbioru tych k-kombinacji. Zakładając, że S jest samo w sobie uporządkowane, na przykład S = { 1, 2, …, n }, istnieją dwie naturalne możliwości uporządkowania jego k-kombinacji: przez porównywanie najpierw ich najmniejszych elementów (jak na ilustracjach powyżej) lub przez porównywanie najpierw ich największych elementów. Ta druga opcja ma tę zaletę, że dodanie nowego największego elementu do S nie zmieni początkowej części wyliczenia, a jedynie doda nowe k-kombinacje większego zbioru po poprzednich. Powtarzając ten proces, wyliczenie można rozszerzać w nieskończoność o k-kombinacje coraz większych zbiorów. Jeśli ponadto przyjmiemy, że przedziały liczb całkowitych zaczynają się od 0, to k-kombinację w danym miejscu i w wyliczeniu można łatwo obliczyć z i, a tak otrzymaną bijekcję nazywamy kombinatorycznym systemem liczbowym. Jest on również znany jako „rank”/”ranking” i „unranking” w matematyce obliczeniowej.
Istnieje wiele sposobów na wyliczenie k kombinacji. Jednym ze sposobów jest odwiedzenie wszystkich liczb binarnych mniejszych niż 2n. Wybrać te liczby, które mają k niezerowych bitów, choć jest to bardzo nieefektywne nawet dla małych n (np. n = 20 wymagałoby odwiedzenia około miliona liczb, podczas gdy maksymalna liczba dozwolonych k kombinacji wynosi około 186 tysięcy dla k = 10). Położenie tych 1 bitów w takiej liczbie jest specyficzną k-kombinacją zbioru { 1, …, n }. Innym, prostszym i szybszym sposobem jest śledzenie k numerów indeksów wybranych elementów, zaczynając od {0 … k-1} (zero-based) lub {1 … k} (jednopodstawowy) jako pierwszej dozwolonej k-kombinacji, a następnie wielokrotnie przechodząc do następnej dozwolonej k-kombinacji przez inkrementację ostatniego numeru indeksu, jeśli jest on mniejszy niż n-1 (zerowy) lub n (jednopodstawowy) lub ostatni numer indeksu x, który jest mniejszy niż numer indeksu następujący po nim minus jeden, jeśli taki indeks istnieje i resetując numery indeksów po x do {x+1, x+2, …}.
.