Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 1. Aşama => 2000 => Konuyu başlatan: geo - Nisan 26, 2014, 05:20:25 ös
-
$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}
$
-
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.
-
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}$
-
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 (https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_(Morris)/02%3A_Enumeration/07%3A_Generating_Functions/7.02%3A_The_Generalized_Binomial_Theorem)'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.