Ивайло Кортезов

Institute of Mathematics and Informatics
Bulgarian Academy of Sciences
Block 8 Acad. G. Bonchev St.
1113 Sofia Bulgaria
E-mail: kortezov@math.bas.bg

Резюме. В статията се предлага нагледен метод за двойно броене при доказване на комбинаторни тъждества, който се запомня с лекота от учениците. Той им позволява да го прилагат творчески в доста ситуации, като сами (пре)откриват резултатите при разнообразни сумирания. Статията е ориентирана към подготовка за математически състезания.

Ключови думи: двойно броене; биномни коефициенти; комбинаторни тъждества

Споменатият в резюмето метод за двойно броене е показан в решенията на конкретни задачи, като целенасочено външният вид на решението варира, за да може читателят да забележи, че има доста свобода при моделирането на съответната ситуация; в частност, в доста от задачите същият метод може да се приложи по начин, различен от показания.

Всички букви статията представят цели числа. Необходимо е читателите да познават сумационния символ \(\Sigma\) и означението \(\binom{n}{k}\), което показва броя начини от \(n\) дадени различни обекта да се изберат \(k\) различни, както и формулата \(\binom{n}{k}=\tfrac{n!}{k!(n-k)!}\) за \(0 \leq k \leq n\) и \(\binom{n}{k}=0\) за всички останали \(k, n\).

Задача 1. Докажете, че \(\sum_{k=1}^{n} k^{2}=\tfrac{n(n+1)(2 n+1)}{6}\).

Решение. Задаваме си въпроса по колко начина можем да настаним Иво, Яна и Ева в \((n+1)\)-етажен блок, така че Иво да живее по-високо от останалите. Ако Иво е на етаж \(k+1\) за дадено \(k=1, \ldots, n\), то за момичетата има \(k^{2}\) начина; така получаваме лявата страна. Ако са разположени на два етажа, за това има \(\binom{n+1}{2}=\tfrac{(n+1) n}{2}\) начина, като Иво е на горния етаж, а момичетата – на долния. Ако са разположени на три етажа, има \(\binom{n+1}{3}=\tfrac{(n+1) n(n-1)}{6}\) начина, като при това има два варианта кое момиче да е на най-долния етаж. Така дясната страна е равна на

\[ \tfrac{(n+1) n}{2}+\tfrac{2(n+1) n(n-1)}{6}=\tfrac{(n+1) n(3+2 n-2)}{6}=\tfrac{n(n+1)(2 n+1)}{6} . \]

Задача 2. Докажете, че \(\sum_{k=1}^{n} k^{3}=\tfrac{n^{2}(n+1)^{2}}{4}\).

Решение. Задаваме си въпроса по колко начина можем да настаним Иво, Яна, Ева и Лора в \((n+1)\)-етажен блок, така че Иво да живее по-високо от момичетата. Ако Иво е на етаж \(k+1\) за дадено \(k=1, \ldots, n\), то за момичетата има \(k^{3}\) начина; така получаваме лявата страна. Ако са разположени на два етажа, за това има \(\binom{n+1}{2}=\tfrac{(n+1) n}{2}\) начина, като Иво е на горния етаж, а момичетата – на долния. Ако са разположени на 3 етажа, има \(\binom{n+1}{3}=\tfrac{(n+1) n(n-1)}{6}\) начина, като при това има 3 варианта кое момиче да е самò на етаж и 2 варианта на кой етаж да е. Ако са разположени на 4 етажа, има \(\binom{n+1}{4}=\tfrac{(n+1) n(n-1)(n-2)}{24}\) начина, като при това има 6 варианта за разполагане на момичетата на трите им етажа. Така дясната страна е равна на

\[ \begin{aligned} & \tfrac{(n+1) n}{2}+(n+1) n(n-1)+\tfrac{(n+1) n(n-1)(n-2)}{4}= \\ = & \tfrac{(n+1) n\left(2+4 n-4+n^{2}-3 n+2\right)}{4}=\tfrac{(n+1) n\left(n^{2}+n\right)}{4} \end{aligned} \]

