Współczynniki multimianowe | Informatyka MIMUW

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:

${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 $\{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}.$