İkili sayma və biyeksiya

İsbat. $A$ çoxluğunun elementlərini $a_1, a_2, \dots, a_m$ kimi sıralayaq. Onda $f(a_1), f(a_2), \dots, f(a_m)$ elementləri (a) şərtinə görə cüt-cüt fərqlidir, deməli $B$-də ən azı $m$ element var: $|B| \ge |A|$. (b) şərtinə görə isə $B$-nin hər elementi bu siyahıda iştirak edir, deməli $|B| \le m$. Hər iki bərabərsizlikdən $|A| = |B|$ alınır. ■

İsbat. Hər bir həlli aşağıdakı kimi bir sətrə çevirək: əvvəlcə $x_1$ ədəd ulduz $\star$, sonra bir arakəsmə $\mid$, sonra $x_2$ ədəd ulduz, yenə arakəsmə və s. Məsələn $k=4$, $n=7$ və $(x_1,x_2,x_3,x_4)=(2,0,4,1)$ həlli üçün

$$\star\star \mid\; \mid \star\star\star\star \mid \star$$

sətri alınır.Sətirdə həmişə $n$ ulduz və $k-1$ arakəsmə, yəni cəmi $n+k-1$ simvol var. Tərs uyğunluq da aşkardır: verilmiş belə bir sətirdə arakəsmələr sətri $k$ hissəyə bölür və hər hissədəki ulduzların sayı bizə $x_i$-ləri qaytarır. Deməli, həllərlə sətirlər arasında biyeksiya mövcuddur.Belə sətirlərin sayını tapmağı isə bilirik: $n+k-1$ mövqedən arakəsmələrin duracağı $k-1$ mövqeni seçmək kifayətdir, qalan mövqelər avtomatik ulduz olur. Bu isə $\binom{n+k-1}{k-1}$ üsulla mümkündür. ■

İsbat. İki isbat verək — hər ikisi faydalıdır.(1) Dəyişənin əvəz edilməsi. $y_i = x_i - 1$ qəbul edək. Onda $y_i \ge 0$ və $y_1 + \dots + y_k = n-k$ alarıq. Əsas formaya görə həllərin sayı $\binom{(n-k)+k-1}{k-1} = \binom{n-1}{k-1}$-dir.(2) Birbaşa biyeksiya. Bir sıraya düzülmüş $n$ ulduz arasındakı $n-1$ boşluqdan $k-1$-ni seçib oraya arakəsmə yerləşdirək. Hər boşluğa ən çoxu bir arakəsmə düşdüyü üçün heç bir hissə boş qalmır — bu isə məhz $x_i \ge 1$ şərtidir. Deməli, cavab $\binom{n-1}{k-1}$. ■

İsbat. Hər bir yol addımların ardıcıllığı ilə tam təyin olunur. Sona çatmaq üçün dəqiq $m$ sağa və $n$ yuxarı addım atmalıyıq (nə çox, nə az), deməli, hər yola uzunluğu $m+n$ olan, tərkibində $m$ ədəd $S$ və $n$ ədəd $Y$ hərfi olan bir söz uyğun gəlir. Tərsinə, belə hər bir söz tam olaraq bir yol təyin edir. Sözlərin sayı isə $m+n$ mövqedən $S$-lərin duracağı $m$ mövqeni seçmək, yəni $\binom{m+n}{m}$ qədərdir.■

İsbat. Bütün yolların sayı $\binom{2n}{n}$-dir. «Pis» yolları — yəni hansısa anda $y = x+1$ xəttinə toxunanları — sayaq. Belə bir yolda $y=x+1$ xəttinə ilk toxunma anını tapaq və yolun həmin andan sonrakı hissəsini $y=x+1$ xəttinə nəzərən simmetrik əks etdirək (sağa addımlar yuxarı, yuxarı addımlar sağa çevrilir). Sonluq $(n,n)$ nöqtəsi bu inikasda $(n-1,n+1)$ nöqtəsinə keçir.Bu qayda tərsinə də işləyir: $(0,0)$-dan $(n-1,n+1)$-ə gedən istənilən yol mütləq $y=x+1$ xəttini kəsir (çünki sonluqda $y > x$-dir) və ilk toxunmadan sonrakı hissəsini əks etdirsək, $(n,n)$-ə gedən bir «pis» yol alarıq. Deməli, pis yollarla $(0,0) \to (n-1,n+1)$ yolları arasında biyeksiya var; sonuncuların sayı isə $\binom{2n}{n-1}$-dir. Nəticə:

$$C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1}\binom{2n}{n}.$$

■

Həll. $x_1+x_2+x_3+x_4=10$, $x_i \ge 0$. Cavab $\binom{13}{3}$. Cavab: $286$□

Həll. $\binom{10-1}{4-1} = \binom{9}{3}$. Cavab: $84$□

Həll. $\binom{15+3-1}{2} = \binom{17}{2}$. Cavab: $136$□

Həll. $\binom{14}{2}$. Cavab: $91$□

Həll. $\binom{23}{3}$. Cavab: $1771$□

Həll. Cəmi $7$ addımdan $3$-ü sağadır: $\binom{7}{3}$. Cavab: $35$□

Həll. $\binom{10}{5}$. Cavab: $252$□

Həll. $y_i = x_i-2$: $y_1+y_2+y_3 = 2$, $y_i \ge 0$, yəni $\binom{4}{2}$. Cavab: $6$□

Həll. $y_i = x_i-3$: cəm $20-15 = 5$, $\binom{5+4}{4} = \binom{9}{4}$. Cavab: $126$□

