Զուգորդություն (կոմբինատորիկա)

Կաղապար:Այլ Մաթեմատիկայում, զուգորդությունը բազմություններից որոշակի անդամների առանց կրկնության ընտրությունն է, այնպես, որ ընտրված անդամների հերթականությունը կարևոր չէ։ Օրինակ, եթե տրված է երեք միրգ՝ խնձոր, նարինջ և տանձ, ապա այդ բազմությունից կարելի է ընտրել երկու տարր երեք ձևով՝ խնձոր և տանձ, խնձոր և նարինջ կամ տանձ և նարինջ։ Ֆորմալ սահմանմամբ, S բազմության որևէ k հզորությամբ և չկրկնվող անդամներով ենթաբազմությունը կոչվում է S բազմության k-զուգորդություն կամ զուգորդություն։ Այսպիսով, երկու զուգորդություններ նույնական են այն և միայն այն դեպքում, երբ դրանք ունեն նույն անդամները (անդամների հերթականությունը կարևոր չէ)։ Եթե բազմությունը ունի n տարր, ապա բազմության k-զուգորդությունների քանակը նշանակվում է $(\genfrac{}{}{0ex}{}{n}{k})$-ով, $C(n,k)$-ով կամ $C_k^n$-ով և հավասար է

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1},$

որը կարելի է ներկայացնել ֆակտորիալի տեսքով որպես $\frac{n!}{k!(n-k)!}$ երբ $k\le n$։ $k>n$ դեպքում այն հավասար է զրոյի։ Այս բանաձևը կարելի է ստանալ այն փաստից, որ n տարր ունեցող S բազմության յուրաքանչյուր k-զուգորդություն ունի $k!$ կարգավորություն, հետևաբար՝ $P_k^n=C_k^n\times k!$ or $C_k^n=P_k^n/k!$։ S բազմության բոլոր k-զուգորդությունների բազմությունը հաճախ նշանակվում է $(\genfrac{}{}{0ex}{}{S}{k})$-ով։

k-զուգորդության գաղափարը համապատասխանում է բազմությունից k անգամ առանց կրկնության անդամներ վերցնելուն։ Եթե կրկնություն թույլատրվում է, ապա այն կոչում են զուգորդություն կրկնություններով և քանակը նշանակում են $(\genfrac{}{}{0ex}{}{\hat{n}}{k})$-ով կամ $\left((\genfrac{}{}{0ex}{}{n}{k})\right)$-ով։ Եթե վերևի օրինակում հնարավոր լինել մրգերից երկու հատ ընտրել, ապա հնարավոր ընտրությունների քանակը կավելանար երեքով՝ երկու խնձոր, երկու նարինջ և երկու տանձ։

Չնայած երեք մրգերի օրինակում բոլոր զուգորդությունների ցանկը կազմելը հեշտ էր, այդ խնդիրը ոչ պրակտիկ է դառնում մեծ բազմությունների դեպքում։ Օրինակ, պոկերի ձեռքը կարելի է ներկայացնել որպես 52 քաղաքարտի 5-զուգորդություն, քանի որ ձեռքում խաղաքարերն իրարից տարբեր են և հերթականությունը կարևոր չէ։ Գոյություն ունեն 2,598,960 զուգորդություններ։

k-զուգորդությունների քանակ

5 տարր ունեցող բազմության 3 տարրանոց ենթաբազմություն

Տրված n տարր ունեցող S բազմության k-զուգորդությունը հաճախ նշանակվում է $(\genfrac{}{}{0ex}{}{n}{k})$-ով, $C(n,k)$-ով, $C_k^n$-ով, ${}_n{C}_k$-ով, ${}^n{C}_k$-ով, $C_{n,k}$-ով կամ $C_n^k$-ով (վերջին տարբերակը տարածված է ֆրանսերեն, ռումիներեն, ռուսերեն և չինարեն գրականությունում): Կարելի է $(\genfrac{}{}{0ex}{}{n}{k})$-ը սահմանել բոլոր բնական k թվերի համար հետևյալ կերպ՝

$(1+X{)}^n=\sum _{k\ge 0}(\genfrac{}{}{0ex}{}{n}{k})X^k,$

ինչից պարզ է, որ

