Kombinasyon

Matematikte kombinasyon, seçim sırasının önemli olmadığı (permütasyonların aksine), farklı üyelere sahip bir kümeden öğelerin seçilmesidir. Örneğin, bir elma, bir portakal ve bir armut gibi üç meyve verildiğinde, bu kümeden çıkarılabilecek üç kombinasyon vardır: bir elma ve bir armut; bir elma ve bir portakal; veya bir armut ve bir portakal. Daha resmi olarak, bir S kümesinin k-kombinasyonu, S'nin k farklı elemanının bir alt kümesidir. Bu nedenle, iki kombinasyon ancak ve ancak her kombinasyon aynı üyelere sahipse özdeştir. (Her bir kümedeki üyelerin dizilişi önemli değildir.) Kümenin n elemanı varsa, k-kombinasyon sayısı $C_{k}^{n}$, binom katsayısına eşittir ⓘ

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

ⓘ

faktöriyeller kullanılarak şu şekilde yazılabilir $\textstyle {\frac {n!}{k!(n-k)!}}$ ne zaman $k\leq n$ve sıfır olduğu zaman $k>n$. Bu formül, n üyeli bir S kümesinin her k-kombinasyonunun aşağıdaki özelliklere sahip olduğu gerçeğinden türetilebilir $k!$ permütasyonlar yani $P_{k}^{n}=C_{k}^{n}\times k!$ veya $C_{k}^{n}=P_{k}^{n}/k!$. Bir S kümesinin tüm k-kombinasyonlarının kümesi genellikle şu şekilde gösterilir $\textstyle {\binom {S}{k}}$. ⓘ

Kombinasyon, tekrarlama olmaksızın bir seferde k tane alınan n şeyin kombinasyonudur. Tekrarlamaya izin verilen kombinasyonları ifade etmek için genellikle k-seçim, k-multiset veya tekrarlamalı k-kombinasyon terimleri kullanılır. Yukarıdaki örnekte, herhangi bir meyve türünden iki tane olması mümkün olsaydı, 3 tane daha 2'li seçim olurdu: biri iki elmalı, biri iki portakallı ve biri de iki armutlu. ⓘ

Üç meyveden oluşan küme, kombinasyonların tam bir listesini yazmak için yeterince küçük olsa da, kümenin boyutu arttıkça bu pratik olmaz. Örneğin, bir poker eli 52 kartlık bir destedeki (n = 52) kartların 5'li kombinasyonu (k = 5) olarak tanımlanabilir. Eldeki 5 kartın hepsi birbirinden farklıdır ve eldeki kartların sırası önemli değildir. Böyle 2.598.960 kombinasyon vardır ve herhangi bir eli rastgele çekme şansı 1 / 2.598.960'tır. ⓘ

Kombinasyon, bir nesne grubu içerisinden sıra gözetmeksizin yapılan seçimlerdir. Nesne grubunun tekabül ettiği kümenin alt kümeleri olarak da tanımlanabilir. Çünkü alt kümelerde sıra önemli değildir. ⓘ

K-kombinasyonlarının sayısı

5 elemanlı bir kümenin 3 elemanlı alt kümeleri ⓘ

Verilen n elemanlı bir S kümesinden k-kombinasyon sayısı, temel kombinatorik metinlerinde genellikle şu şekilde gösterilir $C(n,k)$veya aşağıdaki gibi bir varyasyonla $C_{k}^{n}$, ${}_{n}C_{k}$, ${}^{n}C_{k}$, $C_{n,k}$ hatta $C_{n}^{k}$ (son biçim Fransızca, Romence, Rusça, Çince ve Lehçe metinlerde standarttır). Ancak aynı sayı, diğer birçok matematiksel bağlamda şu şekilde gösterilir ${\tbinom {n}{k}}$ (genellikle "n k'yı seçer" olarak okunur); özellikle binom formülünde bir katsayı olarak ortaya çıkar, bu nedenle binom katsayısı olarak adlandırılır. Biri tanımlayabilir ${\tbinom {n}{k}}$ bağıntısı ile tüm k doğal sayıları için aynı anda ⓘ

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

