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

Անվան այլ կիրառումների համար տե՛ս՝ Զուգորդություն (այլ կիրառումներ)

${\displaystyle {\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},}$

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

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

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

 

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

${\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},}$ 

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

${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}$ 

և

${\displaystyle {\binom {n}{k}}=0}$ 

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

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

${\displaystyle {\binom {n}{k}}={\frac {n(n-1)...(n-r+1)}{k!}}={\frac {n!}{k!(n-k)}}}$ :

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

${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}$ 

որտեղ 0 < k < n, որը հետևում է (1 + X)ⁿ = (1 + X)^{n − 1}(1 + X)-ից։ Այս մեթոդով կարելի է կառուցել Պասկալի եռանկյունը, որի կից թվերը կախված են հետևյալ առնչությամբ։

${\displaystyle {\binom {n}{k}}={\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{եթե }}k0\end{cases}}.}$ 

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

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

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

${\displaystyle {52 \choose 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:}$ 

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

${\displaystyle {\begin{alignedat}{2}{52 \choose 5}&={\frac {52!}{5!47!}}\\[5pt]&={\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!}}}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\\[5pt]&={\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}}}}\\[5pt]&={26\times 17\times 10\times 49\times 12}\\[5pt]&=2{,}598{,}960.\end{alignedat}}}$ 
Կամ, կարելի է օգտվել հետևյալ համարժեք հավասարումից.
${\displaystyle {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}},}$ 

որից

${\displaystyle {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:}$ 

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

${\displaystyle {\begin{aligned}{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\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\[6pt]&=2{,}598{,}960:\end{aligned}}}$