Задача 3. Докажете направо \(\sum_{k=1}^{n} k^{3}=\binom{n+1}{2}^{2}\), без да ползвате горното.

Решение. Както по-горе, aко Иво е на етаж \(k+1\) за дадено \(k=1, \ldots, n\), то за момичетата има \(k^{3}\) начина; така получаваме лявата страна. Дясната страна означава избор на двойки етажи \(\{a ; b\}\) и \(\{c ; d\}, a \lt b, c \lt d\).

Ако \(b \lt d\), то \(d\) е етажът на Иво, \(c\)– на Лора, \(b\)– на Ева, \(a\)– на Яна (тук Ева е по-високо от Яна).

Ако \(b \gt d\), то \(b\) е етажът на Иво, \(a\)– на Лора, \(d\)-на Яна, \(c\)– на Ева (тук Яна е по-високо от Ева).

Ако \(b=d\), то \(b\) е етажът на Иво, \(a\)– на Лора, \(c\)– общият етаж на Яна и Ева.

Задача 4. Докажете, че \(1 . n+2 .(n-1)+3 .(n-2)+\cdots+n .1=\binom{n+2}{3}\).

Решение. Дясната страна явно е равна на броя на начините да изберем три етажа в \((n+2)\)-етажен блок. Нека настаним в тях Иво, Яна и Ева (по един на етаж), така че Яна да живее под Иво и над Ева. Споменатият горе брой е равен и на лявата страна, понеже ако Яна е на етаж \(k+1(k=1,2, \ldots, n)\), то за Ева има \(k\) варианта, а за Иво има \(n+1-k\) варианта.

Задача 5. Докажете, че 1. \(\binom{n}{2}+2 .\binom{n-1}{2}+3 .\binom{n-2}{2}+\cdots+(n-1)\binom{2}{2}=\binom{n+2}{4}\).

Решение. Дясната страна е равна на броя на начините да изберем 4 етажа в \((n+2)\)-етажен блок. Нека настаним в тях Иво, Яна, Ева и Боян (по един на етаж), така че Боян да живее под момичетата, но над Иво. Този брой е равен и на лявата страна, понеже ако Боян е на етаж \(k+1(k=1,2, \ldots, n)\), то за Иво има \(k\) варианта, а за момичетата има \(\binom{n+1-k}{2}\) варианта.

Задача 6. Докажете, че

\[ n\binom{3}{3}+(n-1)\binom{4}{3}+\cdots+2\binom{n+1}{3}+1\binom{n+2}{3}=\binom{n+4}{5} \]

Решение. Дясната страна е равна на броя на начините да изберем 5 етажа в \((n+4)\)-етажен блок. Нека настаним в тях Иво, Яна, Ева, Боян и Лора (по един на етаж), така че Боян да живее над момичетата, но под Иво. Споменатият горе брой е равен и на лявата страна, понеже Боян е на някой от етажите \(4,5, \ldots, n+3\) и:

- ако е на етаж 4, то за момичетата има \(\binom{3}{3}\) избора, а за Иво има \(n\) избора;

- ако е на етаж 5, то за момичетата има \(\binom{4}{3}\) избора, а за Иво има \(n-1\) избора, и т.н.;

- ако е на етаж \(n+2\), то за момичетата има \(\binom{n+1}{3}\) избора, а за Иво има 2 избора;

- ако е на етаж \(n+3\), то за момичетата има \(\binom{n+2}{3}\) избора, а за Иво има 1 избор.

Задача 7. Докажете, че

\[ \binom{3}{3} \cdot\binom{n-3}{2}+\binom{4}{3} \cdot\binom{n-4}{2}+\binom{5}{3} \cdot\binom{n-5}{2}+\cdots+\binom{n-2}{3}\binom{2}{2}=\binom{n+1}{6} . \]

