Binomial Əmsallar və Kombinatorik İsbat — Onlayn dərslik

Qeyd. Bu dərsdə nələr öyrənəcəyik? Dərs 2-də biz

C(n,k)

kəmiyyəti ilə tanış olduq. İndi isə onun daxili strukturuna nəzər yetirəcəyik: bu kəmiyyətlər bir-biri ilə necə əlaqəlidir, nəyə görə «binomial əmsal» adlanırlar və — ən əsası — eynilikləri cəbri hesablamalarla deyil, məhz kombinatorik sayma yolları ilə necə isbat etmək olar.Bu dərsin bizə verəcəyi ən böyük qazanc sadəcə bir düstur deyil, çox güclü bir metoddur:

Eyni çoxluğu iki fərqli üsulla say — alınan nəticələr mütləq bərabər olmalıdır.

Kombinatorikada buna ikili sayma (double counting) metodu deyilir. İlk baxışdan çox sadə bir fikir kimi görünsə də, olimpiada kombinatorikasının ən dərin isbatları məhz bu prinsipə əsaslanır. Bu dərsdə biz həmin metodu eyniliklər üzərində məşq edəcəyik; Blok B-nin 6-cı dərsində isə eyni alətdən istifadə edərək real turnir, masa və şəbəkə (qraf) məsələlərini asanlıqla həll edəcəyik.

Əvvəlki dərslərdən nələri bilməliyik: Toplama və vurma qaydası, tamamlayıcı sayma (Dərs 1);

n!

P(n,k)

C(n,k)

, bölmə prinsipi (Dərs 2). Başqa heç bir xüsusi bilik tələb olunmur.1Binomial əmsal: eyni kəmiyyətin üç fərqli təqdimatı

Tərif 1.1 (Binomial əmsal).

0\le k\le n

tam ədədləri üçün

\binom{n}{k}=C(n,k)=\frac{n!}{k!\,(n-k)!}

kəmiyyətinə binomial əmsal deyilir və «

n

-in

k

-lısı» kimi oxunur.

k<0

və ya

k>n

olduqda

\binom{n}{k}=0

qəbul edilir.

Bu kəmiyyətə üç fərqli cəhətdən yanaşmaq olar və məsələ həllində hər üçü bizə lazım olacaq:

Yanaşma	Kombinatorik mənası
Seçim	$n$ sayda elementdən $k$ -sını sırasız seçmə üsullarının sayı
Altçoxluq	$n$ elementli çoxluğun tam $k$ elementli altçoxluqlarının sayı
Sətir (Söz)	$k$ ədəd « $1$ » və $n-k$ ədəd « $0$ »-dan ibarət binar sətirlərin sayı

Qeyd. Üçüncü yanaşma xüsusilə güclüdür. Çünki

0

–

1

binar sətri əslində bir qərarlar ardıcıllığıdır: yəni çoxluğun hər bir elementi üçün verilən «seçdim / seçmədim» qərarıdır. Bir çox eyniliklər məhz bu dildə ifadə edildikdə onların mənası öz-özlüyündə aydın olur. Aşağıdakı isbatların böyük əksəriyyətində biz məhz bu dilə keçid edəcəyik.

Teorem 1.2 (Simmetriya xassəsi).

\displaystyle \binom{n}{k}=\binom{n}{n-k}

İsbat. Cəbri yolla. Düsturda

k

ilə

n-k

-nın yerini dəyişsək, məxrəc heç bir şəkildə dəyişmir:

\dfrac{n!}{k!(n-k)!}=\dfrac{n!}{(n-k)!\,k!}

.Kombinatorik yolla (əsl isbat). Bərabərliyin sol tərəfi çoxluğun

k

elementli altçoxluqlarının sayını göstərir, sağ tərəfi isə

n-k

elementli altçoxluqlarının sayını. Hər bir

k

elementli altçoxluğa onun tamamlayıcısını (yerdə qalan elementlərini) uyğunlaşdıraq — onun tamamlayıcısı dəqiq

n-k

elementlidir. Bu uyğunlaşdırma qarşılıqlı birmənalıdır (çünki tamamlayıcının tamamlayıcısı elə çoxluğun özüdür), deməli bu iki qrupun (ailənin) element sayı tamamilə bir-birinə bərabərdir.

Qeyd. Bu iki isbat arasındakı fərqə diqqət yetirin. Cəbri isbat riyazi olaraq tamamilə düzgündür, amma prosesin məğzini heç cür izah etmir: bunun üçün siz artıq düsturu əvvəlcədən bilməlisiniz. Kombinatorik isbat isə məntiqi səbəbi göstərir — «

k

nəfəri seçmək, əslində yerdə qalan

n-k

nəfəri seçməklə eyni şeydir». Olimpiadalarda kombinatorik isbatlar həm daha qısa olur, həm də mürəkkəb düsturlar yadınızdan çıxsa belə, köməyinizə çatır.

2Paskal üçbucağıBinomial əmsalları sətirlər üzrə üçbucaq (cədvəl) şəklində düzək:

n

-ci sətirdə

\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}

yerləşsin.

$n=0$							1
$n=1$						1		1
$n=2$					1		2		1
$n=3$				1		3		3		1
$n=4$			1		4		6		4		1
$n=5$		1		5		10		10		5		1
$n=6$	1		6		15		20		15		6		1

Cədvəldəki hər bir ədəd məhz özündən bir sətir yuxarıdakı iki qonşu ədədin cəminə bərabərdir. Bu qətiyyən təsadüf deyil.

Teorem 2.1 (Paskal eyniliyi).

1\le k\le n-1

üçün

\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}.

İsbat.

\{1,2,\dots,n\}

çoxluğunun

k

elementli altçoxluqlarını sayaq — düsturun sol tərəfi məhz bunu ifadə edir. İndi isə eyni şeyi fərqli bir məntiqlə sayaq: bu altçoxluqları $n$ elementinin iştirak edib-etməməsinə görə iki hala ayıraq (Dərs 1-in hallara ayırma qaydası — bu iki hal kəsişmir və bütün altçoxluqları tam əhatə edir).

• $n$ elementi altçoxluğa daxildir. O zaman altçoxluğun yerdə qalan $k-1$ elementini mütləq $\{1,\dots,n-1\}$ çoxluğundan seçmək lazımdır: $\binom{n-1}{k-1}$ üsul.
• $n$ elementi altçoxluğa daxil deyil. O zaman altçoxluğun bütün $k$ elementi də məhz $\{1,\dots,n-1\}$ çoxluğundan seçilməlidir: $\binom{n-1}{k}$ üsul.

Toplama qaydasına əsasən bu iki halın cəmi

\binom{n-1}{k-1}+\binom{n-1}{k}

olur. Hər iki sayma metodu eyni bir çoxluğu saydığına görə, alınan nəticələr mütləq bərabərdir.

Qeyd. Diqqət: bu, bizim ilk «ikili sayma» isbatımız idi. Sxemə diqqətlə baxın:

1. Ortaya bir çoxluq qoyduq (burada: çoxluğun $k$ elementli altçoxluqları).
2. Onu birinci üsulla saydıq — $\binom{n}{k}$ .
3. Eyni çoxluğu ikinci üsulla (hallara ayırmaqla) saydıq.
4. İki nəticə eyni çoxluğu saydığı üçün onları bir-birinə bərabərləşdirdik.

Bütün dərs boyu bu dörd addımın təkrar-təkrar tətbiqini görəcəksiniz. Məsələlərin forması dəyişəcək, lakin bu təməl sxem dəyişməyəcək.

Nümunə 2.1 (izah). Paskal eyniliyinə əsasən

\binom{9}{4}

-ü hesablayaq:

\binom{9}{4}=\binom{8}{3}+\binom{8}{4}=56+70=126

Qeyd. Paskal eyniliyi əmsalları hesablamaq üçün ən sürətli yol deyil — böyük

n

-lər üçün düsturun özünü tətbiq etmək daha əlverişlidir. Bu eyniliyin əsl riyazi dəyəri strukturundadır: o, binomial əmsalları zəncirvari olaraq bir-birinə bağlayır və bir çox mürəkkəb isbatlarda riyazi induksiya üçün keçid addımını təmin edir.

3Sətirlər üzrə cəmlər: ikili sayma metodunun ilk bəhrələri

Teorem 3.1 (Sətir cəmi).

\displaystyle \sum_{k=0}^{n}\binom{n}{k}=\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n}=2^n

İsbat. Fərz edək ki, biz

n

elementli çoxluğun bütün altçoxluqlarını saymaq istəyirik.Birinci sayma. Çoxluğun hər bir elementi üçün müstəqil şəkildə «daxildir/daxil deyil» (var/yox) qərarı veririk (Bax: Dərs 1):

2^n

.İkinci sayma. Bütün altçoxluqları öz ölçülərinə (element saylarına) görə hallara ayıraq:

0

elementli altçoxluqlar

\binom{n}{0}

sayda,

1

elementlilər

\binom{n}{1}

sayda, …, tam

n

elementlilər isə

\binom{n}{n}

saydadır. Bu hallar qətiyyən kəsişmir, ona görə də toplama qaydası bizə onların cəmini verir.Hər iki sayma eyni bir ailəni (bütün altçoxluqları) saydı — deməli, nəticələr bərabərdir.

Teorem 3.2 (İşarəli cəm).

n\ge 1

olduqda

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

, yəni

\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\dots = \binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\dots = 2^{n-1}.

İsbat. Teoremin əsas iddiası budur ki, cüt ölçülü (element sayı cüt olan) altçoxluqların sayı, tək ölçülü altçoxluqların sayına tamamilə bərabərdir. Bunu xüsusi bir cütləşdirmə (bijeksiya) vasitəsilə isbat edək: çoxluqdan hər hansı bir

1

elementini seçək və ixtiyari

A

altçoxluğuna aşağıdakı qayda ilə yeni bir

A^{*}

altçoxluğunu uyğunlaşdıraq:

A^{*}=\begin{cases} A\setminus\{1\}, & 1\in A,\\ A\cup\{1\}, & 1\notin A\end{cases}

Yəni, «əgər

1

elementi altçoxluqda varsa onu çıxar, yoxdursa ona əlavə et». Aydındır ki, bu əməliyyat altçoxluğun ölçüsünü (element sayını) dəqiq olaraq bircə vahid dəyişdirir — deməli, hər cüt ölçülü altçoxluğa mütləq şəkildə bir tək ölçülü altçoxluq uyğun gəlir. Üstəlik

