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

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

որը կարելի է ներկայացնել ֆակտորիալի տեսքով որպես  երբ ։  դեպքում այն հավասար է զրոյի։ Այս բանաձևը կարելի է ստանալ այն փաստից, որ n տարր ունեցող S բազմության յուրաքանչյուր k-զուգորդություն ունի  կարգավորություն, հետևաբար՝  or ։ S բազմության բոլոր k-զուգորդությունների բազմությունը հաճախ նշանակվում է -ով։

k-զուգորդության գաղափարը համապատասխանում է բազմությունից k անգամ առանց կրկնության անդամներ վերցնելուն։ Եթե կրկնություն թույլատրվում է, ապա այն կոչում են զուգորդություն կրկնություններով և քանակը նշանակում են -ով կամ -ով also referred to as an unordered selection.When the term combination is used to refer to either situation (as in ) care must be taken to clarify whether sets or multisets are being discussed.։ Եթե վերևի օրինակում հնարավոր լիներ մրգերից երկու հատ ընտրել, ապա հնարավոր ընտրությունների քանակը կավելանար երեքով՝ երկու խնձոր, երկու նարինջ և երկու տանձ։

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

 k-զուգորդությունների քանակ 
Տրված n տարր ունեցող S բազմության k-զուգորդությունը հաճախ նշանակվում է -ով, -ով, -ով,  -ով, -ով, -ով կամ -ով (վերջին տարբերակը տարածված է ֆրանսերեն, ռումիներեն, ռուսերեն և չինարեն գրականությունում): Կարելի է -ը սահմանել բոլոր բնական k թվերի համար հետևյալ կերպ՝

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

և

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

Տեսնելու համար, որ այս գործակիցները հաշվում են S-ից k-զուգորդությունները, դիտարկենք n տարրերից բոլոր k-զուգորդությունները։ Բոլոր հնարավոր եղանակներով կարգավորենք նրանցից յուրաքանչյուրը։ Ամեն մի k-զուգորդությունից ստացվում է  հատ n տարրերից k-կարգավորություն։ Քանի որ արդյունքում կստանանք n տարրերից բոլոր k-կարգավորությունները, հետրևաբար : Եվ պարզ է, որ 

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

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

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

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

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

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

որից

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

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

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