$(\genfrac{}{}{0ex}{}{n}{0})=(\genfrac{}{}{0ex}{}{n}{n})=1,$

և

$(\genfrac{}{}{0ex}{}{n}{k})=0$

կամայական k > n համար։

Տեսնելու համար, որ այս գործակիցները հաշվում են S-ից k-զուգորդությունները, դիտարկենք n տարրերից բոլոր k-զուգորդությունները։ Բոլոր հնարավոր եղանակներով կարգավորենք նրանցից յուրաքանչյուրը։ Ամեն մի k-զուգորդությունից ստացվում է $k!$ հատ n տարրերից k-կարգավորություն։ Քանի որ արդյունքում կստանանք n տարրերից բոլոր k-կարգավորությունները, հետրևաբար $r!(\genfrac{}{}{0ex}{}{n}{k})=n(n-1)...(n-k+1)$: Եվ պարզ է, որ

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n(n-1)...(n-r+1)}{k!}=\frac{n!}{k!(n-k)}$:

n տարրերից k-զուգորդությունների քանակը կարելի է հաշվել նաև հետևյալ անդրադարձ առնչությունների միջոցով.

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-1}{k}),$

որտեղ 0 < k < n, որը հետևում է Կաղապար:Nowrap=Կաղապար:Nowrap-ից։ Այս մեթոդով կարելի է կառուցել Պասկալի եռանկյունը, որի կից թվերը կախված են հետևյալ առնչությամբ։

$(\genfrac{}{}{0ex}{}{n}{k})=\{\begin{array}{cc}(\genfrac{}{}{0ex}{}{n}{k-1})\frac{n-k+1}{k}& \text{եթե }k>0\\ (\genfrac{}{}{0ex}{}{n-1}{k})\frac{n}{n-k}& \text{եթե }k<n\\ (\genfrac{}{}{0ex}{}{n-1}{k-1})\frac{n}{k}& \text{եթե }n,k>0\end{array}.$

Այս և $(\genfrac{}{}{0ex}{}{n}{0})=1=(\genfrac{}{}{0ex}{}{n}{n})$ նույնության միջոցով կարելի է հաջորդաբար հաշվել Պասկալի եռանկյան յուրաքանչյուր տող։

Զուգորդությունների քանակը հաշվելու օրինակ

Հաշվենք ստանդարտ 52 խաղաքարտերից 5 խաղաքարտ ընտրելու բոլոր հնարավոր տարբերակների քանակը.

$(\genfrac{}{}{0ex}{}{52}{5})=\frac{52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}=\frac{311,875,200}{120}=2,598,960:$

Նույն արդյունքը կարելի է ստանալ արտահայտությունը ֆակտորիալի տեսքով և համարաչին ու հայտարարը ընհանուր արտադրիչներով բաժանելու միջոցով.

$\begin{array}{cc}(\genfrac{}{}{0ex}{}{52}{5})& =\frac{52!}{5!47!}\\ & =\frac{52\times 51\times 50\times 49\times 48\times \cancel{47!}}{5\times 4\times 3\times 2\times \cancel{1}\times \cancel{47!}}\\ & =\frac{52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}\\ & =\frac{(26\times \cancel{2})\times (17\times \cancel{3})\times (10\times \cancel{5})\times 49\times (12\times \cancel{4})}{\cancel{5}\times \cancel{4}\times \cancel{3}\times \cancel{2}}\\ & =26\times 17\times 10\times 49\times 12\\ & =2,598,960.\end{array}$

Կամ, կարելի է օգտվել հետևյալ համարժեք հավասարումից.

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{(n-0)}{1}\times \frac{(n-1)}{2}\times \frac{(n-2)}{3}\times \cdots \times \frac{(n-(k-1))}{k},$

որից

$(\genfrac{}{}{0ex}{}{52}{5})=\frac{52}{1}\times \frac{51}{2}\times \frac{50}{3}\times \frac{49}{4}\times \frac{48}{5}=2,598,960:$

Առանց կրճատման հաշվելու դեպքում ստացվում է.

$\begin{array}{cc}(\genfrac{}{}{0ex}{}{52}{5})& =\frac{n!}{k!(n-k)!}=\frac{52!}{5!(52-5)!}=\frac{52!}{5!47!}\\ & =\frac{80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}\\ & =2,598,960:\end{array}$