(A^{*})^{*}=A

-dır, yəni bu uyğunlaşdırma qarşılıqlı birmənalıdır və bütün altçoxluqları heç biri kənarda qalmamaq şərti ilə cüt-cüt bölür.Deməli, cüt ölçülülərin sayı ilə tək ölçülülərin sayı bərabərdir; onların ümumi cəmi isə

2^n

olduğu üçün, hər biri

2^{n-1}

-ə bərabər olar.

Qeyd. Cütləşdirmə (Bijeksiya) — ikili saymanın əkiz qardaşı. Yuxarıdakı isbatda biz çoxluqları birbaşa saymadıq, sadəcə onları uyğunlaşdırdıq: iki fərqli qrupun elementlərini cüt-cüt bir-birinə bağladıq. Bu riyazi metodun adı bijeksiyadır və o, Dərs 6-nın ən əsas mövzularından biri olacaq. Hələlik sadəcə bunu yadda saxlayın: «iki ailənin (qrupun) bərabər olduğunu sübut etmək üçün onları mütləq saymaq şərt deyil — aralarında birmənalı uyğunluq (bijeksiya) yaratmaq tamamilə kifayətdir».

Teorem 3.3 (Komitə-sədr eyniliyi).

1\le k\le n

üçün

k\binom{n}{k}=n\binom{n-1}{k-1}.

İsbat. Belə bir seçim prosesi quraq: $n$ nəfərdən ibarət böyük kollektivdən $k$ nəfərlik komitə seçmək və daha sonra həmin komitə üzvlərindən birini komitəyə sədr təyin etmək — gəlin yaranan belə (komitə, sədr) cütlüklərinin sayını iki müxtəlif yolla hesablayaq.Birinci sayma (əvvəlcə komitə). Əvvəlcə komitəni

\binom{n}{k}

müxtəlif üsulla seçirik, sonra isə onun içindəki

k

üzvdən hər hansı birini sədr təyin edirik:

k\binom{n}{k}

.İkinci sayma (əvvəlcə sədr). Gəlin bu dəfə sədri birbaşa bütün

n

nəfərin içindən seçək — bunun üçün

n

imkan var; daha sonra isə komitənin yerdə qalan

k-1

sıravi üzvünü kollektivdə qalan

n-1

nəfərdən seçirik —

\binom{n-1}{k-1}

. Bu halda nəticə

n\binom{n-1}{k-1}

olur.Hər iki halda tamamilə eyni (komitə, sədr) cütlükləri sayıldığı üçün nəticələr bir-birinə bərabərdir.

Qeyd. Bu eynilik niyə bu qədər vacibdir? Birincisi, o, mürəkkəb kombinatorik cəmlərdə «

k

-nı içəri sal / çölə çıxart» tipli cəbri çevirmələrin əsasını təşkil edir. İkincisi, ondan dərhal çox faydalı bir cəm düsturu alınır:

\sum_{k=0}^{n} k\binom{n}{k} = \sum_{k=1}^{n} n\binom{n-1}{k-1} = n\sum_{j=0}^{n-1}\binom{n-1}{j} = n\,2^{n-1}.

Məsələn,

n=10

olduqda

\sum k\binom{10}{k}=10\cdot 2^9=5120

edir. Bunun kombinatorik mənası:

n

nəfərdən ibarət kollektivdə mümkün (komitə, sədr) seçimlərinin ümumi sayı məhz

n\cdot 2^{n-1}

-dir — yəni əvvəlcə sədri seçirsən, yerdə qalan hər kəs üçün isə fərdi olaraq «komitədədir/deyil» qərarını verirsən.

4Nyuton binomuİndi isə «binomial əmsal» adının əslində haradan qaynaqlandığına baxaq.

Teorem 4.1 (Nyuton binomu). İstənilən

n\ge 0

tam ədədi üçün

(x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k} = \binom{n}{0}x^n+\binom{n}{1}x^{n-1}y+\dots+\binom{n}{n}y^n .

İsbat. Çoxhədlilərin hasilini açmaq əslində nə deməkdir?

(x+y)^n

ifadəsi özlüyündə

n

dənə

(x+y)

mötərizəsinin bir-birinə vurulmasıdır:

(x+y)(x+y)\cdots(x+y) \qquad (n \text{ ədəd mötərizə}).

Cəbri olaraq mötərizələri vurub açdıqda, biz hər bir mötərizənin içindən ya

x

-i, ya da

y

-i seçib onları bir-birinə vururuq — yəni alınmış hər bir hədd əslində müəyyən bir «seçim ardıcıllığına» uyğun gəlir. Belə seçim ardıcıllıqlarının ümumi sayı

2^n

-dir və hər bir ardıcıllıq nəticədə

x^{n-k}y^k

şəklində bir hasil verir, burada

k

— seçdiyimiz

y

-lərin (və ya

y

seçilən mötərizələrin) sayını bildirir.Bəs

x^{n-k}y^k

həddi cəm şəklində neçə dəfə alınır? Dəqiq olaraq o qədər dəfə ki, biz mövcud

n

mötərizədən daxilində

y

seçiləcək olan

k

dənə mötərizəni neçə fərqli cür seçə bilərik — bu isə məhz

\binom{n}{k}

saydadır. Deməli yekun cəmdə

x^{n-k}y^k

-nın qarşısındakı əmsal

\binom{n}{k}

olacaqdır.

Qeyd. Bu isbatın məğzini sözlə yadda saxlayın: $x^{n-k}y^k$ həddinin əmsalı — $y$ -lərin məhz hansı mötərizələrdən seçiləcəyi variantlarının sayıdır. Məhz buna görə də həmin kəmiyyət binomial əmsal adlanır. Diqqət edin: bu məntiq, tam olaraq Dərs 2-də baxdığımız «

k

dənə

y

hərfi və

n-k

dənə

x

hərfini sıraya düzmək» məsələsi ilə eynidir — yəni bu, eyni kəmiyyətin «sətir (söz)» təqdimatıdır.

Ümumi hədd düsturu — əmsalları tapmağın standart metodu.

(A+B)^n

açılışındakı ixtiyari ümumi hədd belə ifadə olunur:

T_{k}=\binom{n}{k}A^{\,n-k}B^{\,k},\qquad k=0,1,\dots,n .

Hər hansı konkret bir həddin əmsalını tapmaq üçün bu dörd addımı izləyin: (1)

T_k

düsturunu yazın, (2) Mötərizələri sadələşdirərək

x

-in qüvvətini vahid

k

ilə ifadə edin, (3) Həmin qüvvəti sizdən tələb olunan (lazımi) üstə bərabərləşdirib

k

-nın qiymətini tapın, (4) Tapdığınız

k

-nı gətirib

T_k

-da yerinə qoyun. Əgər tənliyin cavabında

k

üçün tam və müsbət ədəd alınmırsa — deməli açılışda ümumiyyətlə elə bir hədd yoxdur və əmsal sıfırdır.

Nümunə 4.1 (izah).

(2x+3)^4

açılışında

x^2

həddinin əmsalını tapaq.Ümumi hədd:

T_k=\binom{4}{k}(2x)^{4-k}3^k

. Burada

x

-in qüvvəti

4-k

-dır;

4-k=2\Rightarrow k=2

. Onda

T_2=\binom{4}{2}(2x)^2 3^2 = 6\cdot 4x^2\cdot 9=216x^2 .

Deməli əmsal

216

-dır.

Nümunə 4.2 (izah).

\left(x+\dfrac{2}{x}\right)^{6}

açılışında sabit (sərbəst) həddi tapaq.

T_k=\binom{6}{k}x^{6-k}\left(\dfrac{2}{x}\right)^{k} =\binom{6}{k}2^k x^{6-2k}

. Sabit hədd olması üçün

x

-in qüvvəti

0

olmalıdır:

6-2k=0\Rightarrow k=3

T_3=\binom{6}{3}2^3=20\cdot 8=160 .

Nümunə 4.3 (izah).

\left(x^{2}+\dfrac{1}{x}\right)^{9}

açılışında

x^{3}

-ün əmsalını tapaq.

T_k=\binom{9}{k}x^{2(9-k)}x^{-k}=\binom{9}{k}x^{18-3k}

;

18-3k=3\Rightarrow 3k=15 \Rightarrow k=5

; əmsal:

\binom{9}{5}=126

Dəyişənləri əvəzetmə metodu. Nyuton binomu düsturunda

x

və

y

dəyişənlərinə müxtəlif konkret qiymətlər verməklə çox faydalı cəmlər əldə etmək olur. Ən çox istifadə olunan üç əvəzetmə bunlardır:

x=y=1:\ \sum_k \binom{n}{k}=2^n; \qquad x=1,\,y=-1:\ \sum_k (-1)^k\binom{n}{k}=0; \qquad x=1,\,y=t:\ \sum_k \binom{n}{k}t^k=(1+t)^n .

Məsələn:

\sum_{k}\binom{8}{k}3^k=(1+3)^8=4^8=65\,536

Qeyd. İki fərqli isbat, iki fərqli riyazi dil. Fikir versəniz, sətir cəminin

2^n

olmasını biz əvvəlcə kombinatorik sayma ilə isbat etdik, indi isə əvəzetmə (cəbr) ilə aldıq. Məsələ həllində hər iki yol bizə lazımdır: əvəzetmə sürətlidir və birbaşa nəticə verir, kombinatorik sayma isə daha mürəkkəb hallara ümumiləşdirilə bilir. Olimpiada məsələlərinin bir çoxunda cəbri yollar dalana dirəndikdə (tıxandıqda) məhz kombinatorik sayma bizi xilas edir.

5Əsas eyniliklər və onların kombinatorik isbatlarıİndi isə yeni öyrəndiyimiz aləti (ikili saymanı) bir neçə klassik eynilik üzərində sınaqdan keçirək.

Teorem 5.1 (Hokkey çubuğu (Hockey-stick) eyniliyi).

0\le r\le n

şərtini ödəyən tam ədədlər üçün

\binom{r}{r}+\binom{r+1}{r}+\binom{r+2}{r}+\dots+\binom{n}{r} = \binom{n+1}{r+1}.

İsbat. Eyniliyin sağ tərəfi

\{1,2,\dots,n+1\}

çoxluğundan

r+1

