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

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

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

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

որը կարելի է ներկայացնել ֆակտորիալի տեսքով որպես $\textstyle {\frac {n!}{k!(n-k)!}}$ երբ $k\leq 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-զուգորդությունների բազմությունը հաճախ նշանակվում է $\textstyle {\binom {S}{k}}$-ով։

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

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

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

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

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

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

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

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

և

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

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

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

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

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

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

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

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

${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:$

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

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

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

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