Współczynniki dwumianowe pojawiały się przy rozwinięciu dwumianu \( (x+y)^n \). Odpowiadały one wyborom dwuwartościowym. Podobnie rozważając trójmian \( (x+y+z)^n \), czy ogólnie \( (x_1+\ldots +x_r)^n \), pojawią się współczynniki odpowiadające wyborom odpowiedni trój- i \( r \)-wartościowym. Wybieranie podzbioru \( k \)-elementowego ze zbioru \( n \)-elementowego to podział zbioru na dwie części o odpowiednio \( k \) i \( n-k \) elementach. Naturalnym uogólnieniem, będzie podział zbioru \( n \)-elementowego na \( r \) części o odpowiednio \( k_1,k_2,\ldots,k_r \) elementach, przy czym oczywiście \( k_1+\ldots k_r=n \).
Współczynnik multimianowy \( {n\choose k_1,k_2\ldots,k_{r}} \), dla \( n\in\mathbb{Z} \), \( r\geq2 \) oraz całkowitych \( k_1,\ldots,k_r \) takich, że \( k_1+\ldots k_r=n \), to liczba sposobów umieszczenia \( n \) obiektów w \( r \) pudełkach z odpowiednio \( k_1 \) obiektami w pierwszym pudełku, \( k_2 \) w drugim, itd., oraz \( k_r \) w \( r \)-tym. Jeśli którakolwiek z liczb \( k_i \) jest ujemna to współczynnik jest równy \( 0 \). Zauważmy, że z uwagi na symetrię dolnych indeksów, ich kolejność nie jest istotna. Oczywiście \( {n \choose k} \) to w nowej notacji \( {n \choose k,n-k} \).
Następna obserwacja wynika wprost z definicji współczynników multimianowych.
Obserwacja 5.18
Dla \( n\in\mathbb{Z} \), \( k,l,k_1,\ldots,k_r\in\mathbb{Z} \) takich, że \( k_1+\ldots k_r=n= k+l \) zachodzi:
Następna obserwacja wymaga krótkiego uzasadnienia.
Obserwacja 5.19
Dla \( n,k_1,\ldots,k_r\geq0 \) takich, że \( k_1+\ldots+k_r=n \)
\( {n\choose k_1,\ldots,k_r} ={n\choose k_1}{n-k_1\choose k_2}{n-(k_1+k_2)\choose k_3} \cdot\ldots\cdot{n-(k_1+\ldots+k_{r-1})\choose k_r}. \)
Dowód
Rozmieszczenie \( n \)-obiektów w \( r \) pudełkach po \( k_i \) w każdym, polega na:
i umieszczeniu ich w trzecim pudełku - możemy to uczynić na \( {n-(k_1+k_2)\choose k_3} \) sposobów,
Zatem wszystkich możliwych rozmieszczeń zgodnie z wymogami z definicji współczynnika multimianowego jest dokładnie \( {n\choose k_1}{n-k_1\choose k_2}{n-(k_1+k_2)\choose k_3} \cdot\ldots\cdot{n-(k_1+\ldots+k_{r-1})\choose k_r} \).
Wniosek 5.20
Dla \( n,k_1,\ldots,k_r\geq0 \) takich, że \( k_1+\ldots+k_r=n \)
\( {n\choose k_1,\ldots,k_r}=\frac{n!}{k_1!\cdot\ldots\cdot k_r!}. \)
Dowód
\( \begin{align*}{n\choose k_1,\ldots,k_r} & ={n\choose k_1}{n-k_1\choose k_2}{n-(k_1+k_2)\choose k_3}\cdot\ldots\cdot{n-(k_1+\ldots+k_{r-1})\choose k_r} \\ & =\frac{n!}{(n-k_1)!k_1!}\cdot\frac{(n-k_1)!}{(n-(k_1+k_2))!k_2!} \cdot\ldots\cdot\frac{(n-(k_1+\ldots+k_{r-1}))!}{(n-(k_1+\ldots+k_r))!k_r!} \\ & =\frac{n!}{k_1!\cdot\ldots\cdot k_r!\cdot(n-(k_1+\ldots+k_r))!} \\ & =\frac{n!}{k_1!\cdot\ldots\cdot k_r!}. \end{align*} \)
Przykład
Ile liczb możemy ułożyć zapisując w dowolnej kolejności \( 11 \) cyfr: \( 1,1,3,4,5,5,5,6,7,7,9 \)?
Zauważmy, że każda taka liczba powstaje przez wybór dwu pozycji dla cyfry \( 1 \), jednej dla cyfry \( 3 \), jednej dla cyfry \( 4 \), trzech dla cyfry \( 5 \), jednej dla cyfry \( 6 \), dwu dla cyfry \( 7 \) i wreszcie jednej pozycji dla cyfry \( 9 \). Zatem \( 11 \) pozycji to nasze obiekty, które rozmieszczamy w siedmiu pudełkach etykietowanych cyframi: \( 1,3,4,5,6,7,9 \). Zatem z definicji współczynnika multimianowego mamy:
\( {11\choose 2,1,1,3,1,2,1}=\frac{11!}{2!\cdot3!\cdot2!}=1663200. \)
Przykład
Rozważmy raz jeszcze podróż w mieście o ulicach na planie siatki. Tym razem jednak... \( 3 \)-wymiarową wersję. Mamy więc do dyspozycji trójwymiarową, prostopadłościenną kratownicę \( a\times b\times c \). Na ile sposobów można połączyć przeciwległe wierzchołki prostopadłoscianu najkrótszą możliwą łamaną Zauważmy, że każda najkrótsza możliwa łamana składa się z dokładnie \( a+b+c \) odcinków jednostkowych. Przy czym dokładnie \( a \) z nich jest poziomych, \( b \) pionowych i \( c \) idzie w głąb. Zatem najkrótszych łamanych jest tyle co rozmieszczeń \( a+b+c \) odcinków (obiekty) w \( 3 \) pudełkach: "poziomy", "pionowy", "w głąb" tak, by w było ich odpowiednio \( a,b \) i \( c \). Z definicji współczynnika multimianowego mamy zatem:
\( {a+b+c\choose a,b,c}=\frac{(a+b+c)!}{a!b!c!}, \)
łamanych.
Kratka z rysunku o wymiarach \( 3\times4\times2 \) ma zatem: \( {9\choose3,4,2}=\frac{9!}{3!\cdot4!\cdot2!}=420 \) interesujących nas łamanych.
Współczynniki multimianowe także zachowują pewną regułę dodawania.
Obserwacja 5.21
Dla \( n>0 \), całkowitych \( k_1,\ldots,k_r \) takich, że \( k_1+\ldots+k_r=n \)
\( {n\choose k_1}={n-1\choose k_1-1,k_2,\ldots,k_r}+{n-1\choose k_1,k_2-1,\ldots,k_r}+\ldots+{n-1\choose k_1,k_2,\ldots,k_r-1}. \)
Dowód
Ponieważ \( n>0 \), możemy wybrać i ustalić ulubiony obiekt \( x \). Możemy go umieścić w jednym z \( r \) pudełek. Jeśli jednak umieścimy go w pierwszym, to pozostałe \( n-1 \) obiektów musimy rozłożyć do \( r \) pudeł zgodnie z warunkami wyjściowymi, ale do pierwszej szuflady mamy włożyć już \( 1 \) obiekt mniej (\( k_1-1 \) a nie \( k_1 \)). Rozłożenia tego możemy dokonać na \( {n\choose k_1-1,k_2,\ldots,k_r} \). Analogicznie gdy \( x \) umieścimy w drugim pudle, to pozostałe przedmioty rozkładamy w pudłach odpowiednio po \( k_1, k_2-1, k_3,\ldots,k_r \). Po przesumowaniu po numerach pudła, w którym jest \( x \) dostajemy nasz wzór.
Jako ćwiczenie pozostawiamy dowód następującego uogólnienia wzoru dwumiennego:
Obserwacja 5.22
\( \displaystyle (x_1+\ldots +x_r)^n = \sum_{k_1+\ldots+k_r=n} {n \choose k_1,\ldots,k_r} x_1^{k_1} x_2^{k_2}\ldots x_r^{k_r}. \)