elementli altçoxluqları seçmə üsullarının sayıdır. Gəlin indi eyni çoxluqlar ailəsini ikinci fərqli yolla sayaq: bunun üçün hər bir altçoxluğu onun daxilindəki ən böyük elementinə görə hallara ayıraq.Fərz edək ki, seçilmiş altçoxluqdakı ən böyük element

m

-dir (

m

-in qiyməti ən azı

r+1

olmalıdır, çünki altçoxluqda ondan kiçik daha

r

sayda element seçilməlidir). O zaman altçoxluğun yerdə qalan

r

elementi yalnız və yalnız

\{1,\dots,m-1\}

çoxluğundan seçilə bilər: yəni bunun üçün

\binom{m-1}{r}

üsul var. Seçilə biləcək ən böyük

m

elementi isə

r+1

-dən başlayaraq ta

n+1

-ə qədər dəyişə bilər. Deməli bütün halların cəmi:

\sum_{m=r+1}^{n+1}\binom{m-1}{r} = \binom{r}{r}+\binom{r+1}{r}+\dots+\binom{n}{r}. \qquad

Aydındır ki, bu hallar bir-biri ilə qətiyyən kəsişmir (çünki hər altçoxluğun ən böyük elementi yeganədir və təkrarlana bilməz), deməli iki fərqli saymanın nəticələri bir-birinə bərabərdir.

Nümunə 5.1 (izah).

1+2+3+\dots+20

ədədi cəmini binomial əmsallar dilində yazaq. Bilirik ki, istənilən

i

üçün

i=\binom{i}{1}

-dir. Buna əsasən:

\sum_{i=1}^{20} i=\sum_{i=1}^{20}\binom{i}{1}=\binom{21}{2}=210 .

Tamamilə eyni məntiqlə:

\binom{2}{2}+\binom{3}{2}+\dots+\binom{8}{2}=\binom{9}{3}=84

Teorem 5.2 (Vandermonde eyniliyi).

\displaystyle \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}

İsbat. Fərz edək ki, bir sinifdə

m

sayda oğlan və

n

sayda qız var — yəni sinifdə cəmi

m+n

nəfər var. Biz onlardan

r

nəfərlik komanda seçməliyik. Gəlin belə komandaların yaradılma sayını iki fərqli cür hesablayaq.Birinci sayma. Şagirdlərin cinsinə heç bir fikir vermədən birbaşa seçirik:

\binom{m+n}{r}

.İkinci sayma. Komandaya daxil olan oğlanların sayına görə seçimi hallara ayıraq. Əgər yaradılan komandada dəqiq

k

sayda oğlan varsa, biz həmin oğlanları

\binom{m}{k}

cür, komandadakı yerdə qalan

r-k

qızı isə qızların içindən

\binom{n}{r-k}

cür seçirik. Vurma qaydasına əsasən bu halda

\binom{m}{k}\binom{n}{r-k}

qədər komanda yaranır. Buradakı

k

dəyişəni

0

-dan

r

-ə qədər dəyişə bilər və aydındır ki, oğlanların sayı fərqli olduğu üçün bu hallar kəsişmir. Toplama qaydasına görə bu halların cəmi bizə eyniliyin sol tərəfini verir.

Nümunə 5.2 (izah).

5

oğlan və

7

qızdan ibarət qrupdan

4

nəfərlik komanda seçirik. Vandermonde eyniliyi bizə deyir ki,

\sum_{k=0}^{4}\binom{5}{k}\binom{7}{4-k}=\binom{12}{4}=495 .

Gəlin yoxlamaq üçün bu cəmin hədlərini açaq (

k

— komandadakı oğlanların sayıdır):

\underbrace{1\cdot 35}_{k=0}+\underbrace{5\cdot 35}_{k=1} +\underbrace{10\cdot 21}_{k=2}+\underbrace{10\cdot 7}_{k=3} +\underbrace{5\cdot 1}_{k=4} =35+175+210+70+5=495 . \textbf{dəqiqdir}

Nəticə 5.3 (Kvadratlar cəmi).

\displaystyle \sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n}

İsbat. Vandermonde eyniliyində xüsusi hal kimi

m=n

və

r=n

qəbul edək:

\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}\binom{n}{n-k} =\sum_{k=0}^{n}\binom{n}{k}\binom{n}{k},

çünki simmetriya xassəsinə görə həmişə

\binom{n}{n-k}=\binom{n}{k}

-dır.

Nümunə 5.3 (izah). Məsələn

n=5

üçün:

1^2+5^2+10^2+10^2+5^2+1^2=1+25+100+100+25+1=252=\binom{10}{5}

. dəqiqdir

Teorem 5.4 (Altkomitə (Subcommittee) eyniliyi).

r\le k\le n

şərtini ödəyən ədədlər üçün

\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}.

İsbat.

n

nəfərdən ibarət kollektivdən

k

nəfərlik komitə, daha sonra isə həmin o komitənin daxilindən

r

nəfərlik xüsusi bir rəhbərlik (altkomitə) seçək. Yaranan belə (komitə, rəhbərlik) cütlərinin sayını iki cür sayaq.Birinci üsul: əvvəlcə komitə.

\binom{n}{k}

cür komitə seçilir, ardınca isə onun daxilindəki

k

üzvdən

r

nəfəri rəhbərliyə cəlb olunur:

\binom{k}{r}

.İkinci üsul: əvvəlcə rəhbərlik. Rəhbərliyə daxil olacaq şəxsləri birbaşa kollektivin bütün

n

nəfərindən seçirik: bunun üçün

\binom{n}{r}

imkan var; daha sonra isə komitənin yerdə qalan

k-r

sayda sıravi üzvünü rəhbərliyə düşməyən yerdə qalan

n-r

nəfərin içindən seçirik:

\binom{n-r}{k-r}

Qeyd. Komitə-sədr eyniliyi məhz bu eyniliyin xüsusi bir halıdır: Əgər düsturda

r=1

qəbul etsəniz,

\binom{n}{k}\binom{k}{1}=\binom{n}{1}\binom{n-1}{k-1}

, yəni sadələşdirilmiş şəkildə

k\binom{n}{k}=n\binom{n-1}{k-1}

alarsınız.

6İkili saymanın iş sxemi

Eyniliyi kombinatorik sayma vasitəsilə isbat etmək. Əgər qarşınızda

\text{sol}=\text{sağ}

şəklində hər hansı bir eynilik varsa, bu ardıcıl addımları izləyin:

1. Düsturun bir tərəfini «oxu» (mənalandır). Adətən düsturun vizual olaraq daha sadə olan tərəfi hər hansı bir sayma məsələsinin birbaşa cavabıdır: məsələn, « $\binom{m+n}{r}$ — cəmi $m+n$ nəfərdən $r$ nəfərlik altçoxluq seçmə üsullarıdır».
2. Həmin çoxluğu açıq təsvir et. Biz nəyi sayırıq? Bir tipik (standart) elementi qısa şəkildə kağıza yazın.
3.
İkinci sayma metodunu qur. Eyniliyin digər tərəfindəki cəmləmə ( $\sum$ ) və ya hasil işarəsi sizə məsələni məhz hansı əlamətə görə hallara ayırmaq (və ya addımlara bölmək) lazım olduğunu pıçıldayır:
- • Əgər $\sum_k$ görürsünüzsə — deməli çoxluğu $k$ -ya görə müəyyən hallara ayırmalısınız (məsələn, komandada neçə oğlan var? çoxluğun ən böyük elementi nədir? $n$ elementi daxildirmi?);
- • Əgər bir neçə əmsalın hasilini görürsünüzsə — deməli burada ardıcıl seçim (vurma qaydası) prosesi qurmalısınız.
4. Yekun nəticəni qeyd et. İsbatı bu cümlə ilə bitirin: «İki fərqli sayma metodu eyni bir çoxluğun elementlərini saydı, deməli bu nəticələr bir-birinə bərabərdir.»

Qeyd. Məsələni hansı meyara görə hallara ayırmalı — kiçik ipucu lüğəti.

Eynilikdə hansı ifadəni görürsən	Ehtimal olunan hallara ayırma meyarı
$\binom{n-1}{k-1}+\binom{n-1}{k}$	«nəzərdə tutulan sonuncu element seçimə daxildirmi?»
$\sum_k \binom{m}{k}\binom{n}{r-k}$	«seçilənlərin neçəsi sırf birinci qrupdandır?»
$\sum_m \binom{m-1}{r}$	«seçilən elementlər içərisində ən böyük element hansıdır?»
$k\binom{n}{k}$ və ya $\binom{n}{k}\binom{k}{r}$	«seçilmiş qrupun içərisindən əlavə nəsə seçilir»
$2^n$	«hər bir element üçün sərbəst var/yox qərarı»
$n\,2^{n-1}$	«əvvəlcə bir seçilmiş xüsusi element $+$ qalanları üçün var/yox qərarı»

Qeyd. Kombinatorik isbatlarda tipik səhvlər.

1. İki sayma metodu fərqli çoxluqları sayır. İsbatı kağıza yazarkən özünüz üçün «mən konkret olaraq hansı çoxluğu sayıram?» sualının cavabını açıq şəkildə yazın; şagirdlərin ən çox kəsdiyi yer məhz buradadır.
2. Ayrılan hallar kəsişir. Seçdiyiniz «Ən böyük element», « $n$ daxildirmi» kimi qruplaşdırma əlamətləri çox yaxşıdır, çünki onlar çoxluqları birmənalı olaraq ayırır. Lakin «Ən azı bir oğlan var» kimi qruplaşdırma əlamətləri pisdir — çünki bu, qrupların kəsişməsinə (eyni halın təkrar sayılmasına) aparıb çıxarır.
3. Kənar (Sərhəd) hədlər. Kombinatorikada qəbul edilmiş $\binom{n}{k}=0$ (əgər $k<0$ və ya $k>n$ olarsa) razılaşmasını unutmaq əksər hallarda cəmlərin sərhədlərində yanlış nəticə verir.
4. Cəbrə (hesablamalara) sığınmaq. Bəzi sadə eyniliklərdə faktorialları açıb kəsrləri ixtisar etmək üsulu işə yarayır, amma Vandermonde kimi eyniliklərdə bu, praktiki olaraq mümkünsüzdür. Kombinatorik isbat həmişə daha qısa və məntiqlidir.
5. Simmetriyanı gözdən qaçırmaq. $\binom{n}{k}=\binom{n}{n-k}$ xassəsini unutsanız, bu çox vaxt ifadədəki cəmi tanınmaz hala salır — buna görə həmişə hər iki formanı gözünüzün önündə yazıb müqayisə edin.