ⓘ

Buradan da anlaşılacağı üzere ⓘ

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

ⓘ

ve daha fazlası, ⓘ

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

ⓘ

k > n için. ⓘ

Bu katsayıların S'den k-kombinasyonlarını saydığını görmek için, önce S'nin s elemanlarıyla etiketlenmiş n farklı Xs değişkenleri koleksiyonu düşünülebilir ve çarpım S'nin tüm elemanları üzerinde genişletilebilir:

$$\prod _{s\in S}(1+X_{s});$$

ⓘ

S'nin tüm alt kümelerine karşılık gelen 2n farklı terime sahiptir, her alt küme karşılık gelen Xs değişkenlerinin çarpımını verir. Şimdi tüm X'leri etiketsiz değişken X'e eşitleyerek çarpımın (1 + X)n olmasını sağlayın, S'deki her k-kombinasyonun terimi Xk olur, böylece sonuçtaki bu gücün katsayısı bu tür k-kombinasyonların sayısına eşit olur. ⓘ

Binom katsayıları çeşitli şekillerde açık olarak hesaplanabilir. (1 + X)n'e kadar olan açılımlar için hepsini elde etmek için (daha önce verilen temel durumlara ek olarak) özyineleme ilişkisi kullanılabilir ⓘ

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

ⓘ

0 < k < n içiⁿ, (1 + X)n = (1 + X)n - 1(1 + X); bu Pascal üçgeninin oluşturulmasına yol açar. ⓘ

Tek bir binom katsayısını belirlemek için aşağıdaki formülü kullanmak daha pratiktir ⓘ

