Бигзор маҷмӯи иборат аз n элемент дода шудааст. Ҳар як зермаҷмӯи ин маҷмӯъ, ки аз k элемент иборат аст, пайвасткунӣ аз n элемент k-тогӣ номида мешавад. Пайвасткунӣ бо ҳарфи C-и лотинӣ ишора карда мешавад.
Бе такроршавӣ: $$C_n^k=\frac{n!}{(n-k)!\cdot k!}.$$ Бо такроршавӣ: $$\overline{C}_n^k=C_{n+k-1}^k=\frac{(n+k-1)!}{(n-1)!\cdot k!}$$
\(\textbf{Ин формулаҳоро исбот мекунем:}\)
$$C_n^k = \frac{A_n^k}{k!}=\frac{n!}{k!\cdot(n-k)!}$$
Инро исбот мекунем:
Бигзор
\(A =\{\)а, б, в, г, ғ, ..., э,ю,я\(\}, |A|=35\)
Аз маҷмӯи A зермаҷмӯи, ки аз 5 элемент иборат аст, интихоб менамоем, бигзор ин зермаҷмӯи
\(B =\{\)к, и, т, о, б\(\}, |B|=5\)
аст. Миқдори ҳамаи зермаҷмӯи батартибовардашудаи ин маҷмӯъ, ки аз \(5\) элемент иборат аст ба \(\frac{35!}{30!}\) баробар аст.
Лекин ин зермаҷмӯҳо чунин шуда метавонанд.
1. \(\{к,и,т,о,б\}\)
2. \(\{и,к,т,о,б\}\)
3. \(\{и,к,о,т,б\}\)
...
Аз рӯи пайвасткунӣ ҳамаи ин як зермаҷмӯъ мебошад. Миқдори ин зермаҷмӯҳоро аз ҷойивазкунӣ ёфта мешавад, ин ба \(5!\) баробар аст. Яъне пайвасткунӣ аз \(35\) элемент \(5\)-тогӣ ба \(\frac{35!}{30!\cdot 5!}\) баробар аст.
Бигзор
\(A =\{a_1,a_2,a_3,...,a_n\}, |A|=n\)
Аз маҷмӯи A зермаҷмӯи, ки аз k элемент иборат аст, интихоб менамоем, бигзор ин зермаҷмӯи
\(B =\{b_1,b_2,...b_k\}, |B|=k\)
аст. Миқдори ҳамаи зермаҷмӯи батартибовардашудаи ин маҷмӯъ, ки аз \(k\) элемент иборат аст ба \(\frac{n!}{(n-k)!}\) баробар аст.
Лекин ин зермаҷмӯҳо чунин шуда метавонанд.
1. \(\{b_1,b_2,...b_k\}\)
2. \(\{b_2,b_1,...b_k\}\)
3. \(\{b_k,b_2,...b_1\}\)
...
Аз рӯи пайвасткунӣ ҳамаи ин як зермаҷмӯъ мебошад. Миқдори ин зермаҷмӯҳоро аз ҷойивазкунӣ ёфта мешавад, ин ба \(k!\) баробар аст. Яъне пайвасткунӣ аз \(n\) элемент \(k\)-тогӣ ба \(\frac{n!}{(n-k)!\cdot k!}\) баробар аст.
Яъне формулаи пайвасткунӣ бе такроршавӣ исбот шуд.
$$\overline{C}_n^k=C_{n+k-1}^k$$
Инро исбот мекунем:
Бигзор
\(A =\{\)а, б, в, г, ғ, ..., э,ю,я\(\}, |A|=35\)
Аз маҷмӯи A зермаҷмӯи, ки аз 6 элемент иборат аст, интихоб менамоем, бигзор ин зермаҷмӯи
\(B =\{\)м, а, к, т, а, б\(\}, |B|=6\)
аст.
Миқдори ҳар як элементи маҷмӯи Aро ҳисоб мекунем:
а - 2, б - 1, в - 0,..., к - 1, қ - 0, л - 0, м-1, ..., с - 0, т - 1, ... , э - 0, ю - 0, я - 0
Акнун миқдори ҳар як элементҳоро бо 1 иваз мекунему, пас аз ҳар як элемент 0 мегузорем:
$$11010...01001...0010...0010...0$$
а-2то, яъне 2то 1 менависем, пас аз он 0 менависем.
б-1то, яъне 1то 1 менависем, пас аз он 0 менависем.
в-0то, яъне наменависем, лекин 0 менависем.
...
к-1то, яъне 1то 1 менависем, пас аз он 0 менависем.
қ-0то, яъне наменависем, лекин 0 менависем.
л-0то, яъне наменависем, лекин 0 менависем.
м-1то, яъне 1то 1 менависем, пас аз он 0 менависем.
...
т-1то, яъне 1то 1 менависем, пас аз он 0 менависем.
...
ю-0то, яъне наменависем, лекин 0 менависем.
я-ҳеҷ чизе наменависем.
Ҳамагӣ \(35+6-1=40\) элемент ҳосил шуд. Аз ин элементҳо мо бояд 6тоашро интихоб намоем, яъне \(\overline{C}_{35}^6=C_{40}^6=C_{35+6-1}^6\)
Бигзор
\(A =\{a_1,a_2,\ldots,a_n\}, |A|=n\)
Аз маҷмӯи A зермаҷмӯи, ки аз k элемент иборат аст, интихоб менамоем, бигзор ин зермаҷмӯи
\(B =\{b_1,\ldots,b_k\}, |B|=k\)
аст.
Миқдори ҳар як элементи маҷмӯи Aро ҳисоб мекунем:
\(a_1\) - \(x_1\),\(a_2\) - \(x_2\),\(a_3\) - \(x_3\), ..., \(a_n\) - \(x_n\)
Акнун миқдори ҳар як элементҳоро бо 1 иваз мекунему, пас аз ҳар як элемент 0 мегузорем:
$$1...101...10...01...10...01...1$$
\(a_1\) - \(x_1\) то, яъне \(x_1\) то 1 менависем, пас аз он 0 менависем.
\(a_2\) - \(x_2\) то, яъне \(x_2\) то 1 менависем, пас аз он 0 менависем.
\(a_3\) - \(x_3\) то, яъне \(x_3\) то 1 менависем, пас аз он 0 менависем.
\(a_4\) - \(x_4\) то, яъне \(x_4\) то 1 менависем, пас аз он 0 менависем.
\(a_5\) - \(x_5\) то, яъне \(x_5\) то 1 менависем, пас аз он 0 менависем.
\(a_6\) - \(x_6\) то, яъне \(x_6\) то 1 менависем, пас аз он 0 менависем.
\(a_7\) - \(x_7\) то, яъне \(x_7\) то 1 менависем, пас аз он 0 менависем.
...
\(a_{n-1}\) - \(x_{n-1}\) то, яъне \(x_{n-1}\) то 1 менависем, пас аз он 0 менависем.
\(a_n\) - \(x_n\) то, яъне \(x_n\) то 1 менависем, лекин пас аз он 0 наменависем.
Ҳамагӣ \(n+k-1\) элемент ҳосил шуд. Аз ин элементҳо мо бояд k-тоашро интихоб намоем, яъне \(\overline{C}_{n}^k=C_{n+k-1}^k\). Яъне ин формула низ исбот шуд.
\(\textbf{Намуна:}\)
\(\textbf{Шарт:}\)
Искандар варзишгар буда, 4 рӯз дар як ҳафта бо каратэ машғул аст.Ӯ бо чанд тарз ҷадвали ҳафтаинаашро сохта метавонад?
\(\textbf{Ҳал:}\)
A = \(\{\)Душанбе, Сешанбе, Чоршанбе, Панҷшанбе, Ҷумъа, Шанбе, Якшанбе\(\}\)
1. {Душанбе, Сешанбе, Чоршанбе, Панҷшанбе}
2. {Душанбе, Сешанбе, Чоршанбе, Ҷумъа}
3. {Душанбе, Сешанбе, Чоршанбе, Шанбе}
4. {Душанбе, Сешанбе, Чоршанбе, Якшанбе}
5. ...
Барои ҳисоб кардани миқдори тарзҳои машғул шудан бо каратэ дар як ҳафта пайвасткуниро истифода мебарем:
$$ C_7^4=\frac{7!}{4!\cdot3!}=\frac{7\cdot6\cdot5}{3\cdot2\cdot1}=7\cdot5=35$$
\(\textbf{Ҷавоб:}\) Искандар бо 35 тарз нақшаи ҳафтаинаашро сохта метавонад.