7Sadə məsələlər

Məsələ 1. Paskal üçbucağının

n=0

-dan

n=6

-ya qədər olan sətirlərini yazın.

Həll. Üçbucağın hər bir sətri mütləq

1

ilə başlayıb

1

ilə bitir, ortada qalan hər bir ədəd isə özündən yuxarıdakı iki qonşu ədədin cəmidir:

\begin{array}{c} 1\\ 1\ \ 1\\ 1\ \ 2\ \ 1\\ 1\ \ 3\ \ 3\ \ 1\\ 1\ \ 4\ \ 6\ \ 4\ \ 1\\ 1\ \ 5\ \ 10\ \ 10\ \ 5\ \ 1\\ 1\ \ 6\ \ 15\ \ 20\ \ 15\ \ 6\ \ 1 \end{array}

Cavab: yuxarıda göstərilmişdir

Məsələ 2.

\binom{9}{4}+\binom{9}{5}

cəmini faktorialları açmadan, Paskal qaydası ilə sadələşdirin.

Həll. Paskal eyniliyinə əsasən:

\binom{9}{4}+\binom{9}{5}=\binom{10}{5}=252

. Cavab:

\binom{10}{5}=252

Məsələ 3.

\binom{15}{13}

kəmiyyəti neçəyə bərabərdir?

Həll. Simmetriya xassəsinə görə:

\binom{15}{13}=\binom{15}{2}=\dfrac{15\cdot 14}{2}=105

. Cavab:

105

Məsələ 4.

\binom{20}{1}+\binom{20}{19}

cəmi neçədir?

Həll.

\binom{20}{19}

kəmiyyəti simmetriyaya görə elə

\binom{20}{1}=20

-yə bərabərdir, deməli onların cəmi

20+20=40

edir. Cavab:

40

Məsələ 5.

(x+y)^6

çoxhədlisinin açılışında

x^4y^2

həddinin əmsalı nədir?

Həll. Ümumi hədd düsturu:

T_k=\binom{6}{k}x^{6-k}y^k

; burada

k=2

olduqda axtarılan hədd alınır. Əmsal:

\binom{6}{2}=15

. Cavab:

15

Məsələ 6.

(1+x)^8

çoxhədlisinin açılışında

x^5

-in əmsalı nədir?

Həll. Nyuton binomuna görə bu

\binom{8}{5}

-dir, o isə

\binom{8}{3}

-ə bərabər olub

56

edir. Cavab:

56

Məsələ 7.

(x-1)^7

çoxhədlisinin açılışında

x^3

-ün əmsalı neçədir?

Həll. Ümumi hədd düsturu:

T_k=\binom{7}{k}x^{7-k}(-1)^k

; burada

x

-in qüvvəti

7-k=3

olmalıdır

\Rightarrow k=4

; deməli əmsal

\binom{7}{4}(-1)^4=35

-dir. Cavab:

35

Məsələ 8.

(2x+1)^5

çoxhədlisinin açılışında

x^3

-ün əmsalı neçədir?

Həll. Ümumi hədd düsturu:

T_k=\binom{5}{k}(2x)^{5-k}

; qüvvətləri bərabərləşdirsək

5-k=3\Rightarrow k=2

; deməli əmsal

\binom{5}{2}2^3=10\cdot 8=80

olar. Cavab:

80

Məsələ 9.

(3x-2)^4

çoxhədlisinin açılışında

x^2

-nin əmsalı neçədir?

Həll. Ümumi hədd:

T_k=\binom{4}{k}(3x)^{4-k}(-2)^k

; qüvvətlərdən

4-k=2\Rightarrow k=2

alarıq. Əmsal:

\binom{4}{2}3^2(-2)^2=6\cdot 9\cdot 4=216

. Cavab:

216

Məsələ 10.

\displaystyle\sum_{k=0}^{10}\binom{10}{k}

cəmi neçəyə bərabərdir?

Həll. Sətir cəmi düsturuna əsasən:

2^{10}=1024

. Cavab:

1024

Məsələ 11.

\displaystyle\sum_{k=0}^{9}(-1)^k\binom{9}{k}

cəmi neçəyə bərabərdir?

Həll. İşarəli (işarələri növbələşən) cəm

n\ge 1

olduqda həmişə sıfırdır (bunu əvəzetmə ilə

(1-1)^9=0

şəklində də almaq olar). Cavab:

0

Məsələ 12. Əgər

\binom{n}{2}=66

olarsa,

n

neçədir?

Həll.

\dfrac{n(n-1)}{2}=66\Rightarrow n(n-1)=132=12\cdot 11\Rightarrow n=12

. Cavab:

12

Məsələ 13. Əgər

\binom{n}{3}=\binom{n}{5}

olarsa,

n

neçədir?

Həll. Simmetriya xassəsinə görə həmişə

\binom{n}{3}=\binom{n}{n-3}

olur; deməli məntiqən ya

3=5

olmalıdır (bu mümkün deyil), ya da

n-3=5

olmalıdır, buradan da

n=8

alınır. Cavab:

8

Məsələ 14.

\left(x+\dfrac{2}{x}\right)^6

çoxhədlisinin açılışında sabit (sərbəst) həddi tapın.

Həll. Ümumi hədd:

T_k=\binom{6}{k}2^k x^{6-2k}

; sabit hədd üçün

x

-in qüvvəti sıfır olmalıdır, yəni

6-2k=0\Rightarrow k=3

: Bu zaman hədd:

\binom{6}{3}2^3=20\cdot 8=160

. Cavab:

160

Məsələ 15.

\left(x^2+\dfrac{1}{x}\right)^9

çoxhədlisinin açılışında

x^3

-ün əmsalı nədir?

Həll. Ümumi hədd:

T_k=\binom{9}{k}x^{18-3k}

; qüvvəti bərabərləşdirsək

18-3k=3\Rightarrow k=5

; deməli əmsal

\binom{9}{5}=126

olacaq. Cavab:

126

Məsələ 16.

1+2+3+\dots+20

cəmini binomial əmsallar vasitəsilə ifadə edin və hesablayın.

Həll. Bilirik ki,

i=\binom{i}{1}

, bunu Hokkey çubuğu eyniliyinə tətbiq etsək:

\sum_{i=1}^{20}\binom{i}{1}=\binom{21}{2}=210

alarıq. Cavab:

210

Məsələ 17.

\binom{2}{2}+\binom{3}{2}+\binom{4}{2}+\dots+\binom{8}{2}

cəmini tapın.

Həll. Hokkey çubuğu eyniliyinə əsasən bu cəm

=\binom{9}{3}=84

edir. Cavab:

84

Məsələ 18. Paskal üçbucağının

n=10

sətrindəki bütün ədədlərin cəmi neçədir?

Həll. Bu birbaşa sətir cəmi düsturudur:

2^{10}=1024

. Cavab:

1024

Məsələ 19. Paskal üçbucağının

n=12

sətrindəki ən böyük ədəd hansıdır?

Həll. Paskal üçbucağında sətirlər öz ortasında maksimum qiymətinə çatır: yəni

\binom{12}{6}=924

. Cavab:

924

Məsələ 20.

(a+b)^{10}

çoxhədlisinin açılışında

a^7b^3

həddinin əmsalı nədir?

Həll. Nyuton binomuna görə

\binom{10}{3}=120

-dir. Cavab:

120

Məsələ 21.

10

nəfərlik qrupdan (a) istənilən sayda üzvü olan (boş qrup (komissiya) da daxil olmaqla), (b) boş olmayan cəmi neçə müxtəlif komissiya qurmaq olar?

Həll. (a) Bu, bütün mümkün altçoxluqların sayıdır:

\sum_k \binom{10}{k}=2^{10}=1024

. (b) Burada yalnız

0

elementli altçoxluq (boş komissiya) çıxılır:

1024-1=1023

. Cavab: (a)

1024

; (b)

1023

Məsələ 22.

10

nəfərlik qrupdan yalnız tək sayda üzvü olan neçə komissiya qurmaq olar?

Həll. Bu, çoxluğun tək ölçülü altçoxluqlarının sayıdır və o,

2^{10-1}=512

edir. Cavab:

512

Məsələ 23. Paskal eyniliyindən istifadə edərək

\binom{10}{3}

kəmiyyətini hesablayıb yoxlayın.

Həll. Paskal eyniliyinə görə:

\binom{9}{2}+\binom{9}{3}=36+84=120

. Doğrudan da bu,

\binom{10}{3}

-ə bərabərdir. dəqiqdir Cavab:

120

Məsələ 24.

(x+y)^5

çoxhədlisinin açılışını tam şəkildə yazın.

Həll. Buradakı əmsallar birbaşa Paskal üçbucağının

5

-ci sətridir:

1,5,10,10,5,1

. Deməli:

(x+y)^5=x^5+5x^4y+10x^3y^2+10x^2y^3+5xy^4+y^5 .

Cavab: yuxarıda göstərilmişdir

Məsələ 25.

\displaystyle\sum_{k=0}^{6}\binom{6}{k}2^k

cəmini tapın.

Həll. Nyuton binomu düsturunda

x=1

y=2

qəbul edək: cəm

=(1+2)^6=3^6=729

olar. Cavab:

729

Məsələ 26.

\displaystyle\sum_{k=0}^{8}\binom{8}{k}3^k

cəmi neçədir?

Həll. Eyni əvəzetmə ilə

(1+3)^8=4^8=65\,536

alırıq. Cavab:

65\,536

Məsələ 27.

\left(x+\dfrac{1}{x}\right)^8

çoxhədlisinin açılışında sabit hədd nədir?

Həll. Ümumi hədd:

T_k=\binom{8}{k}x^{8-2k}

; sabit hədd olması üçün

k=4

olmalıdır. Əmsal:

\binom{8}{4}=70

. Cavab:

70

Məsələ 28.

(x+y)^{12}

çoxhədlisinin açılışında ümumilikdə neçə hədd var?

Həll. İndeks

k

ədədi

0,1,\dots,12

qiymətlərini ala bildiyi üçün burada

13

hədd mövcuddur (və hamısının da əmsalı sıfırdan fərqlidir). Cavab:

13

