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

Մաթեմատիկայում, **զուգորդությունը** բազմություններից որոշակի անդամների առանց կրկնության ընտրությունն է, այնպես, որ ընտրված անդամների հերթականությունը կարևոր չէ։ Օրինակ, եթե տրված է երեք միրգ՝ խնձոր, նարինջ և տանձ, ապա այդ բազմությունից կարելի է ընտրել երկու տարր երեք ձևով՝ խնձոր և տանձ, խնձոր և նարինջ կամ տանձ և նարինջ։ Ֆորմալ սահմանմամբ, *S* բազմության որևէ *k* հզորությամբ և չկրկնվող անդամներով ենթաբազմությունը կոչվում է *S* բազմության *k-զուգորդություն*  կամ *զուգորդություն*։ Այսպիսով, երկու զուգորդություններ նույնական են այն և միայն այն դեպքում, երբ դրանք ունեն նույն անդամները (անդամների հերթականությունը կարևոր չէ)։ Եթե բազմությունը ունի *n* տարր, ապա բազմության *k-զուգորդությունների* քանակը նշանակվում է \textstyle\binom nk-ով, C(n,k)-ով կամ C^n_k-ով և հավասար է 

: \binom nk = \frac{n(n-1)\dotsb(n-k+1)}{k(k-1)\dotsb1},

որը կարելի է ներկայացնել ֆակտորիալի տեսքով որպես \textstyle\frac{n!}{k!(n-k)!} երբ k\leq n։ k>n դեպքում այն հավասար է զրոյի։ Այս բանաձևը կարելի է ստանալ այն փաստից, որ *n* տարր ունեցող *S* բազմության յուրաքանչյուր k-զուգորդություն ունի k! կարգավորություն, հետևաբար՝ P^n_k = C^n_k \times k! or C^n_k = P^n_k / k!։ *S* բազմության բոլոր *k*-զուգորդությունների բազմությունը հաճախ նշանակվում է \textstyle\binom Sk-ով։

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

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

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

Տրված *n* տարր ունեցող *S* բազմության *k*-զուգորդությունը հաճախ նշանակվում է \textstyle\binom nk-ով, C(n,k)-ով, C^n_k-ով,  {}_nC_k-ով, {}^nC_k-ով, C_{n,k}-ով կամ C_n^k-ով (վերջին տարբերակը տարածված է ֆրանսերեն, ռումիներեն, ռուսերեն և չինարեն գրականությունում): Կարելի է \tbinom nk-ը սահմանել բոլոր բնական *k* թվերի համար հետևյալ կերպ՝

:(1 + X)^n = \sum_{k\geq0}\binom{n}{k} X^k,

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

:\binom{n}{0} = \binom{n}{n} = 1,

և

:\binom{n}{k} = 0

կամայական *k*&nbsp;&gt;&nbsp;*n* համար։

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

:\binom nk = \frac{n(n-1)...(n-r+1)}{k!} = \frac{n!}{k!(n-k)}:
*n* տարրերից *k-*զուգորդությունների քանակը կարելի է հաշվել նաև հետևյալ անդրադարձ առնչությունների միջոցով*.*
:\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k},

որտեղ 0 
\binom nk =
\begin{cases}
\binom n{k-1} \frac {n-k+1}k &\quad \text{եթե } k > 0 \\
\binom {n-1}k \frac n{n-k} &\quad \text{եթե } k  0
\end{cases}.


Այս և \tbinom n0=1=\tbinom nn նույնության միջոցով կարելի է հաջորդաբար հաշվել Պասկալի եռանկյան յուրաքանչյուր տող։

### Զուգորդությունների քանակը հաշվելու օրինակ
Հաշվենք ստանդարտ 52 խաղաքարտերից 5 խաղաքարտ ընտրելու բոլոր հնարավոր տարբերակների քանակը.
: {52 \choose 5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311{,}875{,}200}{120} = 
2{,}598{,}960:

Նույն արդյունքը կարելի է ստանալ արտահայտությունը ֆակտորիալի տեսքով և համարաչին ու հայտարարը ընհանուր արտադրիչներով բաժանելու միջոցով.
:\begin{alignat}{2}
  {52 \choose 5}
    &= \frac{52!}{5!47!} \\[5pt]
    &= \frac{52\times51\times50\times49\times48\times\cancel{47!}}{5\times4\times3\times2\times\cancel{1}\times\cancel{47!}} \\[5pt]
    &= \frac{52\times51\times50\times49\times48}{5\times4\times3\times2} \\[5pt]
    &= \frac{(26\times\cancel{2})\times(17\times\cancel{3})\times(10\times\cancel{5})\times49\times(12\times\cancel{4})}{\cancel{5}\times\cancel{4}\times\cancel{3}\times\cancel{2}} \\[5pt]
    &= {26\times17\times10\times49\times12} \\[5pt]
    &= 2{,}598{,}960.
\end{alignat}
:Կամ, կարելի է օգտվել հետևյալ համարժեք հավասարումից.
: {n \choose k} = \frac { ( n - 0 ) }1 \times \frac { ( n - 1 ) }2 \times \frac { ( n - 2 ) }3 \times \cdots \times \frac { ( n - (k - 1) ) }k,
որից
: {52 \choose 5} = \frac{52}1 \times \frac{51}2 \times \frac{50}3 \times \frac{49}4 \times \frac{48}5 = 2{,}598{,}960:


Առանց կրճատման հաշվելու դեպքում ստացվում է.
:
\begin{align}
 {52 \choose 5} &= \frac{n!}{k!(n-k)!} = \frac{52!}{5!(52-5)!} = \frac{52!}{5!47!} \\[6pt]
&= \tfrac{80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000} \\[6pt]
&= 2{,}598{,}960:
\end{align}

## Ծանոթագրություններ

Դիսկրետ մաթեմատիկա