Решение. Дясната страна е равна на броя на начините да изберем 6 етажа в \((n+1)\)-етажен блок. Нека настаним в тях Иво, Яна, Ева, Мими, Боян и Лора (по един на етаж), така че Мими да живее над другите момичета, но под момчетата. Споменатият горе брой е равен и на лявата страна, понеже Мими е на някой от етажите \(4,5, \ldots, n-1\) и:

– ако е на етаж 4, то за момичетата има \(\binom{3}{3}\) избора, а за момчетата има \(\binom{n-3}{2}\) избора;

– ако е на етаж 5, то за момичетата има \(\binom{4}{3}\) избора, а за момчетата – \(\binom{n-3}{2}\) избора, и т.н.;

– ако е на етаж \(n-1\), то за момичетата има \(\binom{n-2}{3}\) избора, а за момчетата \(-\binom{2}{2}\) избора.

Задача 8. Дадени са естествените числа \(k, m, n\). Докажете, че

\[ \sum_{i=0}^{n}\binom{i}{k} \cdot\binom{n-i}{m}=\binom{n+1}{k+m+1} . \]

Решение. Дясната страна е равна на броя на начините да изберем \(k+m+1\) етажа в \((n+1)\)-етажен блок. Нека настаним в тях \(k\) момчета, \(m\) момичета и един тигър (по един на етаж), така че тигърът да живее над момчетата и под момичетата. Ако тигърът е на етаж \(i+1\) за дадено \(i\), то за момчетата изборите са \(\binom{i}{k}\), а за момичетата \(-\binom{n-i}{m}\).

Задача 9. Докажете, че

\[ 2 \cdot\binom{2}{2}+3 \cdot\binom{3}{2}+4 \cdot\binom{4}{2}+\cdots+n\binom{n}{2}=2\binom{n+1}{3}+3\binom{n+1}{4} . \]

Решение. Ще преброим по колко начина можем да настаним Иво, Яна, Ева и Лора в \((n+1)\)-етажен блок, така че Иво да е най-високо, а Ева да е по-високо от Лора.

За дясната страна:

Ако са разположени на три етажа, за това има \(\binom{n+1}{3}\) начина, като Иво е на горния етаж, Ева е над Лора, а Яна е на етажа на Ева или на Лора (2 избора). Ако са разположени на 4 етажа, има \(\binom{n+1}{4}\) начина, като при Иво е най-горе, Ева е над Лора, а за Яна има три избора: над Ева, между Ева и Лора или под Лора.

Задача 10. Докажете, че

\[ n \cdot 1^{2}+(n-1) \cdot 2^{2}+(n-2) \cdot 3^{2}+\cdots+1 \cdot n^{2}=\binom{n+2}{3}+2\binom{n+2}{4} \]

Решение. Ще преброим начините да настаним Боян, Иво, Яна и Ева в \((n+2)\)-етажен блок, така че Иво да живее по-ниско от Боян, но по-високо от останалите (които може и да са на един етаж).

За лявата страна:

Ако Иво е на етаж 2 (по-ниско не може), то за Боян има \(n\) избора за етаж, а за Яна и Ева има \(1^{2}\) избора.

Ако Иво е на етаж 3, то за Боян има (\(n-1\) ) избора за етаж, а за Яна и Ева има \(2^{2}\) избора.

Ако Иво е на етаж 4, то за Боян има (\(n-2\) ) избора за етаж, а за Яна и Ева има \(3^{2}\) избора и т.н.

Ако Иво е на етаж \(n+1\) (по-високо не може), то за Боян има 1 избор за етаж, а за Яна и Ева има \(n^{2}\) избора.

За дясната страна:

Ако са разположени на три етажа, за това има \(\binom{n+2}{3}\) начина, като Боян е на горния етаж, Иво – на средния, а Яна и Ева – на долния. Ако са разположени на 4 етажа, има \(\binom{n+2}{4}\) начина, като при това има два варианта Ева или Яна да е на най-долния етаж.