Məsələ 29.

(x+y)^{20}

çoxhədlisinin açılışında

x^{18}y^2

həddinin əmsalı neçədir?

Həll.

\binom{20}{2}=190

. Cavab:

190

Məsələ 30.

\binom{6}{0}+\binom{6}{2}+\binom{6}{4}+\binom{6}{6}

cəmini hesablayın.

Həll. Bu, cüt indeksli hədlərin cəmidir və düstura əsasən

2^{6-1}=32

-dir. (Sadə sadalama ilə yoxlama:

1+15+15+1=32

.) Cavab:

32

8Orta və çətin məsələlər

Məsələ 31. Paskal eyniliyini —

\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}

— cəbri düsturla deyil, kombinatorik məntiqlə isbat edin.

Həll. Fərz edək ki, biz

\{1,2,\dots,n\}

çoxluğunun tam olaraq

k

elementli altçoxluqlarını saymaq istəyirik: Eyniliyin sol tərəfi birbaşa bunu ifadə edir.Gəlin indi həmin eyni altçoxluqlar ailəsini, xüsusi olaraq

n

elementinin iştirak edib-etməməsinə (taleyinə) görə iki kəsişməyən hala ayıraq:

• Əgər $n$ elementi altçoxluğa daxildirsə, onda yerdə qalan $k-1$ elementi məcburuq ki, ancaq $\{1,\dots,n-1\}$ çoxluğundan seçək — bunun üçün $\binom{n-1}{k-1}$ üsul var;
• Əgər $n$ elementi altçoxluğa qətiyyən daxil deyilsə, onda altçoxluğun bütün $k$ elementi ancaq $\{1,\dots,n-1\}$ çoxluğundan seçilməlidir — bunun üçün də $\binom{n-1}{k}$ üsul var.

Bu iki hal bir-biri ilə kəsişmir və bütün altçoxluqları tam əhatə edir; deməli toplama qaydasına görə bu cəm bizə yekun nəticəni verir. Cavab: İsbat olundu

Məsələ 32.

\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^n

eyniliyini ikili sayma metodu ilə isbat edin.

Həll. Fərz edək ki,

n

elementli bir çoxluğun bütün mümkün altçoxluqlarını sayırıq. Birinci sayma metodu: çoxluqdakı hər element üçün müstəqil şəkildə «altçoxluqda var/yox» qərarı veririk — bu, bizə

2^n

nəticəsini verir. İkinci sayma metodu: bütün altçoxluqları element saylarına (ölçüsünə) görə qruplaşdırıb toplayırıq — bu isə

\sum_k\binom{n}{k}

verir. Hər iki halda tamamilə eyni ailəni saydığımız üçün onlar bərabərdir. Cavab: İsbat olundu

Məsələ 33.

k\binom{n}{k}=n\binom{n-1}{k-1}

Komitə-sədr eyniliyini isbat edin və bu eynilikdən istifadə edərək

\displaystyle\sum_{k=0}^{12}k\binom{12}{k}

mürəkkəb cəmini tapın.

Həll. İsbat. Hər hansı bir kollektivdən (komitə, sədr) cütlərini sayırıq: birinci üsul — əvvəlcə

k

nəfərlik komitə, daha sonra onun içindən sədr seçmək —

k\binom{n}{k}

; ikinci üsul — əvvəlcə bütün kollektivdən sədri seçmək, sonra isə yerdə qalan üzvləri seçmək —

n\binom{n-1}{k-1}

.Cəmin hesablanması.

\sum_{k=0}^{12}k\binom{12}{k}=\sum_{k=1}^{12}12\binom{11}{k-1} =12\sum_{j=0}^{11}\binom{11}{j}=12\cdot 2^{11}=24\,576 .

Cavab:

24\,576

Məsələ 34. Vandermonde eyniliyini —

\displaystyle\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}

ikili sayma (double counting) metodu ilə isbat edin.

Həll. Təsəvvür edək ki,

m

oğlan və

n

qızdan ibarət birləşmiş qrupdan

r

nəfərlik komanda seçirik. Bunu birbaşa saydıqda:

\binom{m+n}{r}

alınır. Lakin seçilən komandadakı oğlanların sayını (

k

qəbul etməklə) meyar kimi götürüb hallara ayırsaq:

\binom{m}{k}\binom{n}{r-k}

yaranır (burada

k=0,\dots,r

). Aydındır ki, bu hallar qətiyyən kəsişmir. Nəticələr isə bərabərdir. Cavab: İsbat olundu

Məsələ 35.

\displaystyle\sum_{k=0}^{n}\binom{n}{k}^2=\binom{2n}{n}

olduğunu isbat edin və

n=8

olduqda bu cəmin qiymətini yazın.

Həll. Bunun üçün Vandermonde eyniliyində məxsusi olaraq

m=n

r=n

qəbul edirik:

\binom{2n}{n}=\sum_k\binom{n}{k}\binom{n}{n-k} =\sum_k\binom{n}{k}^2

(bu isə simmetriya xassəsindən irəli gəlir).Bunun müstəqil kombinatorik mənası belədir:

n

oğlan və

n

qızdan ibarət qrupdan

n

nəfərlik komanda seçirik; əgər komandadakı oğlanların sayı

k

olarsa, onda bu cür komandaların sayı

\binom{n}{k}\binom{n}{n-k}=\binom{n}{k}^2

olar.

n=8

olduqda:

\binom{16}{8}=12\,870

. Cavab:

12\,870

Məsələ 36. Hokkey çubuğu eyniliyini isbat edin:

\displaystyle\sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}

. Daha sonra

\binom{5}{5}+\binom{6}{5}+\dots+\binom{12}{5}

cəmini hesablayın.

Həll. İsbat. Sol tərəf bizə heç nə demir, amma sağ tərəf

\{1,\dots,n+1\}

çoxluğundan seçilmiş

r+1

elementli altçoxluqları saydığımızı göstərir — yəni ümumi say

\binom{n+1}{r+1}

-dir. İndi isə həmin ailəni ikinci üsulla sayaq: hər altçoxluğu onun ən böyük elementinə görə hallara ayıraq. Fərz edək ki, ən böyük element

i+1

-dir. O zaman, altçoxluğun yerdə qalan

r

elementi mütləq

\{1,\dots,i\}

çoxluğundan seçilməlidir — bunun üçün

\binom{i}{r}

üsul var. Aydındır ki, bu

i

dəyişəni məntiqən

r

-dən başlayaraq ta

n

-ə qədər dəyişə bilər.Cəmin hesablanması. Düsturda

r=5

n=12

qəbul etsək cəm:

\binom{13}{6}=1716

olar. Cavab:

1716

Məsələ 37.

\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}

Altkomitə eyniliyini kombinatorik isbat edin.

Həll.

n

nəfərdən ibarət kollektivdən

k

nəfərlik bir komitə, ardınca isə həmin komitənin öz içindən

r

nəfərlik xüsusi bir rəhbərlik seçilir — gəlin bu (komitə, rəhbərlik) cütlərini sayaq.Bərabərliyin sol tərəfi: əvvəlcə bütün kollektivdən komitə seçilir (

\binom{n}{k}

), sonra isə o komitənin öz içindən rəhbərlik seçilir (

\binom{k}{r}

).Bərabərliyin sağ tərəfi: əvvəlcə rəhbərliyi birbaşa olaraq bütün

n

nəfərin içindən seçirik (

\binom{n}{r}

), daha sonra isə komitənin yerdə qalan

k-r

sayda üzvünü rəhbərliyə düşməyən digər

n-r

nəfərdən seçirik (

\binom{n-r}{k-r}

). Cavab: İsbat olundu

Məsələ 38. Tutaq ki,

(1+x)^{14}

çoxhədlisinin açılışında ardıcıl gələn hər hansı üç əmsal

1:2:3

nisbətindədir, bu əmsallar özləri hansılardır?

Həll. Fərz edək ki, həmin ardıcıl əmsallar

\binom{14}{k},\binom{14}{k+1},\binom{14}{k+2}

-dir. Bu cür nisbətlərlə işləmək üçün bizə çox faydalı olacaq riyazi münasibət budur:

\frac{\binom{n}{k+1}}{\binom{n}{k}}=\frac{n-k}{k+1}.

Birinci nisbət şərti:

\dfrac{14-k}{k+1}=2 \Rightarrow 14-k=2k+2 \Rightarrow k=4

verir. Gəlin tapdığımız bu qiyməti ikinci şərt üçün də yoxlayaq:

\dfrac{\binom{14}{6}}{\binom{14}{5}}=\dfrac{14-5}{6}=\dfrac{9}{6} =\dfrac{3}{2}

— bəli, tamamilə doğrudur, çünki məsələdə bizdən ardıcıl olaraq

2:3

nisbəti tələb olunurdu.Deməli həqiqətən də

k=4

-dür və axtarılan əmsallar bunlardır:

\binom{14}{4}=1001

\binom{14}{5}=2002

\binom{14}{6}=3003

. Cavab:

1001

2002

3003

Qeyd. Qonşu əmsalların nisbəti — əvəzolunmaz bir alətdir.

\dfrac{\binom{n}{k+1}}{\binom{n}{k}}=\dfrac{n-k}{k+1}

riyazi münasibəti faktorialları tam açmadan əldə edilir və üç mühüm məqsəd üçün çox faydalıdır: (a) o, nisbət tipli məsələləri birbaşa sadə xətti tənliyə çevirir; (b) o, binomial sətrin harada artıb harada azaldığını aydın göstərir; (c) bunun köməyi ilə sətirdəki ən böyük əmsalı tapmaq daha asan olur.

Məsələ 39. Paskal üçbucağının ümumiyyətlə hansı sətrində hər hansı ardıcıl üç element

1:3:5

nisbətində ola bilər?

Həll. Tənlikləri quraq:

\dfrac{n-k}{k+1}=3

və

\dfrac{n-k-1}{k+2}=\dfrac{5}{3}

.Birinci tənlikdən

n-k=3k+3

, yəni

n=4k+3

alırıq. Bunu gətirib ikinci tənlikdə yerinə qoyaq:

\dfrac{4k+3-k-1}{k+2}=\dfrac{3k+2}{k+2}=\dfrac53 \Rightarrow 9k+6=5k+10 \Rightarrow k=1

, buradan da

n=7

tapılır.Yoxlayaq:

\binom{7}{1},\binom{7}{2},\binom{7}{3}=7,21,35

