Współczynniki multimianowe

Współczynniki multimianowe


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}\natur \), \( 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}\natur \), \( k,l,k_1,\ldots,k_r\in\mathbb{Z}\integer \) takich, że \( k_1+\ldots k_r=n= k+l \) zachodzi:

  • \( {n\choose n,0,\ldots,0}=1 \),
  • \( {n\choose 1,1,\ldots,1}=1 \),
  • \( {n\choose 0,k_1,\ldots,k_r}={n\choose k_1,\ldots,k_r} \),
  • \( {n\choose l,l,0,\ldots,0}={n\choose k}={n\choose l} \),
  • \( {n\choose k_1,\ldots,k_r} = {n\choose k_{\sigma(1)},\ldots,k_{\sigma(r)}} \), dla dowolnej permutacji \( \sigma \) zbioru \( \set\{1,2,\ldots,r\} \).

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:

  • wyborze \( k_1 \) obiektów spośród wszystkich \( n \) i umieszczeniu ich w pierwszym pudełku - możemy to uczynić na \( {n\choose k_1} \) sposobów,
  • wyborze \( k_2 \) obiektów spośród pozostałych \( n-k_1 \) i umieszczeniu ich w drugim pudełku - możemy to uczynić na \( {n-k_1\choose k_2} \) sposobów,
  • wyborze \( k_3 \) obiektów spośród pozostałych \( n-(k_1+k_2) \)

i umieszczeniu ich w trzecim pudełku - możemy to uczynić na \( {n-(k_1+k_2)\choose k_3} \) sposobów,

  • ...
  • wyborze \( k_r \) obiektów spośród pozostałych \( n-(k_1+\ldots+k_{r-1})=k_r \) i umieszczeniu ich w ostatnim pudełku - możemy to uczynić na \( {n-(k_1+\ldots+k_{r-1})\choose k_r}={k_r\choose k_r}=1 \) 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}. \)