Tübitak Lise 1. Aşama 2000 Soru 11

[geo]

$7$ kırmızı, $7$ beyaz topu, her kutuda tam olarak $2$ top olması koşuluyla, $7$ kutuya kaç değişik biçimde dağıtabiliriz?

$
\textbf{a)}\ 163
\qquad\textbf{b)}\ 393
\qquad\textbf{c)}\ 858
\qquad\textbf{d)}\ 1716
\qquad\textbf{e)}\ \text {Hiçbiri}
$

[geo]

Yanıt: $\boxed{B}$

Önce kırmızı topları dağıtalım. Tüm kırmızı toplar dağıtıldıktan sonra, toplamda $14$ top olacağı için geri kalan $7$ top, $7$ boşluğa tek bir şekilde dağıtılır. Yani soru, "$7$ topu $7$ kutuya, her kutuda en fazla $2$ top olacak şekilde kaç değişik biçimde dağıtırız?" oldu.
Kırmızı toplar kutulara ($(x_1,x_2,x_3,x_4,x_5,x_6,x_7)$ ile her kutunun içindeki kırmızı top sayısını gösteriyoruz),
Hiçbir kutuda $2$ kırmızı top olmayacak şekilde ($(1,1,1,1,1,1,1)$)  $\dfrac{7!}{7!}=1$ değişik biçimde,

tam olarak $1$ kutuda $2$ kırmızı top olacak şekilde ($(2,1,1,1,1,1,0)$)  $\dfrac{7!}{5!1!1!} = 42$ değişik biçimde,

tam olarak $2$ kutuda $2$ kırmızı top olacak şekilde ($(2,2,1,1,1,0,0)$)  $\dfrac{7!}{3!2!2!} = 210$ değişik biçimde,

tam olarak $3$ kutuda $2$ kırmızı top olacak şekilde ($(2,2,2,1,0,0,0)$)  $\dfrac{7!}{3!3!} = 140$ değişik biçimde dağıtılır.

Yani toplamda, $1+42+210+140=393$ farklı şekilde dağıtılır.

[geo]

Her kutuda $0, 1$ ya da $2$ kırmızı top olabilir. Beyaz toplar geri kalan yerlere tek bir şekilde yerleşecektir.

Bu durumda $(1+x+x^2)^7$ polinomunda $x^7$ nin katsayısı aradığımız yanıttır. (bkz. Generating Functions [Üretici Fonksiyonlar])

$1^ax^b(x^2)^{c} = x^7$ olması için $a+b+c = 7$ ve $b+2c = 7$ olması gerekir. $(b,c) = (1,3), (3,2), (5,1), (7,0)$ aradığımız değerlerdir.

O halde, aradığımız katsayı;

$\begin{array} {lcl}
\dbinom {7}{3,1,3} + \dbinom {7}{2,3,2} + \dbinom {7}{1,5,1} + \dbinom {7}{0,7,0} &=& \dfrac {7!}{3!1!3!} + \dfrac {7!}{2!3!2!} + \dfrac {7!}{1!5!1!} + \dfrac {7!}{0!7!0!} \\
&=& 7\cdot 5 \cdot 4 + 7\cdot 6 \cdot 5 + 7\cdot 6 + 1 \\
&=& 7\cdot 56 + 1 \\
&=& 393
\end{array}$

[geo]

Bir önceki çözümün başlangıç adımlarını uyguladıktan sonra $(1+x+x^2)^7$ polinomunda $x^7$ li terimi bulalım.

$\dfrac 1{1-x} = 1 + x + x^2 + \dots$ serisini kullanarak;

$(1+x+x^2)^7 = \dfrac {\left (1-x^3 \right )^7}{(1-x)^7} = \left (1-x^3 \right )^7(1+x+x^2 + \dots)^{7}$ elde ederiz.

$(1+x+x^2 + \dots)^{7}$ polinomunda $x^k$ lı terimin katsayısını bulmak $k$ top $7$ kişiye kaç farklı şekilde dağıtılır sorusu ile özdeştir. Cevap da $\dbinom {k+6}{6}$ dır.

$\left (1-x^3 \right )^7$ açılımından $x^0$, $x^3$, $x^6$ lı terimlerin katsayıları sırasıyla $\dbinom 70$, $-\dbinom 71$ ve $\dbinom 72$ olacaktır.

$(1+x+x^2 + \dots)^{7}$ açılımdan $x^7$, $x^4$, $x^1$ lı terimlerin katsayıları sırasıyla $\dbinom {7 + 6}{6}$, $\dbinom {4 + 6}{6}$ ve $\dbinom {1 + 6}{6}$ olacaktır.

O halde, $x^7$ li terimin katsayısı $\dbinom 70 \cdot \dbinom {13}6 - \dbinom 71 \cdot \dbinom {10}6 + \dbinom 72 \cdot \dbinom 76 = 1716 - 1470 + 147 = 393$ tür.

Not:
Genelleştirilmiş Binom Teoremi'nden

$(1+x)^n = \displaystyle \sum_{k=0}^{\infty} \binom{n}{k}x^k$

$(1-x)^{-n} = \displaystyle \sum_{k=0}^{\infty} \binom{-n}{k}(-x)^k$

$\dbinom {-n}{k} = (-1)^k \dbinom {n+ k - 1}{k}$

Dolayısıyla $(1-x)^{-n}$ açılımında $x^k$ lı terimin katsayısı $\dbinom {-n}{k} (-x)^k = \dbinom {n+ k - 1}{k} \cdot x^k$ olacaktır.