— doğrudan da onlar ardıcıl

1:3:5

nisbətindədir. Cavab:

n=7

Məsələ 40.

\left(x^3+\dfrac{1}{x^2}\right)^{15}

açılışında sabit həddi (yəni

x

-dən asılı olmayan həddi) tapın.

Həll. Ümumi hədd:

T_k=\binom{15}{k}x^{3(15-k)}x^{-2k}=\binom{15}{k}x^{45-5k}

. Sabit hədd üçün qüvvət sıfır olmalıdır:

45-5k=0\Rightarrow k=9

; bu zaman əmsal

\binom{15}{9}=\binom{15}{6}=5005

. Cavab:

5005

Məsələ 41.

(x+2)^{10}

çoxhədlisinin açılışındakı ən böyük əmsal məhz hansı həddə aiddir?

Həll. Ümumi hədd düsturu

T_k=\binom{10}{k}2^k x^{10-k}

şəklindədir, buradakı əmsal isə

a_k=\binom{10}{k}2^k

olur. Əmsalın harada pik (maksimum) nöqtəsinə çatdığını tapmaq üçün ardıcıl qonşu əmsalların nisbətinə baxaq:

\frac{a_{k+1}}{a_k}=\frac{\binom{10}{k+1}}{\binom{10}{k}}\cdot 2 =\frac{10-k}{k+1}\cdot 2 .

Bu nisbət yalnız o zaman

1

-dən böyük olur ki,

\iff 2(10-k)>k+1 \iff 19>3k \iff k\le 6

. Bu o deməkdir ki, açılışdakı əmsallar

k=0,\dots,7

intervalı boyunca dayanmadan artır, sonra isə azalmağa başlayır; maksimum qiymət isə tam olaraq

k=7

olduqda alınır:

a_7=\binom{10}{7}2^7=120\cdot 128=15\,360 ,

yəni bu,

x^3

həddinin əmsalıdır. Cavab:

15\,360

(

x^3

həddi)

Məsələ 42.

\displaystyle\sum_{k=0}^{10}k^2\binom{10}{k}

cəmini kombinatorik hesablayın.

Həll. Riyazi bir hiylə kimi

k^2=k(k-1)+k

ayrılışından istifadə edək. Əgər biz yuxarıda öyrəndiyimiz Komitə-sədr eyniliyini iki dəfə ardıcıl tətbiq etsək, o zaman

k(k-1)\binom{n}{k}=n(n-1)\binom{n-2}{k-2}

bərabərliyi alınır (Bunun kombinatorik mənası: komitə seç, daha sonra isə onun içindən sıralı olaraq iki rəhbər təyin et). Onda alırıq ki,

\sum_k k(k-1)\binom{n}{k}=n(n-1)2^{n-2},\qquad \sum_k k\binom{n}{k}=n2^{n-1},

və deməli:

\sum_k k^2\binom{n}{k}=n(n-1)2^{n-2}+n2^{n-1}=n(n+1)2^{n-2}.

İndi

n=10

qəbul edək:

10\cdot 11\cdot 2^{8}=110\cdot 256=28\,160

. Cavab:

28\,160

Məsələ 43.

\binom{2n}{2}=2\binom{n}{2}+n^2

bərabərliyinin doğruluğunu ikili sayma metodu ilə isbat edin.

Həll. Təsəvvür edin ki,

n

oğlan və

n

qızdan ibarət, cəmi

2n

nəfərlik qrupdan

2

nəfərlik cütlükləri saymaq istəyirik — düsturun sol tərəfi birbaşa bunu ifadə edir.Bunu ikinci üsulla sayaq: seçilən cütlüyün gender tərkibinə görə üç kəsişməyən hala baxaq. Cütlük iki oğlandan ibarətdir:

\binom{n}{2}

; iki qızdan ibarətdir:

\binom{n}{2}

; və nəhayət bir oğlan və bir qızdan ibarətdir:

n\cdot n=n^2

. Toplama qaydası bizə bu halların cəminin düsturun sağ tərəfinə bərabər olduğunu göstərir. Cavab: İsbat olundu

Məsələ 44.

10

nəfərlik işçi kollektivindən müəyyən bir komissiya seçilir və daha sonra o komissiyanın içindən xüsusi olaraq

2

nəfərlik rəhbərlik təyin olunur. Belə (komissiya, rəhbərlik) cütlərinin cəmi sayı neçədir?

Həll. Bizi maraqlandıran axtarılan kəmiyyət əslində

\displaystyle\sum_{k}\binom{10}{k}\binom{k}{2}

-dir. Gəlin Altkomitə eyniliyini tətbiq edək: Bilirik ki,

\binom{10}{k}\binom{k}{2}=\binom{10}{2}\binom{8}{k-2}

. Onda

\sum_k \binom{10}{2}\binom{8}{k-2}=\binom{10}{2}\cdot 2^{8} =45\cdot 256=11\,520 .

Kombinatorik oxunuş (daha qısa yol). Əvvəlcə birbaşa bütün işçilərdən

2

rəhbəri seçirik (

\binom{10}{2}=45

), daha sonra isə yerdə qalan

8

nəfərin hər biri üçün ayrı-ayrılıqda, müstəqil olaraq «komissiyadadır / komissiyada deyil» qərarını veririk (

2^8

). Hasil eynidir. Cavab:

11\,520

Məsələ 45. Paskal üçbucağının ilk

11

sətrində (yəni

n=0

-dan

n=10

-a qədər olan hissəsində) ümumilikdə neçə tək ədəd iştirak edir?

Həll. Bu məsələni həll etmək üçün Paskal üçbucağını

2

modulunda (

1

— tək ədəd,

0

— cüt ədəd qəbul edərək) quraq; qeyd edək ki, Paskal eyniliyi qaydası hətta mod

2

-də də riyazi olaraq keçərlidir:

\begin{array}{l} n=0:\ 1 \quad (1)\\ n=1:\ 1\,1 \quad (2)\\ n=2:\ 1\,0\,1 \quad (2)\\ n=3:\ 1\,1\,1\,1 \quad (4)\\ n=4:\ 1\,0\,0\,0\,1 \quad (2)\\ n=5:\ 1\,1\,0\,0\,1\,1 \quad (4)\\ n=6:\ 1\,0\,1\,0\,1\,0\,1 \quad (4)\\ n=7:\ 1\,1\,1\,1\,1\,1\,1\,1 \quad (8)\\ n=8:\ 1\,0\,0\,0\,0\,0\,0\,0\,1 \quad (2)\\ n=9:\ 1\,1\,0\,0\,0\,0\,0\,0\,1\,1 \quad (4)\\ n=10:\ 1\,0\,1\,0\,0\,0\,0\,0\,1\,0\,1 \quad (4) \end{array}

Tapdığımız tək ədədlərin saylarını toplasaq:

1+2+2+4+2+4+4+8+2+4+4=37

.Qeyd. Ümumiyyətlə,

n

-ci sətirdəki tək ədədlərin sayı həmişə və həmişə

2

-nin hər hansı bir qüvvətidir — daha dəqiq desək, əgər

n

ədədinin ikilik (binar) yazılışındakı vahidlərin (

1

-lərin) sayı

s

olarsa, o sətirdəki tək ədədlərin sayı qanunauyğun olaraq

2^{s}

olur. (Bu riyaziyyatda Lukas (Lucas) teoremi kimi tanınır; lakin burada biz onu yalnız maraqlı bir müşahidə kimi qeyd edirik.) Cavab:

37

Məsələ 46.

\displaystyle\sum_{k=0}^{n-1}\binom{n}{k}\binom{n}{k+1}=\binom{2n}{n-1}

bərabərliyinin doğruluğunu isbat edin və

n=5

halı üçün onun qiymətini tapın.

Həll. Gəlin simmetriya xassəsini işə salaq: bilirik ki,

\binom{n}{k}=\binom{n}{n-k}

, deməli verilmiş cəmi belə yaza bilərik

\sum_{k}\binom{n}{k}\binom{n}{k+1} =\sum_{k}\binom{n}{n-k}\binom{n}{k+1}.

İndi bu yazılış bizə çox tanış gəlir, bu Vandermonde eyniliyinin sağ tərəfidir: orada

m=n

r=n-1

yazsaq

\sum_{j}\binom{n}{j}\binom{n}{n-1-j}=\binom{2n}{n-1}

alarıq — yuxarıdakı cəm sadəcə olaraq

j=n-k

əvəzetməsi ilə məhz eyni nəticəni verir.Kombinatorik mənası.

n

oğlan və

n

qızdan ibarət qrupdan

n-1

nəfərlik komanda seçirik; komandadakı qızların sayını meyar qəbul edərək hallara ayırırıq.

n=5

halı üçün:

\binom{10}{4}=210

. Cavab:

210

Məsələ 47.

\displaystyle\sum_{k=0}^{n}k\binom{n}{k}^2=n\binom{2n-1}{n-1}

eyniliyini isbat edin və

n=4

halı üçün qiymətini hesablayın.

Həll. Gəlin belə bir maraqlı çoxluğu sayaq: tutaq ki,

n

oğlan və

n

qızdan ibarət böyük qrupdan

n

nəfərlik vahid bir komanda seçilir və ardınca isə həmin komandadakı oğlanlardan biri komandaya kapitan təyin olunur.Birinci sayma üsulu. Fərz edək ki, komandada

k

sayda oğlan var: bu halda oğlanları

\binom{n}{k}

cür, qızları isə

\binom{n}{n-k}=\binom{n}{k}

cür seçirik. Oğlanların içindən kapitanı isə

k

fərqli cür seçə bilərik. Bunların yekun cəmi:

\sum_k k\binom{n}{k}^2

olur.İkinci sayma üsulu. Bu dəfə gəlin əvvəlcə kapitanı seçək — o, bütün mövcud

n

oğlandan biri olmalıdır, bunun üçün

n

imkan var. Ardınca yerdə qalan

2n-1

nəfərdən (yəni yerdə qalan

n-1

oğlan və

n

qızdan) komandanın çatışmayan

n-1

üzvünü seçirik:

\binom{2n-1}{n-1}

n=4

olduqda:

4\binom{7}{3}=4\cdot 35=140

. Cavab:

140

Məsələ 48. Əgər

(1+x)^n

çoxhədlisinin açılışında

x^k

və

x^{k+1}