Забележка. С преобразуване на дясната страна можем да получим и тъждеството

\[ n \cdot 1^{2}+(n-1) \cdot 2^{2}+\cdots+1 \cdot n^{2}=\tfrac{n(n+1)^{2}(n+2)}{12} \]

Задача 11. Докажете, че

\[ \binom{2}{2}^{2}+\binom{3}{2}^{2}+\binom{4}{2}^{2}+\cdots+\binom{n}{2}^{2}=\binom{n+1}{3}+6\binom{n+1}{4}+6\binom{n+1}{5} . \]

Решение. Ще преброим по колко начина можем да настаним Иво, Яна, Ева, Боян и Лора в \((n+1)\)-етажен блок, така че Иво да е най-високо, Яна да е по-високо от Ева, а Боян – по-високо от Лора.

За лявата страна:

Ако Иво е на етаж 3, то за Яна-Ева има \(\binom{2}{2}\) избора за етажи, както и за Боян-Лора.

Ако Иво е на етаж 4, то за Яна-Ева има \(\binom{3}{2}\) избора за етажи, както и за Боян-Лора.

Ако Иво е на етаж 5, то за Яна-Ева има \(\binom{4}{2}\) избора за етажи, както и за Боян-Лора и т.н.

Ако Иво е на етаж \(n+1\), то за Яна-Ева има \(\binom{n}{2}\) избора за етажи, както и за Боян-Лора.

За дясната страна:

Ако са разположени на три етажа, за това има \(\binom{n+1}{3}\) начина, като Иво е на горния етаж, Яна и Боян са на средния етаж, а Ева и Лора – на долния.

Ако са разположени на 4 етажа, има \(\binom{n+1}{4}\) начина, като се спазва наредбата и на един етаж са Яна-Боян (2 варианта за Ева и Лора), Яна-Лора, Ева-Боян или Ева-Лора (2 варианта за Яна и Боян): общо \(2+1+1+2=6\) варианта. Ако са разположени на 5 етажа, има \(\binom{n+1}{5}\) начина; Иво е най-горе, а за останалите има \(4!=24\) наредби; в половината от тях Боян е над Лора и в половината от тези Яна е над Ева, така че тук има \(24: 4=6\) варианта.

Забележка. Преобразувайки дясната страна, получаваме

\[ \sum_{k=2}^{n}\binom{k}{2}^{2}=\tfrac{n\left(n^{2}-1\right)\left(3 n^{2}-2\right)}{60} \]

Задача 12. Докажете, че

\[ n^{2} \cdot 1^{2}+(n-1)^{2} \cdot 2^{2}+(n-2)^{2} \cdot 3^{2}+\cdots+1^{2} \cdot n^{2}=\binom{n+2}{3}+4\binom{n+2}{4}+4\binom{n+2}{5} \]

Решение. Ще преброим по колко начина можем да настаним Ани, Ася, Гео, Еми и Ели в \((n+2)\)-етажен блок, така че Гео да живее по-ниско от Ани и Ася, но по-високо от Еми и Ели (тези с една буква може да са на един етаж).

За лявата страна:

Ако Гео е на етаж 2 (по-ниско не може), то за Ани и Ася има \(n^{2}\) избора за етаж, а за Еми и Ели има \(1^{2}\) избор.

Ако Гео е на етаж 3, то за Ани и Ася има \((n-1)^{2}\) избора за етаж, а за Еми и Ели има \(2^{2}\) избора.

Ако Гео е на етаж 4, то за Ани и Ася има \((n-2)^{2}\) избора за етаж, а за Еми и Ели има \(3^{2}\) избора и т.н.

Ако Гео е на етаж \(n+1\), то за Ани и Ася има \(1^{2}\) избор за етаж, а за Еми и Ели има \(n^{2}\) избора.

За дясната страна:

Ако са разположени на три етажа, за това има \(\binom{n+2}{3}\) начина, като Ани и Ася са на горния етаж, Гео – на средния, а Еми и Ели – на долния. Ако са разположени на 5 етажа, има \(\binom{n+2}{5}\) начина, като при това има 2  кое момиче да е на най-долния етаж, и 2 варианта кое да е на най-горния, затова ще умножим по 4. Ако са разположени на 4 етажа, има \(\binom{n+2}{4}\) начина, при което има 2 варианта на кой от средните етажи да е Гео, и 2 варианта кое момиче да е самò на краен етаж, затова ще умножим по 4.

Задача 13. Докажете, че \[ 1^{2} \cdot\binom{n}{2}+2^{2} \cdot\binom{n-1}{2}+3^{2} \cdot\binom{n-2}{2}+\cdots+(n-1)^{2} \cdot\binom{2}{2}=\binom{n+2}{4}+2\cdot\binom{n+2}{5} \] Решение. По колко начина можем да настаним Ани, Ася, Гео, Димо и Емо в \((n+2)\)-етажен блок, така че хората с по-предна буква да са на по-нисък етаж?

За лявата страна:

Ако Гео е на етаж 2, за Ани и Ася има \(1^{2}\) избора за етаж, а за Димо и Емо има \(\binom{n}{2}\) избора.

Ако Гео е на етаж 3, за Ани и Ася има \(2^{2}\) избора за етаж, а за Димо и Емо има \(\binom{n-1}{2}\) избора.

Ако Гео е на етаж 4, за Ани и Ася има \(3^{2}\) избора за етаж, а за Димо и Емо има \(\binom{n-2}{2}\) избора и т.н.

Ако Гео е на етаж \(n\), то за Ани и Ася има \((n-1)^{2}\) избор за етаж, а за Еми и Ели има \(\binom{2}{2}\) избора.

За дясната страна:

Ако са разположени на 4 етажа, за това има \(\binom{n+2}{4}\) начина, като Ани и Ася са на долния етаж, нагоре следват Гео, Димо и Емо. Ако са разположени на 5 етажа, има \(\binom{n+2}{5}\) начина, като при това има 2 варианта кое момиче да е на най-долния етаж, затова ще умножим по 2.

Забележка. Ако горе заменим \(n\) с \(n-1\) и да преобразуваме, получаваме тъждеството

\[ \sum_{k=0}^{n} k^{2}\binom{n-k}{2}=\tfrac{(n+1) n(n-1)(n-2)(2 n-1)}{120} . \] Задача 14. Докажете, че

\[ 2^{2} \cdot\binom{2}{2}+3^{2} \cdot\binom{3}{2}+\cdots+n^{2} \cdot\binom{n}{2}=4\binom{n+1}{3}+15\binom{n+1}{4}+12\binom{n+1}{5} \] Решение. По колко начина можем да настаним Лора, Боян, Ева, Иво и Яна в \((n+1)\)-етажен блок, така че Яна да е най-високо и Боян да е по-високо от Лора?

За лявата страна:

Ако Яна е на етаж 3, за Ева и Иво има \(2^{2}\) избора за етаж, а за Боян-Лора има \(\binom{2}{2}\) избора.

Ако Яна е на етаж 4, за Ева и Иво има \(3^{2}\) избора за етаж, а за Боян-Лора има \(\binom{3}{2}\) избора и т.н.

Ако Яна е на етаж \(n+1\), за Ева и Иво има \(n^{2}\) избора за етаж, а за Боян-Лора има \(\binom{n}{2}\) избора.

За дясната страна:

-Ако са разположени на 3 етажа, за това има \(\binom{n+1}{3}\) начина, като на тези три етажа отгоре надолу са Яна, Боян и Лора; за Ева има 2 варианта дали да е на етажа на Боян, или на Лора; и за Иво има 2 варианта дали да е на етажа на Боян, или на Лора; затова ще умножим по 4.

