Ivaylo Kortezov

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

Abstract. The article proposes a double counting method for proving combinatorial identities that is easily visualized and remembered by the students. It allows them to apply it creatively to many situations and to (re)discover related results by themselves. The article is oriented towards preparation for mathematical contests mainly in junior high school, however the acquired techniques can be useful far beyond that age.

Keywords: double counting; binomial coefficients; combinatorial identities

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

Всички букви статията представят цели числа. Необходимо е читателите да познават сумационния символ \(\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\).