-in əmsalları tamamilə bir-birinə bərabərdirsə, bu halda

n

ilə

k

arasında hansı riyazi əlaqə var?

Həll. Məlum əmsal nisbəti düsturuna əsasən

\dfrac{\binom{n}{k+1}}{\binom{n}{k}}=\dfrac{n-k}{k+1}=1 \Rightarrow n-k=k+1 \Rightarrow n=2k+1

.Bu o deməkdir ki, belə bir bərabərliyin olması üçün

n

mütləq tək ədəd olmalıdır və həmin bərabər olan əmsallar Paskal sətrinin tam olaraq mərkəzində yerləşən iki qonşu ədəddir. Məsələn,

n=7

k=3

olduqda:

\binom{7}{3}=\binom{7}{4}=35

. Cavab:

n=2k+1

Məsələ 49. Sübut edin ki, Paskal üçbucağının hər bir sətrində ədədlər əvvəlcə ciddi şəkildə artır, sonra isə ciddi şəkildə azalmağa başlayır (yəni maksimum qiymət həmişə sətrin ortasındadır).

Həll. Qonşu əmsalların nisbətinə bir daha baxaq:

\dfrac{\binom{n}{k+1}}{\binom{n}{k}}=\dfrac{n-k}{k+1}

. Bu kəsrin qiyməti yalnız o zaman

1

-dən böyükdür ki,

\iff n-k>k+1 \iff k<\dfrac{n-1}{2}

.Deməli o vaxta qədər ki,

k<\frac{n-1}{2}

ödənilir, əmsallar ardıcıl olaraq artır, və

k>\frac{n-1}{2}

olduqdan sonra isə əmsallar dayanmadan azalır. Əgər

n

cüt olarsa bu zaman maksimum yeganə bir nöqtədə olur və o da

k=\frac n2

-də alınır; lakin

n

tək olarsa, o zaman tam ortada iki bərabər maksimum yaranır:

k=\frac{n-1}{2}

və

k=\frac{n+1}{2}

. Cavab: İsbat olundu

9Ev tapşırıqlarıA hissəsi — sadə məsələlər

Paskal üçbucağının $n=7$ nömrəli sətrini yazın.
$\binom{11}{4}+\binom{11}{5}$ cəmini hesablamanı uzatmadan Paskal qaydası ilə sadələşdirib hesablayın.
$\binom{18}{16}$ neçədir?
Əgər $\binom{n}{2}=78$ olarsa, $n$ neçədir?
Əgər $\binom{n}{4}=\binom{n}{6}$ olarsa, $n$ neçədir?
$(x+y)^7$ çoxhədlisinin açılışında $x^3y^4$ həddinin əmsalı neçədir?
$(1+x)^9$ çoxhədlisinin açılışında $x^4$ -ün əmsalı nədir?
$(x-2)^5$ çoxhədlisinin açılışında $x^2$ -nin əmsalı neçədir?
$(3x+1)^4$ çoxhədlisinin açılışında $x^3$ -ün əmsalı neçədir?
$(2x-1)^6$ çoxhədlisinin açılışında $x^4$ -ün əmsalı nədir?
$\displaystyle\sum_{k=0}^{12}\binom{12}{k}$ cəmi neçədir?
$\displaystyle\sum_{k=0}^{12}(-1)^k\binom{12}{k}$ cəmi nəyə bərabərdir?
$\binom{9}{0}+\binom{9}{2}+\binom{9}{4}+\binom{9}{6}+\binom{9}{8}$ cəmini tapın.
$\left(x+\dfrac1x\right)^{10}$ çoxhədlisinin açılışında sabit (sərbəst) həddi tapın.
$\left(x^2+\dfrac1x\right)^{6}$ çoxhədlisinin açılışında sabit hədd nədir?
$1+2+\dots+15$ ədədi cəmini binomial əmsallar vasitəsilə ifadə edib hesablayın.
$\binom{3}{3}+\binom{4}{3}+\dots+\binom{9}{3}$ cəmini tapın.
$(a+b)^{12}$ açılışında tam ortada dayanan həddin əmsalı neçədir?
$(x+y)^{15}$ çoxhədlisinin açılışında ümumilikdə neçə hədd iştirak edir?
$\binom{10}{4}$ -ü düsturla hesablayın.
$12$ nəfərdən (a) istənilən sayda üzvü olan, (b) boş qrup istisna olmaqla (boş olmayan) neçə müxtəlif komissiya qurmaq mümkündür?
Bəs həmin $12$ nəfərdən yalnız cüt sayda üzvü olan neçə komissiya var?
$(1+x)^n$ açılışındakı bütün əmsalların cəmi $1024$ -ə bərabərdirsə, bu halda $n$ neçədir?
$(2+x)^5$ çoxhədlisinin açılışındakı bütün əmsalların yekun cəmi neçə edir?
$(3x-2y)^4$ açılışında $x^2y^2$ həddinin əmsalı nədir?
Paskal eyniliyindən istifadə edərək $\binom{9}{4}$ -ü hesablayın.
$\binom{100}{98}$ neçəyə bərabərdir?
$(x+2)^7$ açılışında $x^5$ -in əmsalı nədir?
$\displaystyle\sum_{k=0}^{7}\binom{7}{k}2^k$ cəmini tapın.
$\displaystyle\sum_{k=0}^{6}\binom{6}{k}(-2)^k$ cəmini hesablayın.
Paskal üçbucağının $n=15$ sətrində iştirak edən ən böyük ədəd hansıdır?
$(x^3+x)^5$ çoxhədlisinin açılışında $x^{11}$ -in əmsalı nə olacaq?
$(1+x)^{20}$ açılışında $x^{18}$ -in əmsalı neçədir?
$\binom{n}{1}+\binom{n}{n-1}=20$ olarsa, $n$ neçəyə bərabərdir?
$\left(x-\dfrac1x\right)^{6}$ açılışında sabit (sərbəst) həddi tapın.
$(1+x)^{10}$ çoxhədlisinin açılışında $x^3$ və $x^7$ -nin əmsallarını müqayisə edin və alınan nəticənin riyazi səbəbini izah edin.

B hissəsi — orta və çətin məsələlər

$\binom{n}{k}=\binom{n}{n-k}$ eyniliyini yalnız kombinatorik sayma metodu ilə (heç bir cəbri düsturdan istifadə etmədən) isbat edin.
İsbat edin ki: $\displaystyle\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0$ ( $n\ge 1$ olduqda). Məsələni Bijeksiya (Cütləşdirmə) üsulundan istifadə edərək həll edin.
İsbat edin ki, $n$ elementli hər hansı bir çoxluğun cüt ölçülü altçoxluqlarının sayı mütləq $2^{n-1}$ -ə bərabərdir.
$\displaystyle\sum_{k=0}^{14}k\binom{14}{k}$ cəmini tapın.
$\displaystyle\sum_{k=0}^{7}\binom{7}{k}^2$ cəmini tapın.
$\displaystyle\sum_{k=0}^{3}\binom{6}{k}\binom{8}{3-k}$ cəmini Vandermonde eyniliyi vasitəsilə hesablayın.
$\binom{4}{4}+\binom{5}{4}+\dots+\binom{11}{4}$ cəmini tapın.
$\left(x^2-\dfrac{1}{x}\right)^{12}$ açılışında sabit həddi tapın.
$\left(x+\dfrac{1}{x^2}\right)^{12}$ açılışında sabit hədd nədir?
$(x+3)^{12}$ açılışındakı ən böyük əmsal məhz hansı həddə aiddir?
$\displaystyle\sum_{k=0}^{12}k^2\binom{12}{k}$ cəmini tapın.
Əgər $(1+x)^n$ açılışında ardıcıl olaraq gələn üç əmsal $2:3:4$ nisbətindədirsə, o zaman $n$ neçədir?
Əgər $(1+x)^n$ açılışında ardıcıl gələn üç əmsal $2:4:5$ nisbətindədirsə, $n$ neçədir?
İsbat edin: $\binom{n}{k}\binom{k}{2}=\binom{n}{2}\binom{n-2}{k-2}$ .
$15$ nəfərlik işçi kollektivindən müəyyən bir komissiya seçilir və onun da öz içindən $3$ nəfərlik rəhbərlik təyin olunur. Belə yarana biləcək (komissiya, rəhbərlik) cütlərinin sayı neçədir?
İsbat edin ki: $\binom{2n}{n}$ kəmiyyəti həmişə cüt ədəddir ( $n\ge 1$ ).
Paskal üçbucağının ilk $8$ sətrində (yəni $n=0,\dots,7$ aralığında) ümumilikdə neçə tək ədəd mövcuddur?
$\displaystyle\sum_{k=0}^{10}\binom{10}{k}3^k$ cəmini tapın.
$(1+x)^{2n}$ açılışında $x^n$ -in əmsalının məhz $\binom{2n}{n}$ olduğunu $(1+x)^n(1+x)^n$ hasilindən istifadə etməklə çıxarın və bunun köməyi ilə $\sum_k\binom{n}{k}^2=\binom{2n}{n}$ eyniliyini əldə edin.
$(2x-3y)^6$ açılışında $x^4y^2$ həddinin əmsalı nədir?
İsbat edin: $\displaystyle\sum_{k=0}^{n}\binom{n}{k}\binom{n}{k+1} =\binom{2n}{n-1}$ və $n=6$ olduqda bu cəmin qiymətini yazın.
$\binom{n}{k}$ və $\binom{n}{k+1}$ əmsallarının nisbətinin məhz $\dfrac{n-k}{k+1}$ olduğunu isbat edin.
İsbat edin ki: $\displaystyle\sum_{k=0}^{n}k\binom{n}{k}^2 =n\binom{2n-1}{n-1}$ ; və $n=5$ halı üçün onun qiymətini tapın.
$\binom{3n}{3}$ ifadəsini $\binom{n}{3}$ , $\binom{n}{2}$ və $n$ dəyişənləri vasitəsilə cəbri olaraq ifadə edin (İpucu: kombinatorik olaraq $3n$ nəfəri üç bərabər qrupa bölməyə çalışın).
$(1+x)^{16}$ açılışında $x^k$ və $x^{k+1}$ -in əmsalları tam bərabərdirsə belə bir $k$ indeksi varmı? Cavabınızı riyazi olaraq əsaslandırın.
$8$ oğlan və $6$ qızdan ibarət qrupdan $5$ nəfərlik komanda seçilməlidir. Vandermonde eyniliyindən istifadə edərək belə komandaların ümumi sayının doğrudan da $\binom{14}{5}$ olduğunu yoxlayın (bunun üçün eyniliyin hər iki tərəfini hesablayın).
İsbat edin ki: $\binom{n}{0}^2-\binom{n}{1}^2+\binom{n}{2}^2-\dots$ şəklindəki işarəli kvadratlar cəmi, $n$ tək ədəd olduqda həmişə sıfıra bərabərdir.
$\left(\sqrt{x}+\dfrac{1}{x}\right)^{9}$ açılışında sabit hədd varmı? Əgər varsa onu tapın.
$(1+x)^{n}$ açılışındakı bütün əmsalların ən böyüyü $\binom{n}{5}$ olarsa, bu halda $n$ hansı tam qiymətləri ala bilər?
İsbat edin ki, $\displaystyle\sum_{k=0}^{n}\binom{n}{k} \binom{n}{n-k}=\binom{2n}{n}$ eyniliyi əslində mahiyyətcə $\sum_k\binom{n}{k}^2=\binom{2n}{n}$ eyniliyi ilə tamamilə eynidir və hər ikisinin kombinatorik mənasını ətraflı izah edin.

