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

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

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

${\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!}$^[1]։ S բազմության բոլոր k-զուգորդությունների բազմությունը հաճախ նշանակվում է ${\displaystyle \textstyle {\binom {S}{k}}}$-ով։

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

Չնայած երեք մրգերի օրինակում բոլոր զուգորդությունների ցանկը կազմելը հեշտ էր, այդ խնդիրը ոչ պրակտիկ է դառնում մեծ բազմությունների դեպքում։ Օրինակ, պոկերի ձեռքը կարելի է ներկայացնել որպես 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}}$-ով^[6] (վերջին տարբերակը տարածված է ֆրանսերեն, ռումիներեն, ռուսերեն և չինարեն գրականությունում^[7][8]): Կարելի է ${\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{եթե }}k<n\\{\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{եթե }}n,k>0\end{cases}}.}$

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

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

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