$${\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.$$

ⓘ

Pay, n'nin k-permutasyonlarının, yani S'nin k farklı elemanının dizilerinin sayısını verirken, payda, sıra göz ardı edildiğinde aynı k-kombinasyonunu veren bu tür k-permutasyonlarının sayısını verir. ⓘ

k sayısı n/2'yi aştığında, yukarıdaki formül pay ve paydada ortak faktörler içerir ve bunların iptal edilmesi şu ilişkiyi verir ⓘ

$${\binom {n}{k}}={\binom {n}{n-k}},$$

ⓘ

Bu, binom formülünden açıkça görülen bir simetriyi ifade eder ve (n - k) kombinasyonu olan böyle bir kombinasyonun tümleyenini alarak k-kombinasyonları açısından da anlaşılabilir. ⓘ

Son olarak, bu simetriyi doğrudan sergileyen ve hatırlanması kolay olma özelliğine sahip bir formül vardır:

$${\binom {n}{k}}={\frac {n!}{k!(n-k)!}},$$

ⓘ

Bu formül, pay ve paydayı (n - k) ile çarparak önceki formülden elde edilir, bu nedenle hesaplama açısından bu formülden kesinlikle daha az verimlidir. ⓘ

Son formül, S'nin tüm elemanlarının n<nowiki>!</nowiki> permütasyonlarını göz önünde bulundurarak doğrudan anlaşılabilir. Bu permütasyonların her biri, ilk k elemanını seçerek bir k-kombinasyon verir. Birçok yinelenen seçim vardır: ilk k elemanın birbirleri arasında ve son (n - k) elemanın birbirleri arasındaki herhangi bir kombine permütasyonu aynı kombinasyonu üretir; bu da formüldeki bölünmeyi açıklar. ⓘ

Yukarıdaki formüllerden, Pascal üçgenindeki bitişik sayılar arasındaki her üç yöndeki ilişkileri takip edin:

$${\binom {n}{k}}={\begin{cases}{\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\{\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\{\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}.$$

ⓘ

Temel durumlarla birlikte ${\tbinom {n}{0}}=1={\tbinom {n}{n}}$Bunlar sırasıyla aynı kümeden (Pascal'ın üçgenindeki bir satır) tüm kombinasyon sayılarının, artan boyutlardaki kümelerin k-kombinasyonlarının ve sabit n - k boyutunda bir tamamlayıcıya sahip kombinasyonların ardışık olarak hesaplanmasını sağlar. ⓘ

Sayma kombinasyonlarına örnek

Spesifik bir örnek olarak, standart elli iki kartlık bir desteden elde edilebilecek beş kartlık el sayısı şu şekilde hesaplanabilir:

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

ⓘ

Alternatif olarak, formül faktöriyeller cinsinden kullanılabilir ve paydaki faktörler paydadaki faktörlerin bir kısmına karşı iptal edilebilir, bundan sonra sadece kalan faktörlerin çarpılması gerekir:

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

ⓘ

İlkine eşdeğer olan bir başka alternatif hesaplama, aşağıdakilerin yazılmasına dayanır ⓘ

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

ⓘ

hangi verir ⓘ

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

ⓘ

Aşağıdaki sırada değerlendirildiğinde, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, bu yalnızca tamsayı aritmetiği kullanılarak hesaplanabilir. Bunun nedeni, her bölme işlemi gerçekleştiğinde, üretilen ara sonucun kendisinin bir binom katsayısı olması, dolayısıyla hiçbir kalanın oluşmamasıdır. ⓘ

Simetrik formülü faktöriyeller cinsinden basitleştirme yapmadan kullanmak oldukça kapsamlı bir hesaplama verir:

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

ⓘ

k-kombinasyonlarını numaralandırma

Biri, n elemanlı belirli bir S kümesinin tüm k-kombinasyonlarını sabit bir sırada sayabilir, bu da bir aralıktan bir bieksiyon oluşturur. ${\tbinom {n}{k}}$ bu k-kombinasyonlarının kümesi ile tamsayılar. S'nin kendisinin sıralı olduğunu varsayarsak, örneğin S = { 1, 2, ..., n }, k-kombinasyonlarını sıralamak için iki doğal olasılık vardır: önce en küçük elemanlarını karşılaştırarak (yukarıdaki resimlerde olduğu gibi) veya önce en büyük elemanlarını karşılaştırarak. İkinci seçenek, S'ye yeni bir en büyük eleman eklemenin numaralandırmanın başlangıç kısmını değiştirmeyeceği, sadece daha büyük kümenin yeni k-kombinasyonlarını öncekilerden sonra ekleyeceği avantajına sahiptir. Bu işlem tekrarlanarak, daha büyük kümelerin k-kombinasyonları ile sayım süresiz olarak genişletilebilir. Dahası, tam sayıların aralıkları 0'dan başlayacak şekilde alınırsa, numaralandırmada verilen bir i yerindeki k-kombinasyonu i'den kolayca hesaplanabilir ve bu şekilde elde edilen bijeksiyon kombinatoryal sayı sistemi olarak bilinir. Hesaplama matematiğinde "rank"/"ranking" ve "unranking" olarak da bilinir. ⓘ

k kombinasyonlarını sıralamanın birçok yolu vardır. Bir yol, 2n'den küçük tüm ikili sayıları ziyaret etmektir. Bu küçük n için bile çok verimsiz olsa da, k sıfır olmayan biti olan sayıları seçin (örneğin, n = 20 için yaklaşık bir milyon sayıyı ziyaret etmek gerekirken, izin verilen maksimum k kombinasyon sayısı k = 10 için yaklaşık 186 bindir). Bu 1 bitlerinin böyle bir sayıdaki konumları {1, ..., n } kümesinin belirli bir k-kombinasyonudur. Diğer basit ve daha hızlı bir yol ise {0 ... k-1} (sıfır tabanlı) veya {1 ... k} ile başlayarak seçilen elemanların k indeks numarasını izlemektir. (bir tabanlı) ilk izin verilen k-kombinasyon olarak ve ardından n-1'den (sıfır tabanlı) veya n'den (bir tabanlı) küçükse son indeks numarasını veya böyle bir indeks varsa onu izleyen indeks numarasından eksi bir küçük olan son indeks numarası x'i artırarak ve x'ten sonraki indeks numaralarını {x+1, x+2, ...} olarak sıfırlayarak bir sonraki izin verilen k-kombinasyona tekrar tekrar geçerek. ⓘ

Tekrarlı kombinasyon sayısı

Tekrarlı bir k-kombinasyon veya k-çoklu kombinasyon veya n boyutlu bir S kümesinden k boyutlu bir çoklu alt küme, sıralamanın dikkate alınmadığı, S'nin mutlaka farklı olmayan k elemanından oluşan bir küme tarafından verilir: iki dizi, biri diğerinden terimlerin permütasyonu ile elde edilebiliyorsa aynı çoklu kümeyi tanımlar. Başka bir deyişle, n elemanlı bir kümeden k elemanlı bir örneklemdir, yinelemelere izin verir (yani, değiştirme ile) ancak farklı sıralamaları göz ardı eder (örneğin {2,1,2} = {1,2,2}). S'nin her bir elemanına bir indeks atayın ve S'nin elemanlarını nesne türleri olarak düşünün, o zaman $x_{i}$ bir çoklu alt kümedeki i tipindeki elemanların sayısını gösterir. O halde k büyüklüğündeki çoklu alt küme sayısı, Diophantine denkleminin negatif olmayan tamsayı (yani sıfıra izin veren) çözümlerinin sayısıdır:

$$x_{1}+x_{2}+\ldots +x_{n}=k.$$

ⓘ

S'nin n elemanı varsa, bu tür k çoklu alt kümelerin sayısı şu şekilde gösterilir ⓘ

$$\left(\!\!{\binom {n}{k}}\!\!\right),$$

ⓘ

k-alt kümeleri sayan binom katsayısına benzer bir gösterimdir. Bu ifade, n multichoose k, binom katsayıları cinsinden de verilebilir:

$$\left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}.$$

ⓘ

Bu ilişki, yıldızlar ve çubuklar olarak bilinen bir gösterim kullanılarak kolayca kanıtlanabilir.

İspat

Yukarıdaki Diophantine denkleminin bir çözümü şu şekilde gösterilebilir $x_{1}$ yıldızlar, bir ayırıcı (bir çubuk), sonra $x_{2}$ daha fazla yıldız, başka bir ayırıcı ve bu şekilde devam eder. Bu gösterimdeki toplam yıldız sayısı k ve çubuk sayısı n - 1'dir (n parçaya ayırma n-1 ayırıcı gerektirdiğinden). Dolayısıyla, k + n - 1 (veya n + k - 1) sembolden (yıldızlar ve çubuklar) oluşan bir dizi, dizide k yıldız varsa bir çözüme karşılık gelir. Herhangi bir çözüm, yıldızları yerleştirmek için k + n - 1 konumdan k tanesini seçerek ve kalan konumları çubuklarla doldurarak temsil edilebilir. Örneğin, çözüm $x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5$ denkleminin $x_{1}+x_{2}+x_{3}+x_{4}=10$ (n = 4 ve k = 10) ile temsil edilebilir.

$$\bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar .$$

Bu tür dizelerin sayısı, 10 yıldızı 13 konuma yerleştirmenin yollarının sayısıdır, ${\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}$ Bu da 4 elemanlı bir kümenin 10 çoklu alt kümelerinin sayısıdır. ⓘ

7'li bir kümenin 3'lü alt kümeleri (solda) ve 5'li bir kümenin elemanlarını içeren 3'lü çoklu kümeler (sağda) arasındaki bieksiyon.
Bu şunu göstermektedir ${\textstyle {\binom {7}{3}}=\left(\!\!{\binom {5}{3}}\!\!\right)}$. ⓘ

Binom katsayılarında olduğu gibi, bu çoklu seçim ifadeleri arasında da çeşitli ilişkiler vardır. Örneğin, için $n\geq 1,k\geq 0$, ⓘ

$$\left(\!\!{\binom {n}{k}}\!\!\right)=\left(\!\!{\binom {k+1}{n-1}}\!\!\right).$$

Bu özdeşlik, yukarıdaki gösterimde yıldızların ve çubukların yer değiştirmesinden kaynaklanır. ⓘ

Çoklu alt kümeleri sayma örneği

Örneğin, bir menüde aralarından seçim yapabileceğiniz dört çeşit çörek (n = 4) varsa ve siz üç çörek (k = 3) istiyorsanız, çörekleri tekrarlı olarak seçmenin yollarının sayısı şu şekilde hesaplanabilir ⓘ

$$\left(\!\!{\binom {4}{3}}\!\!\right)={\binom {4+3-1}{3}}={\binom {6}{3}}={\frac {6\times 5\times 4}{3\times 2\times 1}}=20.$$

ⓘ

Bu sonuç, S = {1,2,3,4} kümesinin tüm 3'lü çoklu alt kümeleri listelenerek doğrulanabilir. Bu, aşağıdaki tabloda gösterilmektedir. İkinci sütun gerçekte seçtiğiniz çörekleri listelerken, üçüncü sütun negatif olmayan tamsayı çözümlerini göstermektedir $[x_{1},x_{2},x_{3},x_{4}]$ denkleminin $x_{1}+x_{2}+x_{3}+x_{4}=3$ ve son sütun çözümlerin yıldız ve çubuk gösterimini vermektedir. ⓘ

Hayır.	3'lü multiset	Eşitlik çözüm	Yıldızlar ve çubuklar ⓘ
1	{1,1,1}	[3,0,0,0]	$\bigstar \bigstar \bigstar |||$
2	{1,1,2}	[2,1,0,0]	$\bigstar \bigstar |\bigstar ||$
3	{1,1,3}	[2,0,1,0]	$\bigstar \bigstar ||\bigstar |$
4	{1,1,4}	[2,0,0,1]	$\bigstar \bigstar |||\bigstar$
5	{1,2,2}	[1,2,0,0]	$\bigstar |\bigstar \bigstar ||$
6	{1,2,3}	[1,1,1,0]	$\bigstar |\bigstar |\bigstar |$
7	{1,2,4}	[1,1,0,1]	$\bigstar |\bigstar ||\bigstar$
8	{1,3,3}	[1,0,2,0]	$\bigstar ||\bigstar \bigstar |$
9	{1,3,4}	[1,0,1,1]	$\bigstar ||\bigstar |\bigstar$
10	{1,4,4}	[1,0,0,2]	$\bigstar |||\bigstar \bigstar$
11	{2,2,2}	[0,3,0,0]	$|\bigstar \bigstar \bigstar ||$
12	{2,2,3}	[0,2,1,0]	$|\bigstar \bigstar |\bigstar |$
13	{2,2,4}	[0,2,0,1]	$|\bigstar \bigstar ||\bigstar$
14	{2,3,3}	[0,1,2,0]	$|\bigstar |\bigstar \bigstar |$
15	{2,3,4}	[0,1,1,1]	$|\bigstar |\bigstar |\bigstar$
16	{2,4,4}	[0,1,0,2]	$|\bigstar ||\bigstar \bigstar$
17	{3,3,3}	[0,0,3,0]	$||\bigstar \bigstar \bigstar |$
18	{3,3,4}	[0,0,2,1]	$||\bigstar \bigstar |\bigstar$
19	{3,4,4}	[0,0,1,2]	$||\bigstar |\bigstar \bigstar$
20	{4,4,4}	[0,0,0,3]	$|||\bigstar \bigstar \bigstar$

Tüm k için k kombinasyonlarının sayısı

Tüm k için k-kombinasyonlarının sayısı, n elemanlı bir kümenin alt kümelerinin sayısıdır. Bu sayının 2n olduğunu görmenin birkaç yolu vardır. Kombinasyonlar açısından, ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$Pascal üçgenindeki binom katsayılarının n'inci satırının (0'dan itibaren sayılır) toplamıdır. Bu kombinasyonlar (alt kümeler), 0'dan 2n - 1'e kadar sayan 2 tabanındaki sayılar kümesinin 1 basamağı ile numaralandırılır, burada her basamak konumu n kümesinden bir öğedir. ⓘ

1'den 3'e kadar numaralandırılmış 3 kart verildiğinde, boş küme de dahil olmak üzere 8 farklı kombinasyon (alt küme) vardır:

$$|\{\{\};\{1\};\{2\};\{1,2\};\{3\};\{1,3\};\{2,3\};\{1,2,3\}\}|=2^{3}=8$$

ⓘ

Bu alt kümeleri (aynı sırayla) taban 2 rakamları olarak temsil etme:

• 0 – 000
• 1 – 001
• 2 – 010
• 3 – 011
• 4 – 100
• 5 – 101
• 6 – 110
• 7 – 111 ⓘ

Olasılık: rastgele bir kombinasyonu örnekleme

Belirli bir küme veya listeden rastgele bir kombinasyon seçmek için çeşitli algoritmalar vardır. Reddetme örneklemesi büyük örneklem boyutları için son derece yavaştır. n büyüklüğündeki bir popülasyondan verimli bir şekilde bir k-kombinasyon seçmenin bir yolu, popülasyonun her bir öğesi boyunca yinelemek ve her adımda dinamik olarak değişen bir olasılıkla o öğeyi seçmektir. ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$ (bkz. Rezervuar örneklemesi). Bir diğeri ise, aşağıdakilerden daha küçük rastgele negatif olmayan bir tamsayı seçmektir $\textstyle {\binom {n}{k}}$ ve kombinatoryal sayı sistemini kullanarak bir kombinasyona dönüştürün. ⓘ

Nesneleri kutulara koymanın yollarının sayısı

Bir kombinasyon iki öğe kümesinin seçimi olarak da düşünülebilir: seçilen kutuya gidenler ve seçilmeyen kutuya gidenler. Bu, her öğenin tam olarak bir kutuya gitmesi gerektiği kısıtlamasıyla herhangi bir sayıda kutuya genelleştirilebilir. Nesneleri kutulara koymanın yollarının sayısı çok terimli katsayı ile verilir ⓘ

$${n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}},$$

ⓘ

Burada n öğe sayısı, m kutu sayısı ve $k_{i}$ i kutusuna giren nesnelerin sayısıdır. ⓘ

Bu denklemin neden geçerli olduğunu görmenin bir yolu, önce nesneleri 1'den n'ye kadar rastgele numaralandırmak ve numaraları $1,2,\ldots ,k_{1}$ sırayla ilk kutuya, numaraları olan nesneler $k_{1}+1,k_{1}+2,\ldots ,k_{2}$ sırayla ikinci kutuya ve bu şekilde devam eder. Burada $n!$ Farklı numaralandırmalar olabilir, ancak bunların çoğu eşdeğerdir, çünkü yalnızca bir kutudaki öğeler kümesi önemlidir, içindeki sıraları değil. Her bir kutunun içeriğinin her birleşik permütasyonu, öğeleri kutulara yerleştirmenin eşdeğer bir yolunu üretir. Sonuç olarak, her eşdeğerlik sınıfı şunlardan oluşur $k_{1}!\,k_{2}!\cdots k_{m}!$ farklı numaralandırmalar ve eşdeğerlik sınıflarının sayısı $\textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}$. ⓘ

Binom katsayısı, k öğenin seçilen kutuya girdiği ve geri kalan öğelerin $n-k$ öğeler seçilmemiş çöp kutusuna gider:

$${\binom {n}{k}}={n \choose k,n-k}={\frac {n!}{k!(n-k)!}}.$$

ⓘ

Kombinasyon özellikleri

• C(R, 1) = R
• C(R, R) = 1
• C(R, 0) = 1
• N ≠ M olmak üzere C(R, N) = C(R, M) ise N + M = R
• C(R, N) = S (sayma sayıları) ise R, N'den küçük olamaz. ⓘ

Kombinasyonların hesaplanması

Örnek

$C(5,3)={5 \choose 3}={5 \choose {5-3}}={\frac {P(5,3)}{3!}}={\frac {5!}{3!(5-3)!}}=10$ ⓘ

$C(5,3)$	C1	C2	C3 ⓘ
R1	4	3	2
R2	4	3	1
R3	4	3	0
R4	3	2	1
R5	3	2	0
R6	2	1	4
R7	2	1	0
R8	2	4	0
R9	1	3	0
R10	1	4	0