10Ev tapşırıqlarının cavabları

Qeyd. Necə istifadə etməli. İsbatı tələb olunan tapşırıqlarda cavab yerinə «İsbat olundu» yazılıb və yalnız kombinatorik açar ideya göstərilib — yəni məsələdə hansı çoxluğu sayacağınız və onları hansı əlamətə görə hallara ayıracağınız qeyd olunub. İsbatın yerdə qalan hissəsini mütləq özünüz yazın: kombinatorik isbatın əsl dəyəri məhz onun sizin tərəfinizdən səliqəli və məntiqli yazılışındadır.

A hissəsi1.

1,7,21,35,35,21,7,1

\binom{12}{5}=792

153

13

10

35

126

-80

108

10.

240

11.

4096

12.

0

13.

256

14.

252

15.

15

16.

\binom{16}{2}=120

17.

\binom{10}{4}=210

18.

924

19.

16

20.

210

21. (a)

4096

, (b)

4095

22.

2048

23.

10

24.

243

25.

216

26.

126

27.

4950

28.

84

29.

2187

30.

1

31.

\binom{15}{7}=6435

32.

10

33.

190

34.

10

35.

-20

36. hər ikisi

120

-dir; riyazi səbəb simmetriya xassəsidir:

\binom{10}{3}=\binom{10}{7}

B hissəsi — cavablar və qısa ideyalar

1. İsbat olundu. Hər bir $k$ elementli altçoxluğa onun tamamlayıcısını (yerdə qalan elementlərini) uyğunlaşdırın — bu, qarşılıqlı birmənalı uyğunluq (bijeksiya) yaradır.
2. İsbat olundu. «Əgər $1$ elementi altçoxluqda varsa onu çıxar, yoxdursa ona əlavə et» əməliyyatı bütün cüt ölçülü altçoxluqları tək ölçülülərlə qüsursuz şəkildə cütləşdirir.
3. $2^{n-1}$ . Əvvəlki tapşırığın nəticəsinə görə: cüt və tək ölçülü altçoxluqların sayı tamamilə bərabərdir, onların ümumi cəmi isə $2^n$ -dir.
4. $114\,688$ . Komitə-sədr eyniliyinə əsasən $14\cdot 2^{13}$ .
5. $3432$ . Vandermonde eyniliyinə əsasən $\binom{14}{7}$ .
6. $364$ . Eyni qayda ilə $\binom{14}{3}$ .
7. $792$ . Hokkey çubuğu eyniliyi: $\binom{12}{5}$ .
8. $495$ . $T_k=\binom{12}{k}(-1)^k x^{24-3k}$ ; $k=8$ ; $(-1)^8\binom{12}{8}=495$ .
9. $495$ . $x^{12-3k}$ ; $k=4$ ; $\binom{12}{4}$ .
10. $4\,330\,260$ — $x^3$ həddi. $\dfrac{a_{k+1}}{a_k}=\dfrac{3(12-k)}{k+1}>1\iff k\le 8$ , deməli əmsallar $k=9$ -a qədər artır, yəni maksimum $k=9$ -dadır: $\binom{12}{9}3^9$ .
11. $159\,744$ . Cəm $n(n+1)2^{n-2}=12\cdot 13\cdot 2^{10}$ edir.
12. $n=34$ ( $k=13$ ). $\dfrac{n-k}{k+1}=\dfrac32$ və $\dfrac{n-k-1}{k+2}=\dfrac43$ tənliklər sistemini qurun və həll edin.
13. $n=8$ ( $k=2$ ). Açılışdakı həmin əmsallar $28,56,70$ -dir.
14. İsbat olundu. Altkomitə eyniliyində $r=2$ olduqda yaranan haldır; kombinatorik oxunuşu: böyük komitəni seç, sonra isə onun içindən iki nəfərlik kiçik rəhbərlik seç.
15. $1\,863\,680$ . $\binom{15}{3}\cdot 2^{12}=455\cdot 4096$ (daha qısa yol: əvvəlcə $3$ rəhbəri birbaşa seç, yerdə qalan $12$ nəfərin hər biri üçün isə fərdi «var/yox» qərarı ver).
16. İsbat olundu. $\binom{2n}{n}=2\binom{2n-1}{n-1}$ (Bunu Komitə-sədr eyniliyindən, və ya birbaşa Paskal eyniliyi ilə əldə etmək olar: $\binom{2n}{n}=\binom{2n-1}{n-1}+\binom{2n-1}{n}$ və bu iki hədd simmetriyaya görə bir-birinə onsuz da bərabərdir, yəni cüt ədəddir).
17. $27$ . Hər sətirdəki tək ədədlərin sayı belə dəyişir: $1,2,2,4,2,4,4,8$ . Cəmi $27$ .
18. $1\,048\,576$ . Dəyişənləri əvəzetməklə $(1+3)^{10}=4^{10}$ .
19. İsbat olundu. Aydındır ki, $(1+x)^n(1+x)^n=(1+x)^{2n}$ ; sol tərəfdə vurub açdıqda $x^n$ -in əmsalı $\sum_k\binom{n}{k}\binom{n}{n-k}=\sum_k\binom{n}{k}^2$ yaranır, sağ tərəfdə isə birbaşa $\binom{2n}{n}$ alınır. Bunlar eynidir.
20. $2160$ . $\binom{6}{2}2^4(-3)^2=15\cdot 16\cdot 9$ .
21. İsbat olundu; $n=6$ üçün cavab $\binom{12}{5}=792$ . Məsələni simmetriya xassəsi ilə cəmi Vandermonde formasına (standartına) salaraq isbat edin.
22. İsbat olundu. Faktorial açılışı ilə yoxlamaq çox asandır: $\dfrac{\binom{n}{k+1}}{\binom{n}{k}} =\dfrac{n!\,k!\,(n-k)!}{(k+1)!\,(n-k-1)!\,n!}=\dfrac{n-k}{k+1}$ .
23. İsbat olundu; $n=5$ üçün qiymət $5\binom{9}{4}=630$ -dur. Məsələnin məntiqi: $n$ oğlan və $n$ qızdan ümumilikdə $n$ nəfərlik bir komanda seçin və məhz oğlanlardan birini kapitan təyin edin; bu prosesi iki müxtəlif yolla sayın.
24. $\binom{3n}{3}=3\binom{n}{3}+6n\binom{n}{2}+n^3$ . $3n$ nəfər insanı üç fərqli və bərabər qrupa bölməyə görə hallara ayırın: 1) seçilənlərin hamısı bircə qrupdan ola bilər, 2) seçilənlərin ikisi bir qrupdan, biri digərindən ola bilər, 3) üçü də tamamilə üç fərqli (ayrı) qrupdan ola bilər.
25. Belə bir $k$ tam ədədi yoxdur. Bərabərliyin ödənməsi riyazi olaraq $n=2k+1$ tələb edir, bu isə o deməkdir ki, $n$ mütləq tək ədəd olmalıdır; lakin məsələdəki $16$ cüt ədəddir.
26. Hər iki tərəfin hesabı $2002$ verir. $\sum_k\binom{8}{k}\binom{6}{5-k}=\binom{14}{5}=2002$ .
27. İsbat olundu. Cəmdəki simmetrik $k$ ilə $n-k$ hədlərini cütləşdirin: Bilirik ki, $\binom{n}{k}^2=\binom{n}{n-k}^2$ -dir, lakin $n$ tək ədəd olduqda qarşıdakı $(-1)^k$ və $(-1)^{n-k}$ işarələri bir-birinin tam əksidir (biri müsbətdirsə, digəri mütləq mənfidir), buna görə də cəmdəki hədlər qarşılıqlı olaraq bir-birini yox edir (sıfırlayır).
28. Bəli, var: cavab $84$ -dür. $T_k=\binom{9}{k}x^{(9-3k)/2}$ ; sıfıra bərabərləşdirsək $9-3k=0 \Rightarrow k=3$ ; Deməli $\binom{9}{3}=84$ .
29. Yalnız $n\in\{9,10,11\}$ ola bilər. Əgər $n$ cütdürsə əmsalın maksimumu yalnız tam mərkəzdə $k=n/2$ -də olur (yəni $n=10$ olduqda); lakin əgər $n$ təkdirsə, bu zaman mərkəzdə yan-yana iki eyni maksimum olur — $k=\frac{n-1}{2}$ ( $n=11$ üçün ödəyir) və $k=\frac{n+1}{2}$ ( $n=9$ üçün ödəyir).
30. İsbat olundu. Simmetriya xassəsinə görə həmişə $\binom{n}{n-k}=\binom{n}{k}$ olur, deməli iki cəm vizual olaraq fərqli görünsə də, riyazi olaraq hərfbəhərf eynidir. Onun kombinatorik mənası belədir: cəmi $n$ oğlan və $n$ qızdan ibarət birləşmiş qrupdan $n$ nəfərlik komanda seçmək $\binom{2n}{n}$ müxtəlif cürdür; lakin komandadakı qızların (və ya oğlanların) sayını bir meyar kimi qəbul edib hallara ayırsaq, həmin cəm $\sum_k\binom{n}{k}^2$ şəklinə düşür. Nəticə eynidir.