Həll. Əlavə (süni) dəyişən $t = 10-(x+y+z) \ge 0$ daxil edirik: $x+y+z+t = 10$, cavab $\binom{13}{3}$. Cavab: $286$□

Həll. Hər altçoxluğa uzunluğu $10$ olan $0/1$ sətri uyğun gəlir və bu uyğunluq qarşılıqlı birqiymətlidir: $2^{10}$. Cavab: $1024$□

Həll. $\binom{10}{3} = 120$ və $\binom{10}{7} = 120$. Səbəb: tamamlayıcı çoxluğa keçid biyeksiyadır. Cavab: $120$; saylar bərabərdir□

Həll. $\binom{5+2}{2} = \binom{7}{2}$. Cavab: $21$□

Həll. İkili sayma: $\sum d_v = 10\cdot 3 = 30 = 2E$, deməli $E = 15$. Cavab: $15$□

Həll. Görüşmə (əl sıxma) lemması: $2E = 30$. Cavab: $15$□

Həll. Hər cütə bir oyun: $\binom{6}{2} = 15$. Hər oyunun bir qalibi var, deməli qalibiyyətlərin cəmi də $15$-dir. Cavab: $15$ və $15$□

Həll. İnsidentlik cütlərini iki cür sayaq: $30 \cdot 4 = 120 = 10 \cdot d$, deməli $d = 12$. Cavab: $12$□

Həll. $15\cdot 4 = 60 = 12\cdot m \Rightarrow m = 5$. Cavab: $5$□

Həll. $\binom{7}{2}$. Cavab: $21$□

Həll. Biyeksiya: hər $3$ elementli altçoxluğu yalnız bir üsulla artan sıraya düzmək olar, deməli cavab $\binom{9}{3}$. Cavab: $84$□

Həll. $\binom{4+3}{3} = \binom{7}{3}$. Cavab: $35$□

Həll. Təkrarlı kombinasiya: $\binom{10+2}{2} = \binom{12}{2}$. Cavab: $66$□

Həll. $\binom{8+4}{4} = \binom{12}{4}$. Cavab: $495$□

Həll. $\binom{8}{4}$. Cavab: $70$□

Həll. $\binom{8}{3}$. Cavab: $56$□

Həll. Yolu iki hissəyə bölürük: $\binom{4}{2}\cdot\binom{4}{2} = 6\cdot 6$. Cavab: $36$□

Həll. Birbaşa: $\binom{6}{2} = 15$. İkili sayma: hər nəfər $5$ cütdə iştirak edir, cəmi $6\cdot 5 = 30$; lakin hər cüt iki dəfə sayıldı, deməli $15$. Cavab: $15$□

Həll. Hər təpədən $7$ diaqonal çıxır, cəmi $10\cdot 7 = 70$; hər diaqonal iki dəfə sayıldı: $35$. (Eyni cavab: $\binom{10}{2} - 10 = 45-10 = 35$.) Cavab: $35$□

Həll. $S \mapsto S \bigtriangleup \{1\}$ (yəni $1$ obyekti varsa çıxarmaq, yoxsa əlavə etmək) uyğunluğu özü-özünün tərsinə bərabərdir və element sayının cütlüyünü dəyişir. Deməli biyeksiyadır və hər iki sayın $2^{n-1}$ olduğu alınır. Cavab: İsbat olundu□

Həll. $y_1 = x_1-2$, $y_2 = x_2-1$, $y_3 = x_3-1$: cəm $8-4 = 4$, cavab $\binom{4+2}{2} = \binom{6}{2}$. Cavab: $15$□

Həll. $\binom{11}{2}$. Cavab: $55$□

Həll. $b_i = a_i-(i-1)$ sıxlaşdırması ilə cavab $\binom{20-3+1}{3} = \binom{18}{3}$. Cavab: $816$□

Həll. Biyeksiya: düzbucaqlı $9$ üfüqi xəttdən $2$-nin və $9$ şaquli xəttdən $2$-nin seçilməsi ilə tam təyin olunur: $\binom{9}{2}^2 = 36^2$. Cavab: $1296$□

Həll. Xeyr: Görüşmə (əl sıxma) lemmasına görə bu cəm $2E$-yə bərabər, yəni cüt olmalıdır. $27$ isə tək ədəddir. Cavab: Mümkün deyil□

Həll. Hər paylanmaya $n$ ulduz və $k-1$ arakəsmədən ibarət sətri uyğunlaşdırırıq ($i$-ci qutudakı obyektlərin sayı $i$-ci arakəsmə qrupundakı ulduzların sayıdır). Tərs qayda: sətirdəki arakəsmələr onu $k$ hissəyə bölür və hər hissədəki ulduz sayı qutunun məzmununu bərpa edir. Deməli biyeksiya var. Uzunluğu $n+k-1$ olan sətirdə arakəsmələrin mövqelərini seçmək $\binom{n+k-1}{k-1}$ üsulla mümkündür. Cavab: İsbat olundu□

Həll. Bütün həllər: $\binom{23}{3} = 1771$. $x_1 \ge 6$ olanlar: $y_1 = x_1-6$ qəbul edərək cəmi $14$ alırıq — $\binom{17}{3} = 680$. Fərq: $1771-680$. Cavab: $1091$□

Həll. Sərhədsiz: $\binom{22}{2} = 231$. Bir dəyişənin $\ge 11$ olması: $\binom{11}{2} = 55$, üç dəyişən üçün $165$. İki dəyişənin eyni anda $\ge 11$ olması mümkün deyil ($22 > 20$). Cavab $231-165$. Cavab: $66$□