-Ако са разположени на 4 етажа, за това има \(\binom{n+1}{4}\) начина, като най- горе е Яна. Има 3 избора на коя двойка етажи да са Лора и Боян. За всяка от другите две има 3 варианта на кой етаж да е (при Боян, при Лора или на останалия етаж); оттук трябва да махнем вариантите, в които останалият етаж остава незает (2 варианта за Ева и 2 за Иво). В крайна сметка, трябва да умножим по \(3(3.3-2.2)=15\).

-Ако са на 5 етажа, за това има \(\binom{n+1}{5}\) начина, като най-горе е Яна, а за останалите има \(4!=24\) варианта, от които в половината Боян е над Лора; затова ще умножим по \(24: 2=12\).

Забележка. Преобразувайки дясната страна, имаме \[ \sum_{k=0}^{n} k^{2}\binom{k}{2}=\tfrac{n\left(n^{2}-1\right)\left(12 n^{2}+15 n+2\right)}{120} \]

Задача 15. Докажете, че \(\sum_{k=1}^{n} k^{3}(n-k)=\binom{n+1}{3}+6\binom{n+1}{4}+6\binom{n+1}{5}\).

Решение. По колко начина можем да настаним Ади, Ани, Ася, Ели и Ива в \((n+1)\)-етажен блок, така че хората с по-предна буква да са на по-нисък етаж?

За лявата страна. Ако Ели е на етаж \(k+1\) за дадено \(k=1, \ldots, n\), то за Ади, Ани и Ася има \(k^{3}\) начина, а за Ива има \(n-k\) начина.

За дясната страна. Ако са разположени на три етажа, за това има \(\binom{n+1}{3}\) начина, като Ади, Ани и Ася са на долния етаж, Ели – на средния, и Ива – най-горе. Ако са разположени на 4 етажа, има \(\binom{n+1}{4}\) начина, като при това има 3 варианта кое момиче с „А“ да е само на етаж, и 2 варианта – на кой етаж да е. Ако са разположени на 5 етажа, има \(\binom{n+1}{5}\) начина, като при това има 6 варианта за разполагане на момичетата с „А“ на трите им етажа. Така дясната страна е равна на \(\binom{n+1}{3}+6\binom{n+1}{4}+6\binom{n+1}{5}\).

Забележка. Преобразувайки дясната страна, имаме

\(\sum_{k=1}^{n} k^{3}(n-k)=\tfrac{(n+1) n(n-1)\left(3 n^{2}-2\right)}{60}\).

Забележка.Сравнявайки със задача 11, получаваме \(\sum_{k=1}^{n} k^{3}(n-k)=\sum_{k=2}^{n}\binom{k}{2}^{2}\). Но можем да получим това и директно с описания метод, ако се запитаме по колко начина можем да настаним Ади, Ани, Ася, Иво и Тео в \((n+1)\)-етажен блок, така че хората с по-предна буква да са на по-нисък етаж. Ако Иво е на етаж \(k+1\) за дадено \(k=1, \ldots, n\), то за момичетата има \(k^{3}\) начина, а за Тео има \(n-k\) начина; така получаваме лявата страна.

За дясната страна, за всяко \(k=2, \ldots, n\) слагаме Тео на етаж \(k+1\) и избираме двойки етажи \(\{a ; b\}\) и \(\{c ; d\}, a \lt b \leq k, c \lt d \leq k\).

Ако \(b \lt d\), то \(d\) е етажът на Иво, \(c\)– на Ани, \(b\)– на Ади, \(a\)-на Ася (тук Ади е по-високо от Ася).

Ако \(b \gt d\), то \(b\) е етажът на Иво, \(a\)– на Ани, \(d\)– на Ася, \(c\)-на Ади (тук Ася е по-високо от Ади).

Ако \(b=d\), то \(b\) е етажът на Иво, \(a\)– на Ани, \(c\)– общият етаж на Ася и Ади.

БЕЛЕЖКИ

1. Напомняме, че \(\binom{i}{j}=0\) при \(j \lt 0\) и при \(j \gt i\).