Chapterبەش 4 · Lectureوانە 4.4

Combinationsگونجێنەکان

Selections where order does not matter: why every group of $r$ hides $r!$ permutations, the formula $\frac{n!}{r!\,(n-r)!}$ , choosing $r$ is leaving $n - r$ , Pascal's triangle, committees with "at least" conditions, two groups chosen together, the basket problem, combinations in probability (the midterm committee) and math.comb in Python.

هەڵبژاردن کە ڕیز تێیدا گرنگ نییە: بۆچی هەر گرووپێکی $r$ دانەیی $r!$ دەشارێتەوە، $\frac{n!}{r!\,(n-r)!}$ ، هەڵبژاردنی $r$ واتە بەجێهێشتنی $n - r$ ، ، لیژنە بە مەرجی «لانیکەم»، دوو گرووپ کە پێکەوە هەڵدەبژێردرێن، کێشەی سەبەتەکە، لە (لیژنەکەی تاقیکردنەوەی نیوەی وەرز) و math.comb لە Pythonـدا.

16 min read18 خولەک خوێندنەوە · 16 stepsهەنگاو

What you will learnچی فێر دەبیت

Decide whether a counting question needs combinations or permutations.
Compute $\binom{n}{r}$ by cancelling, and use $\binom{n}{r} = \binom{n}{n-r}$ and Pascal's triangle.
Solve committee problems with "at least" conditions by cases or by the complement.
Use combinations to find probabilities when every group is equally likely.

بڕیار بدە ئایا پرسیارێکی ژماردن پێویستی بە هەیە یان بە .
$\binom{n}{r}$ بە سڕینەوە بژمێرە و $\binom{n}{r} = \binom{n}{n-r}$ و بەکاربهێنە.
کێشەی لیژنە بە مەرجی «لانیکەم» بە حاڵەت یان بە چارەسەر بکە.
بەکاربهێنە بۆ دۆزینەوەی کاتێک هەموو گرووپێک بێت.

When order does not matterکاتێک ڕیز گرنگ نییە

In Counting and Permutations you counted arrangements: the order of the objects mattered. First, second and third place in a race are different results, so ABC and BAC are counted separately. That kind of count is a permutation.

لە ژماردن و گۆڕینەکان ڕیزکردنەکانت ژمارد: ڕیزی شتەکان گرنگ بوو. پلەی یەکەم، دووەم و سێیەم لە پێشبڕکێیەکدا ئەنجامی جیاوازن، بۆیە ABC و BAC جیا دەژمێردرێن. ئەو جۆرە ژماردنە .

Many questions ask only which objects are chosen, not in which order: a committee of 3 students, 4 questions to answer from a paper, 3 colours to buy. A committee of Aram, Dilan and Lana is the same committee however you list the names. Such a selection is a combination.

زۆر پرسیار تەنها دەپرسن کام شتانە هەڵدەبژێردرێن، نەک بە چ ڕیزێک: لیژنەیەکی 3 قوتابی، 4 پرسیار بۆ وەڵامدانەوە لە پەڕەیەک، 3 ڕەنگ بۆ کڕین. لیژنەی ئارام، دیلان و لانا هەمان لیژنەیە، ناوەکان بە هەر ڕیزێک بنووسیت. هەڵبژاردنی وا .

Definitionپێناسە

A selection of objects where order does not matter: ${}^{n}C_{r} = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}$ .

هەڵبژاردنی چەند شتێکە کە ڕیزەکەیان گرنگ نییە: ${}^{n}C_{r} = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}$ .

A combination of $r$ objects from $n$ different objects is a selection made without regard to order.

$r$ شت لە $n$ شتی جیاواز هەڵبژاردنێکە کە ڕیزەکەی لەبەرچاو ناگیرێت.

Buying pastries in the bazaarکڕینی شیرینی لە بازاڕ

You choose 3 kinds of pastry from 5 for a box. The box does not care which kind you pointed at first: it holds the same 3 kinds. But if the shopkeeper lines them up in the window from left to right, the order now shows, and every order is a different window.

لە 5 جۆر شیرینی 3 جۆر بۆ قوتوویەک هەڵدەبژێریت. قوتووەکە گرنگی پێ نادات کام جۆرت یەکەم جار پیشان دا: هەمان 3 جۆری تێدایە. بەڵام گەر دوکاندارەکە لە جامەخانەکەدا لە چەپەوە بۆ ڕاست ڕیزیان بکات، ئێستا ڕیزەکە دەردەکەوێت و هەر ڕیزێک جامەخانەیەکی جیاوازە.

Where the analogy stops workingسنووری ئەم نموونەیە

In real shops you may buy two pieces of the same kind. A combination here chooses different objects, each at most once.

لە دوکانی ڕاستەقینەدا دەکرێت دوو پارچەی هەمان جۆر بکڕیت. لێرەدا شتی جیاواز هەڵدەبژێرێت، هەر یەکەیان تەنها یەک جار.

Quick checkپشکنینی خێراWhich question is about a combination?کام پرسیار دەربارەی ؟How many 4-digit PIN codes can be made from the digits 0–9?چەند کۆدی PINـی 4 ژمارەیی لە ژمارەکانی 0 تا 9 دروست دەبێت؟How many ways can 3 runners finish first, second and third?3 ڕاکەر بە چەند ڕێگا دەتوانن ببنە یەکەم، دووەم و سێیەم؟How many 3-person committees can a class of 20 form?پۆلێکی ⁦20⁩ کەسی چەند لیژنەی 3 کەسی دەتوانێت پێک بهێنێت؟

From permutations to combinations: $60 = 10 \times 3!$ لە گۆڕینەکانەوە بۆ گونجێنەکان: $60 = 10 \times 3!$

Take the five letters A, B, C, D, E. Arranging 3 of them in a row gives $P(5,3) = \frac{5!}{(5-3)!} = 5 \times 4 \times 3 = 60$ arrangements. Now ignore the order. The arrangements ABC, ACB, BAC, BCA, CAB and CBA are all the same group {A, B, C}. Every group of 3 letters can be ordered in $3! = 6$ ways, so the 60 arrangements fall into $60 \div 6 = 10$ groups.

پێنج پیتی A، B، C، D، E وەربگرە. ڕیزکردنی 3 دانەیان لە ڕیزێکدا $P(5,3) = \frac{5!}{(5-3)!} = 5 \times 4 \times 3 = 60$ ڕیزکردن دەدات. ئێستا ڕیزەکە پشتگوێ بخە. ABC، ACB، BAC، BCA، CAB و CBA هەموویان هەمان گرووپی {A، B، C}ن. هەر گرووپێکی 3 پیتی بە $3! = 6$ ڕێگا ڕیز دەکرێت، بۆیە ⁦60⁩ ڕیزکردنەکە دەبنە $60 \div 6 = 10$ گرووپ.

Every combination hides

3!

permutations. Divide the permutations by

3!

to count the combinations.هەر

3!

لە خۆیدا دەشارێتەوە. دابەشی

3!

بکە بۆ ژماردنی .CêIT

The same reasoning works for any $n$ and $r$ : each combination of $r$ objects can be arranged in $r!$ orders, so

هەمان بیرکردنەوە بۆ هەر $n$ و $r$ ـێک کار دەکات: هەر $r$ شت بە $r!$ ڕیز ڕیز دەکرێت، بۆیە

C(n,r) = \binom{n}{r} = \frac{P(n,r)}{r!} = \frac{n!}{r!\,(n-r)!}

Computing $C(n,r)$ without huge numbersژماردنی $C(n,r)$ بەبێ ژمارەی زۆر گەورە

Example (9). How many 3-member committees can be chosen from a class of 20? Writing out $20!$ is not needed: most of it cancels.

نموونەی ⁦(9)⁩. چەند لیژنەی 3 ئەندامی لە پۆلێکی ⁦20⁩ کەسی هەڵدەبژێردرێت؟ پێویست ناکات $20!$ بنووسیت: زۆربەی دەسڕێتەوە.

\binom{20}{3} = \frac{20!}{3!\,17!} = \frac{20 \times 19 \times 18 \times 17!}{3! \times 17!} = \frac{20 \times 19 \times 18}{6} = \frac{6840}{6} = 1140

Is it a selection?هەڵبژاردنە؟
A committee has no first or second member, so order does not matter: use combinations.
لیژنە ئەندامی یەکەم و دووەمی نییە، بۆیە ڕیز گرنگ نییە: بەکاربهێنە.
Find $n$ and $r$ $n$ و $r$ بدۆزەرەوە
$n = 20$ students to choose from, $r = 3$ places on the committee.
$n = 20$ قوتابی کە لێیان هەڵدەبژێردرێت، $r = 3$ شوێن لە لیژنەکەدا.
Cancel, then multiplyبیسڕەوە، پاشان لێک بدە
$\frac{20 \times 19 \times 18}{3 \times 2 \times 1} = 1140$ . Cancel first if you like: $\frac{18}{6} = 3$ , then $20 \times 19 \times 3 = 1140$ .
$\frac{20 \times 19 \times 18}{3 \times 2 \times 1} = 1140$ . گەر پێت باشە پێشتر بیسڕەوە: $\frac{18}{6} = 3$ ، پاشان $20 \times 19 \times 3 = 1140$ .

Two values are worth remembering. $\binom{n}{0} = 1$ : there is exactly one way to choose nothing. $\binom{n}{n} = 1$ : there is exactly one way to take everything. Both follow from the formula because $0! = 1$ (see Why zero factorial is 1).

دوو نرخ شایەنی لەبیرکردنن. $\binom{n}{0} = 1$ : ڕێک یەک ڕێگا هەیە بۆ هەڵنەبژاردنی هیچ. $\binom{n}{n} = 1$ : ڕێک یەک ڕێگا هەیە بۆ وەرگرتنی هەمووی. هەردووکیان لە دێن، چونکە $0! = 1$ (بڕوانە بۆچی $0!$ یەکسانە بە 1).

Choosing $r$ is leaving $n - r$ هەڵبژاردنی $r$ واتە بەجێهێشتنی $n - r$

Choosing which 8 of 10 questions to answer is the same as choosing which 2 to skip: every choice of 8 leaves exactly one set of 2 behind. So

هەڵبژاردنی ئەوەی کام 8 پرسیار لە ⁦10⁩ وەڵام بدەیتەوە هەمان هەڵبژاردنی ئەوەیە کام 2 بەجێ بهێڵیت: هەر هەڵبژاردنێکی 8 دانە ڕێک یەک کۆمەڵەی 2 دانە بەجێ دەهێڵێت. بۆیە

\binom{n}{r} = \binom{n}{n-r} \qquad \binom{10}{8} = \binom{10}{2} = \frac{10 \times 9}{2} = 45

Example (10). An exam paper has two parts, P and Q, with 10 questions each. A student must answer 8 questions from P and 4 from Q. In how many ways can the questions be chosen?

نموونەی ⁦(10)⁩. پەڕەیەکی تاقیکردنەوە دوو بەشی P و Qـی هەیە و هەر بەشێک ⁦10⁩ پرسیاری تێدایە. قوتابی دەبێت 8 پرسیار لە P و 4 پرسیار لە Q وەڵام بداتەوە. بە چەند ڕێگا پرسیارەکان هەڵدەبژێردرێن؟

Two independent choices: count each with a combination, then multiply.دوو هەڵبژاردنی جیا: هەر یەکەیان بە بژمێرە، پاشان لێکیان بدە.CêIT

\binom{10}{8} \cdot \binom{10}{4} = \binom{10}{2} \cdot \binom{10}{4} = 45 \times 210 = 9450

Pascal's triangleسێگۆشەی پاسکاڵ

Write the numbers $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$ in row $n$ , one row under the other, and you get Pascal's triangle. You can build it without any factorials:

ژمارەکانی $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$ لە ڕیزی $n$ ـدا بنووسە، ڕیزێک لە ژێر ڕیزێکی تر، ئەوە دروست دەبێت. بەبێ هیچ دروست دەکرێت:

Pascal's triangle grows from row 0 to row 5. Every row starts and ends with 1; each inside number is the sum of the two above it (1 + 1 = 2, 1 + 2 = 3, 3 + 3 = 6, 6 + 4 = 10). The last frame highlights the two 10s in row 5: C(5,2) = C(5,3) = 10. — Each number is the sum of the two numbers above it.هەر ژمارەیەک کۆی دوو ژمارەکەی سەرەوەیەتی.CêIT

\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} \qquad \binom{5}{3} = \binom{4}{2} + \binom{4}{3} = 6 + 4 = 10

The mathematical secrets of Pascal’s triangle - Wajdi Mohamed RatemiTED-Ed · Englishئینگلیزی · 3.2M viewsبینین · 69K likesلایک
How Pascal's triangle is built by adding the two numbers above, and how its rows give the combination numbers.
چۆن دروست دەکرێت بە کۆکردنەوەی ئەو دوو ژمارەیەی سەرەوە، هەروەها ڕیزەکانی چۆن ژمارەکانی دەدەن.
Building the triangle from 0:36, binomial coefficients from 1:08, patterns and probability uses after that.
دروستکردنی سێگۆشەکە لە ⁦0:36⁩ـەوە، لە ⁦1:08⁩ـەوە، پاشان تایبەتمەندییە سەرنجڕاکێشەکانی و بەکارهێنانی لە .

Pascal's triangleسێگۆشەی پاسکاڵ

What the rows tell youڕیزەکانی سێگۆشەی پاسکاڵ چی دەڵێن

Each row reads the same from both ends: that is $\binom{n}{r} = \binom{n}{n-r}$ .
Row $n$ adds up to $2^n$ (row 5: $1 + 5 + 10 + 10 + 5 + 1 = 32$ ): every object is either in or out of a group. You will use this in Example (12).
Row $n$ also counts coin tosses: in $n$ tosses, $\binom{n}{k}$ of the $2^n$ head–tail sequences have exactly $k$ heads, because you choose which $k$ tosses are heads (3 tosses: HHT, HTH, THH are the $\binom{3}{2} = 3$ ways to get 2 heads). This is where the binomial distribution comes from: Coins.

هەر ڕیزێک لە هەردوو سەرەوە وەک یەک دەخوێنرێتەوە: ئەوە $\binom{n}{r} = \binom{n}{n-r}$ ـە.
کۆی ڕیزی $n$ دەکاتە $2^n$ (ڕیزی 5: $1 + 5 + 10 + 10 + 5 + 1 = 32$ ): هەر شتێک یان لە ناو گرووپەکەدایە یان لە دەرەوە. لە نموونەی ⁦(12)⁩دا بەکاری دەهێنیت.
ڕیزی $n$ هەروەها هەڵدانی دراو دەژمێرێت: لە $n$ هەڵداندا، $\binom{n}{k}$ زنجیرە لە $2^n$ زنجیرەی شێر و خەت ڕێک $k$ شێریان تێدایە، چونکە هەڵدەبژێریت کام $k$ هەڵدان شێر بن (⁦3⁩ هەڵدان: HHT، HTH و THH ئەو $\binom{3}{2} = 3$ ڕێگایەن کە 2 شێر دەدەن). لێرەوە دێت: دراوەکان.

Older than Pascalکۆنتر لە پاسکاڵ

Blaise Pascal wrote about the triangle in 1654, but he was not the first. In Baghdad around the year 1000, al-Karaji gave the general rule for building it (we know it from the later writings of al-Samawal), and a Chinese book by Zhu Shijie printed the triangle in 1303. Some books name it after Omar Khayyam, which is why the Kurdish name «سێگۆشەی خەییام» also appears.

بلێز پاسکاڵ لە ساڵی ⁦1654⁩ دەربارەی ئەم سێگۆشەیە نووسی، بەڵام یەکەم کەس نەبوو. لە بەغدا نزیکەی ساڵی ⁦1000⁩، کەرەجی یاسا گشتییەکەی دروستکردنی نووسی (لە نووسینەکانی دواتری سەمەوئەلەوە دەیزانین) و کتێبێکی چینیی جو شیجیە لە ساڵی ⁦1303⁩ سێگۆشەکەی چاپ کرد. هەندێک کتێب بە ناوی عومەر خەییامەوە ناوی دەنێن، هەر بۆیە ناوی «سێگۆشەی خەییام»ـیش لە کوردیدا بەکاردێت.

Example (8): colour sets or painting plans?نموونەی ⁦(8)⁩: کۆمەڵەی ڕەنگ یان پلانی بۆیاخکردن؟

Example (8) in the notes: three rooms are to be painted, each a different colour, choosing from 7 colours. The notes answer with a combination:

نموونەی ⁦(8)⁩ لە تێبینییەکاندا: سێ ژوور بۆیاخ دەکرێن، هەر یەکەیان بە ڕەنگێکی جیاواز، لە ناو 7 ڕەنگدا. تێبینییەکان بە وەڵام دەدەنەوە:

\binom{7}{3} = \frac{7!}{4!\,3!} = 35

35 counts the colour sets, not the painting plans⁦35⁩ کۆمەڵەی ڕەنگەکان دەژمێرێت، نەک پلانەکانی بۆیاخکردن

35 answers the question "which 3 colours do we buy?". But the rooms are different rooms: blue in the kitchen and green in the bedroom is not the same as green in the kitchen and blue in the bedroom. If the question is "in how many ways can the three rooms be painted?", order matters and the answer is $P(7,3) = 7 \times 6 \times 5 = 210$ . Check: each of the 35 colour sets can be given to the 3 rooms in $3! = 6$ ways, and $35 \times 6 = 210$ .

⁦35⁩ وەڵامی پرسیاری «کام 3 ڕەنگ بکڕین؟»ـە. بەڵام ژوورەکان ژووری جیاوازن: شین بۆ چێشتخانە و سەوز بۆ ژووری نووستن هەمان شت نییە وەک سەوز بۆ چێشتخانە و شین بۆ ژووری نووستن. گەر پرسیارەکە «سێ ژوورەکە بە چەند ڕێگا بۆیاخ دەکرێن؟» بێت، ڕیز گرنگە و وەڵامەکە $P(7,3) = 7 \times 6 \times 5 = 210$ ـە. پشکنین: هەر یەکێک لە ⁦35⁩ کۆمەڵە ڕەنگەکە بە $3! = 6$ ڕێگا بە 3 ژوورەکە دەدرێت و $35 \times 6 = 210$ .

So always ask: does swapping two chosen objects give a different result? If yes, count permutations. If no, count combinations.

کەواتە هەمیشە بپرسە: ئایا ئاڵوگۆڕی دوو شتی هەڵبژێردراو ئەنجامێکی جیاواز دەدات؟ گەر بەڵێ، بژمێرە. گەر نەخێر، بژمێرە.

Committees with conditions: "at least"لیژنە بە مەرجەوە: «لانیکەم»

H.W (1). A class has 9 men and 3 women. (a) How many committees of 4 students can be formed? (b) How many of them contain at least 2 women?

ئەرکی ماڵەوەی ⁦(1)⁩. پۆلێک 9 پیاو و 3 ئافرەتی تێدایە. (أ) چەند لیژنەی 4 قوتابی پێک دێت؟ (ب) چەند دانەیان لانیکەم 2 ئافرەتیان تێدایە؟

(a) Read the question(أ) پرسیارەکە بخوێنەوە
It asks for 4 students, whatever their gender, so add the two groups: $n = 9 + 3 = 12$ . It is a selection, so use combinations, and 4 students are chosen, so $r = 4$ .
داوای 4 قوتابی دەکات، ڕەگەزیان هەرچی بێت، بۆیە دوو گرووپەکە کۆ بکەرەوە: $n = 9 + 3 = 12$ . هەڵبژاردنە، بۆیە بەکاربهێنە و 4 قوتابی هەڵدەبژێردرێن، بۆیە $r = 4$ .
(a) Compute(أ) بیژمێرە
$\binom{12}{4} = \frac{12 \times 11 \times 10 \times 9}{4!} = \frac{11880}{24} = 495$ committees.
$\binom{12}{4} = \frac{12 \times 11 \times 10 \times 9}{4!} = \frac{11880}{24} = 495$ لیژنە.
(b) Split "at least 2" into cases(ب) «لانیکەم 2» بکە بە چەند حاڵەتێک
At least 2 women means exactly 2 or exactly 3. Exactly 2: choose 2 of 3 women and 2 of 9 men, $\binom{3}{2}\binom{9}{2} = 3 \times 36 = 108$ . Exactly 3: $\binom{3}{3}\binom{9}{1} = 9$ . Total $108 + 9 = 117$ .
لانیکەم 2 ئافرەت واتە ڕێک 2 یان ڕێک 3. ڕێک ⁦2: 2⁩ لە 3 ئافرەت و 2 لە 9 پیاو هەڵبژێرە، $\binom{3}{2}\binom{9}{2} = 3 \times 36 = 108$ . ڕێک 3: $\binom{3}{3}\binom{9}{1} = 9$ . کۆ $108 + 9 = 117$ .

Committees with conditions: "at least"لیژنە بە مەرجەوە: «لانیکەم»

Count what you do not wantئەوەی نایەوێت بیژمێرە

(b) Or count what you do not want(ب) یان ئەوەی نایەوێت بیژمێرە
From all 495 committees take away those with no woman, $\binom{9}{4} = 126$ , and those with exactly one, $\binom{3}{1}\binom{9}{3} = 3 \times 84 = 252$ : $495 - 126 - 252 = 117$ .
لە هەموو ⁦495⁩ لیژنەکە ئەو $\binom{9}{4} = 126$ لیژنەیە دەربکە کە هیچ ئافرەتێکیان تێدا نییە. هەروەها ئەو $\binom{3}{1}\binom{9}{3} = 3 \times 84 = 252$ لیژنەیەش دەربکە کە ڕێک یەک ئافرەتیان تێدایە: $495 - 126 - 252 = 117$ .

Both methods give 117; a Python check that lists all 495 committees one by one agrees (see the Python screen). The second method is the complement idea: count the opposite and subtract. It is fastest when the opposite has few cases.

هەردوو ڕێگاکە ⁦117⁩ دەدەن؛ پشکنینێکی Python کە هەموو ⁦495⁩ لیژنەکە یەک یەک دەنووسێت هەمان وەڵام دەدات (بڕوانە شاشەی Python). ڕێگای دووەم بیرۆکەی بەکاردەهێنێت: پێچەوانەکە بژمێرە و لێی دەربکە. کاتێک پێچەوانەکە حاڵەتی کەمی هەبێت خێراترینە.

A tempting wrong answer: 135وەڵامێکی هەڵەی سەرنجڕاکێش: ⁦135⁩

"Pick 2 women first ( $\binom{3}{2} = 3$ ways), then any 2 of the other 10 people ( $\binom{10}{2} = 45$ )" gives $3 \times 45 = 135$ , which is too big. A committee with all 3 women is counted 3 times, once for each pair of women picked "first". Split into exact cases instead.

«سەرەتا 2 ئافرەت هەڵبژێرە ( $\binom{3}{2} = 3$ ڕێگا)، پاشان هەر 2 کەسێک لە ⁦10⁩ کەسەکەی تر ( $\binom{10}{2} = 45$ )» $3 \times 45 = 135$ دەدات کە زۆر گەورەیە. لیژنەیەک کە هەر 3 ئافرەتەکەی تێدایە 3 جار دەژمێردرێت، یەک جار بۆ هەر جووتێک ئافرەت کە «یەکەم» هەڵبژێردراوە. لەبری ئەوە بیکە بە حاڵەتی ڕێک.

Football teams and a basket of ballsتیمی تۆپی پێ و سەبەتەیەک تۆپ

Example (11). 20 boys come to try out for the football team. How many different teams of 11 can be chosen?

نموونەی ⁦(11)⁩. ⁦20⁩ کوڕ بۆ تاقیکردنەوەی تیمی تۆپی پێ دێن. چەند تیمی جیاوازی ⁦11⁩ کەسی هەڵدەبژێردرێت؟

\binom{20}{11} = \frac{20!}{11!\,9!} = \binom{20}{9} = 167\,960

Example (12). A child has 6 numbered balls and throws some of them into a basket. In how many ways can the basket be filled? The notes add up the cases "1 ball, 2 balls, …, 6 balls":

نموونەی ⁦(12)⁩. منداڵێک 6 تۆپی ژمارەداری هەیە و هەندێکیان فڕێ دەداتە ناو سەبەتەیەک. سەبەتەکە بە چەند ڕێگا پڕ دەبێت؟ تێبینییەکان حاڵەتەکانی «1 تۆپ، 2 تۆپ، …، 6 تۆپ» کۆ دەکەنەوە:

\binom{6}{1} + \binom{6}{2} + \binom{6}{3} + \binom{6}{4} + \binom{6}{5} + \binom{6}{6} = 6 + 15 + 20 + 15 + 6 + 1 = 63 = 2^6 - 1

Example (12): state the answer and the meaningنموونەی ⁦(12)⁩: وەڵام و واتاکە بنووسە

The notes leave the sum unevaluated. It is 63, and it counts only which balls end up in the basket, with at least one ball thrown. A quicker way: each of the 6 balls is either in or out, $2^6 = 64$ possibilities, minus the one case where the basket stays empty: $64 - 1 = 63$ . This is row 6 of Pascal's triangle without its first 1.

تێبینییەکان کۆکەیان نەژماردووە. ⁦63⁩ـە و تەنها دەژمێرێت کام تۆپانە دەچنە ناو سەبەتەکە، بە مەرجێک لانیکەم یەک تۆپ فڕێ بدرێت. ڕێگایەکی خێراتر: هەر یەکێک لە 6 تۆپەکە یان لە ناوەوەیە یان لە دەرەوە، $2^6 = 64$ حاڵەت، کەمکردنەوەی تاکە حاڵەتێک کە سەبەتەکە بەتاڵ دەمێنێتەوە: $64 - 1 = 63$ . ئەمەش کۆی ڕیزی 6ی دەدات، بەبێ 1ـی یەکەمی.

Quick checkپشکنینی خێراA cafe offers 5 toppings. How many different pizzas can you order with at least one topping?کافێیەک 5 جۆر زیادەی سەر پیتزا پێشکەش دەکات. چەند پیتزای جیاواز دەتوانیت داوا بکەیت کە لانیکەم یەک زیادەی لەسەر بێت؟

31

31

32

32

120

120

Combinations in probability: the midterm committeeگونجێنەکان لە ئەگەردا: لیژنەکەی تاقیکردنەوەی نیوەی وەرز

When every group of $r$ is equally likely, a probability is "favourable groups ÷ all groups", and combinations count both. Midterm Q2B: you and 3 friends are among 100 people running for a 4-person committee. If the 4 winners are chosen at random, what is the probability that you and your 3 friends win all 4 seats?

کاتێک هەموو گرووپێکی $r$ دانەیی بێت، دەکاتە «گرووپە گونجاوەکان ÷ هەموو گرووپەکان» و هەردووکیان دەژمێرن. پرسیاری ⁦2B⁩ـی تاقیکردنەوەی نیوەی وەرز: تۆ و 3 هاوڕێت لە ناو ⁦100⁩ کەسدان کە بۆ لیژنەیەکی 4 کەسی خۆیان کاندید کردووە. گەر 4 براوەکە بە هەڕەمەکی هەڵبژێردرێن، ئەوە چەندە کە تۆ و 3 هاوڕێکەت هەر 4 کورسییەکە ببەنەوە؟

P = \frac{\binom{4}{4}}{\binom{100}{4}} = \frac{1}{3\,921\,225} \approx 2.55 \times 10^{-7}

Why

4/100

is wrongبۆچی

4/100

هەڵەیە

A student answer was $\frac{4}{100} = 0.04$ . That is the chance that one named person wins some seat ( $\binom{99}{3}/\binom{100}{4} = 4/100$ ). Here all four of you must win at once, which is far less likely: about 1 in 4 million. (The lecturer's handwritten answer prints $C^4_{100}$ ; in the notation of this lesson it is $\binom{100}{4}$ .)

وەڵامی قوتابییەک $\frac{4}{100} = 0.04$ بوو. ئەوە ئەوەیە کە یەک کەسی دیاریکراو کورسییەک ببات ( $\binom{99}{3}/\binom{100}{4} = 4/100$ ). لێرەدا دەبێت هەر چوارتان پێکەوە ببەنەوە کە زۆر کەمتر ڕوو دەدات: نزیکەی 1 لە 4 ملیۆن. (وەڵامە دەستنووسەکەی مامۆستا $C^4_{100}$ دەنووسێت؛ بە نیشانەی ئەم وانەیە $\binom{100}{4}$ ـە.)

The same idea counts mixed groups. A box holds 4 red and 6 blue balls and you take 3 without looking. Let R be the number of red balls you get: $P(R = 2) = \frac{\binom{4}{2}\binom{6}{1}}{\binom{10}{3}} = \frac{6 \times 6}{120} = \frac{3}{10}$ . The homework about defective items in Expected Value uses exactly this count.

هەمان بیرۆکە گرووپی تێکەڵ دەژمێرێت. سندووقێک 4 تۆپی سوور و 6 تۆپی شینی تێدایە و بەبێ سەیرکردن 3 دانە دەردەهێنیت. با R ژمارەی ئەو تۆپە سوورانە بێت کە دەریاندەهێنیت: $P(R = 2) = \frac{\binom{4}{2}\binom{6}{1}}{\binom{10}{3}} = \frac{6 \times 6}{120} = \frac{3}{10}$ . ئەرکی ماڵەوەی کەرەستە بێکەڵکەکان لە نرخی پێشبینیکراو ڕێک ئەم ژماردنە بەکاردەهێنێت.

Quick checkپشکنینی خێراSame box (4 red, 6 blue), take 3. What is the probability that all 3 are red?هەمان سندووق (⁦4⁩ سوور، 6 شین)، 3 دانە دەربهێنە. ئەوە چەندە کە هەر 3 دانەکە سوور بن؟

1/30

1/30

4/10

4/10

1/120

1/120

Combinations in Pythonگونجێنەکان لە Pythonـدا

Python's math module has comb(n, k) and perm(n, k) (since Python 3.8), and itertools.combinations lists the groups themselves. Listing is a good way to check a formula on a small case.

math لە Pythonـدا comb(n, k) و perm(n, k)ـی هەیە (لە ⁦Python 3.8⁩ـەوە) و itertools.combinations خودی گرووپەکان دەنووسێت. نووسینی هەموویان ڕێگایەکی باشە بۆ پشکنینی لەسەر حاڵەتێکی بچووک.

Count, then check by listingبژمێرە، پاشان بە نووسینی هەموویان بیپشکنەcombinations_demo.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from itertools import combinations
from math import comb, perm

letters = "ABCDE"
groups = ["".join(g) for g in combinations(letters, 3)]
print(len(groups), "groups:", groups)
print("perm(5, 3) =", perm(5, 3), "| comb(5, 3) =", comb(5, 3))
print("comb(10, 8) == comb(10, 2):", comb(10, 8) == comb(10, 2))

# H.W 1(b): 9 men and 3 women, committees of 4 with at least 2 women
people = ["M"] * 9 + ["W"] * 3
count = sum(1 for c in combinations(range(12), 4)
            if sum(people[i] == "W" for i in c) >= 2)
print("listed one by one:", count)
print("by formula:", comb(3, 2) * comb(9, 2) + comb(3, 3) * comb(9, 1))

print("committee of 4 from 100:", comb(100, 4))
print(f"P(our 4 win) = 1/{comb(100, 4)} = {1 / comb(100, 4):.2e}")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 5

combinations(letters, 3) produces each group once, in alphabetical order, as a tuple such as ('A', 'B', 'C').

combinations(letters, 3) هەر گرووپێک یەک جار دروست دەکات، بە ڕیزی ئەلفوبێ، وەک وەک ⁦('A', 'B', 'C')⁩.

Lineدێڕی 11-14

Lists all 495 committees of H.W 1 and counts those with at least 2 women: the brute-force check of 117.

هەموو ⁦495⁩ لیژنەکەی ئەرکی ماڵەوەی 1 دەنووسێت و ئەوانە دەژمێرێت کە لانیکەم 2 ئافرەتیان تێدایە: پشکنینی ⁦117⁩ بە ژماردنی هەمووی.

Lineدێڕی 18

:.2e prints the tiny probability in scientific notation.

:.2e زۆر بچووکەکە بە نووسینی زانستی چاپ دەکات.

Python 3.15 and later⁦Python 3.15⁩ و دواتر

Python 3.15 added the module math.integer, and math.comb and math.perm became aliases kept for old code (soft-deprecated). They still work. In new code for 3.15 or later you can write from math.integer import comb, perm. For $k > n$ both return 0, and a negative argument raises ValueError.

⁦Python 3.15⁩ نوێی بە ناوی math.integer زیاد کرد و math.comb و math.perm بوون بە ناوی جێگرەوە کە تەنها بۆ کۆدی کۆن هێڵدراونەتەوە (بە نەرمی کراون). هێشتا کار دەکەن. لە کۆدی نوێدا بۆ ⁦3.15⁩ یان دواتر دەتوانیت بنووسیت from math.integer import comb, perm. بۆ $k > n$ هەردووکیان 0 دەگەڕێننەوە و کە نەرێنی بێت ValueError دەدات.

New to import and loops in Python? See Modules and The for loop.

گەر import و لە Pythonـدا نوێن بۆت، بڕوانە مۆدیوڵەکان و خولی for.

Common mistakesهەڵە باوەکان

Mistakeهەڵە	Why it is wrongبۆچی هەڵەیە	Do this insteadلەبری ئەوە ئەمە بکە
Using $P(n,r)$ for a committee or a hand of objectsبەکارهێنانی $P(n,r)$ بۆ لیژنە یان دەستەیەک شت	Each group is counted $r!$ times, once for every order.هەر گرووپێک $r!$ جار دەژمێردرێت، یەک جار بۆ هەر ڕیزێک.	Ask whether swapping two chosen objects changes the result; if not, use $\binom{n}{r}$ .بپرسە ئایا ئاڵوگۆڕی دوو شتی هەڵبژێردراو ئەنجامەکە دەگۆڕێت؛ گەر نا، $\binom{n}{r}$ بەکاربهێنە.
Using $\binom{n}{r}$ when positions differ (Example 8 with distinct rooms)بەکارهێنانی $\binom{n}{r}$ کاتێک شوێنەکان جیاوازن (نموونەی 8 بە ژووری جیاواز)	Different rooms or posts make the order matter.ژوور یان پۆستی جیاواز ڕیز گرنگ دەکەن.	Count permutations: $P(7,3) = 210$ . بژمێرە: $P(7,3) = 210$ .
"At least 2" as "pick 2, then any others" (135)«لانیکەم 2» وەک «2 هەڵبژێرە، پاشان هەر کەسێکی تر» ⁦(135)⁩	Groups with more than 2 are counted several times.گرووپی زیاتر لە 2 چەند جار دەژمێردرێن.	Add exact cases, or subtract the unwanted cases from the total (117).حاڵەتە ڕێکەکان کۆ بکەرەوە، یان حاڵەتە نەویستراوەکان لە کۆ دەربکە ⁦(117)⁩.
Adding the counts of two groups chosen together (H.W 2: $10 + 35$ )کۆکردنەوەی ژمارەی دوو گرووپ کە پێکەوە هەڵدەبژێردرێن (ئەرکی ماڵەوەی 2: $10 + 35$ )	Both choices happen in the same committee.هەردوو هەڵبژاردن لە هەمان لیژنەدا ڕوو دەدەن.	Multiply: $10 \times 35 = 350$ .لێکیان بدە: $10 \times 35 = 350$ .
Probability of one person's success used for a whole group ( $4/100$ ) سەرکەوتنی یەک کەس بۆ هەموو گرووپێک بەکارهێنراوە ( $4/100$ )	The group must win together.گرووپەکە دەبێت پێکەوە ببەنەوە.	Favourable groups ÷ all groups: $1/\binom{100}{4}$ .گرووپە گونجاوەکان ÷ هەموو گرووپەکان: $1/\binom{100}{4}$ .

Quick checkپشکنینی خێرا5 women and 7 men; a committee needs 2 women and 3 men. Which calculation is right?5 ئافرەت و 7 پیاو؛ لیژنەیەک پێویستی بە 2 ئافرەت و 3 پیاوە. کام ژماردن ڕاستە؟

\binom{5}{2} \times \binom{7}{3}

\binom{5}{2} \times \binom{7}{3}

\binom{12}{5}

\binom{12}{5}

\binom{5}{2} + \binom{7}{3}

\binom{5}{2} + \binom{7}{3}

Exercisesڕاهێنانەکان

ExerciseڕاهێنانH.W (2): two groups in one committeeئەرکی ماڵەوەی ⁦(2)⁩: دوو گرووپ لە یەک لیژنەدا

A club has 5 women and 7 men (12 members). How many committees with 2 women and 3 men can be formed?

یانەیەک 5 ئافرەت و 7 پیاوی هەیە (⁦12⁩ ئەندام). چەند لیژنە بە 2 ئافرەت و 3 پیاو پێک دێت؟

Hintئاماژە

Count the women's choices and the men's choices separately.

هەڵبژاردنی ئافرەتان و هەڵبژاردنی پیاوان جیا جیا بژمێرە.

Show answerوەڵامەکە پیشان بدە

Groupگرووپ	Chooseهەڵبژاردن	Waysڕێگاکان
5 women5 ئافرەت	2 of them (A)2 دانەیان ⁦(A)⁩	$\binom{5}{2} = \frac{5!}{3!\,2!} = 10$
7 men7 پیاو	3 of them (B)3 دانەیان ⁦(B)⁩	$\binom{7}{3} = \frac{7!}{4!\,3!} = 35$
committeeلیژنە	A and B togetherA و B پێکەوە	$10 \times 35 = 350$

Every pair of women can sit with every trio of men, so the counts multiply (the fundamental counting principle): 350 committees.

هەر جووتێک ئافرەت دەتوانن لەگەڵ هەر سێیەکی پیاوان دابنیشن، بۆیە ژمارەکان لێک دەدرێن (): ⁦350⁩ لیژنە.

ExerciseڕاهێنانH.W (3)ئەرکی ماڵەوەی ⁦(3)⁩

How many committees of 5 can be chosen from 8 people?

چەند لیژنەی 5 کەسی لە 8 کەس هەڵدەبژێردرێت؟

Show answerوەڵامەکە پیشان بدە

\binom{8}{5} = \frac{8!}{3!\,5!} = \binom{8}{3} = \frac{8 \times 7 \times 6}{6} = 56

ExerciseڕاهێنانChoosing coursesهەڵبژاردنی وانەکان

A department offers 5 maths electives and 3 programming electives. (a) In how many ways can a student pick 3 electives of any kind? (b) In how many ways can they pick 2 maths and 1 programming elective?

بەشێک 5 وانەی هەڵبژاردەی بیرکاری و 3 وانەی هەڵبژاردەی پێشکەش دەکات. (أ) قوتابییەک بە چەند ڕێگا 3 وانەی هەڵبژاردە لە هەر جۆرێک هەڵدەبژێرێت؟ (ب) بە چەند ڕێگا 2 وانەی بیرکاری و 1 وانەی هەڵدەبژێرێت؟

Show answerوەڵامەکە پیشان بدە

\text{a) } \binom{8}{3} = 56 \qquad \text{b) } \binom{5}{2}\binom{3}{1} = 10 \times 3 = 30

ExerciseڕاهێنانSpot the mistakeهەڵەکە بدۆزەرەوە

A box has 4 red and 6 blue balls. Shilan takes 3 balls at once. With R the number of red balls, she writes $P(R \ge 1) = \frac{C(4,1) \cdot C(9,2)}{C(10,3)} = \frac{4 \times 36}{120} = 1.2$ . What went wrong, and what is the right answer?

سندووقێک 4 تۆپی سوور و 6 تۆپی شینی تێدایە. شیلان 3 تۆپ پێکەوە دەردەهێنێت. با R ژمارەی تۆپە سوورەکان بێت. شیلان دەنووسێت: $P(R \ge 1) = \frac{C(4,1) \cdot C(9,2)}{C(10,3)} = \frac{4 \times 36}{120} = 1.2$ . چی هەڵە بوو و وەڵامی ڕاست چییە؟

Hintئاماژە

What is the opposite of "at least one red"?

پێچەوانەی «لانیکەم یەک سوور» چییە؟

Show answerوەڵامەکە پیشان بدە

A probability can never be more than 1, so something is counted many times. "Pick one red, then any 2 of the other 9" counts a group with 2 or 3 red balls more than once. Use the complement: no red means all 3 blue.

هیچ لە 1 زیاتر نابێت، بۆیە شتێک چەند جار ژمێردراوە. «یەک سوور هەڵبژێرە، پاشان هەر 2 دانەیەک لە 9ـەکەی تر» گرووپێک کە 2 یان 3 تۆپی سووری تێدایە زیاتر لە جارێک دەژمێرێت. بەکاربهێنە: هیچ سوورێک واتە هەر 3 دانەکە شین.

P(R \ge 1) = 1 - P(R = 0) = 1 - \frac{\binom{6}{3}}{\binom{10}{3}} = 1 - \frac{20}{120} = \frac{5}{6}

Summaryپوختە

A combination is a selection where order does not matter; a permutation is an arrangement where it does.
$\binom{n}{r} = \frac{n!}{r!(n-r)!} = \frac{P(n,r)}{r!}$ : every group of $r$ hides $r!$ orders ( $60 = 10 \times 3!$ ).
$\binom{n}{r} = \binom{n}{n-r}$ , $\binom{n}{0} = \binom{n}{n} = 1$ , and Pascal's rule $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ .
Choices from separate groups multiply (9450, 350); "at least" = add exact cases or subtract the unwanted ones (117).
With equally likely groups, the probability is favourable groups ÷ all groups ( $1/\binom{100}{4}$ , not $4/100$ ).

هەڵبژاردنێکە کە ڕیز تێیدا گرنگ نییە؛ ڕیزکردنێکە کە ڕیز تێیدا گرنگە.
$\binom{n}{r} = \frac{n!}{r!(n-r)!} = \frac{P(n,r)}{r!}$ : هەر گرووپێکی $r$ دانەیی $r!$ ڕیز دەشارێتەوە ( $60 = 10 \times 3!$ ).
$\binom{n}{r} = \binom{n}{n-r}$ ، $\binom{n}{0} = \binom{n}{n} = 1$ و یاسای پاسکاڵ $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ .
هەڵبژاردن لە گرووپی جیاواز لێک دەدرێن (⁦9450⁩، ⁦350⁩)؛ «لانیکەم» = حاڵەتە ڕێکەکان کۆ بکەرەوە یان نەویستراوەکان دەربکە ⁦(117)⁩.
بە گرووپی ، بریتییە لە گرووپە گونجاوەکان ÷ هەموو گرووپەکان ( $1/\binom{100}{4}$ ، نەک $4/100$ ).

Review questionsپرسیارەکانی پێداچوونەوە

Why is Example (8)'s 35 not the number of ways to paint the rooms?بۆچی ⁦35⁩ـی نموونەی ⁦(8)⁩ ژمارەی ڕێگاکانی بۆیاخکردنی ژوورەکان نییە؟

35 counts which colours are bought. The rooms are different, so each set can be assigned in $3!$ ways: 210 painting plans.

⁦35⁩ دەژمێرێت کام ڕەنگانە دەکڕدرێن. ژوورەکان جیاوازن، بۆیە هەر کۆمەڵەیەک بە $3!$ ڕێگا دابەش دەکرێت: ⁦210⁩ پلانی بۆیاخکردن.

How do you get 63 in Example (12) in one step?چۆن ⁦63⁩ـی نموونەی ⁦(12)⁩ بە یەک هەنگاو دەدۆزیتەوە؟

Each of 6 balls is in or out: $2^6 = 64$ , minus the empty basket: 63.

هەر یەکێک لە 6 تۆپەکە لە ناوەوەیە یان لە دەرەوە: $2^6 = 64$ ، کەمکردنەوەی سەبەتەی بەتاڵ: ⁦63⁩.

Videoڤیدیۆ

Watch a videoسەیری ڤیدیۆیەک بکە

A video that viewers liked a lot and praised in their comments, chosen for this lesson.ڤیدیۆیەک کە بینەران زۆریان پێ خۆش بووە و لە کۆمێنتەکانیاندا ستایشیان کردووە، بۆ ئەم وانەیە هەڵبژێردراوە.

Combinations made easytecmath · Englishئینگلیزی · 304K viewsبینین · 5K likesلایک
What a combination is (order does not matter) and a quick way to compute nCr by cancelling before you multiply.
چییە (ڕیزبەندی گرنگ نییە) و ڕێگایەکی خێرا بۆ ژماردنی ${}_nC_r$ : پێش لێکدان، ژمارەکان کورت بکەرەوە.
An example from 0:22, the rule at 3:14 and more examples from 5:11; the cancelling shortcut is the method of the "Computing C(n,r)" screen.
نموونەیەک لە ⁦0:22⁩ـەوە، یاساکە لە ⁦3:14⁩ و نموونەی زیاتر لە ⁦5:11⁩ـەوە؛ ڕێگای کورتکردنەوەکە هەمان ڕێگایە کە لە شاشەی «ژماردنی $C(n,r)$ » بەکار دێت.

Lesson complete!وانەکە تەواو بوو!

Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.

Key termsزاراوە سەرەکییەکان

Next lessonوانەی داهاتوو

The Axioms of Probability and the Complement Ruleبەڵگەنەویستەکانی ئەگەر و یاسای تەواوکەر

Related lecturesوانە پەیوەندیدارەکان

References and further readingسەرچاوەکان و خوێندنەوەی زیاتر

This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.

Combinationsگونجێنەکان

What you will learnچی فێر دەبیت

When order does not matterکاتێک ڕیز گرنگ نییە

From permutations to combinations: 60=10×3!60 = 10 \times 3!60=10×3!لە گۆڕینەکانەوە بۆ گونجێنەکان: 60=10×3!60 = 10 \times 3!60=10×3!

Computing C(n,r)C(n,r)C(n,r) without huge numbersژماردنی C(n,r)C(n,r)C(n,r) بەبێ ژمارەی زۆر گەورە

Choosing rrr is leaving n−rn - rn−rهەڵبژاردنی rrr واتە بەجێهێشتنی n−rn - rn−r

Pascal's triangleسێگۆشەی پاسکاڵ

What the rows tell youڕیزەکانی سێگۆشەی پاسکاڵ چی دەڵێن

Example (8): colour sets or painting plans?نموونەی ⁦(8)⁩: کۆمەڵەی ڕەنگ یان پلانی بۆیاخکردن؟

Committees with conditions: "at least"لیژنە بە مەرجەوە: «لانیکەم»

Count what you do not wantئەوەی نایەوێت بیژمێرە

Football teams and a basket of ballsتیمی تۆپی پێ و سەبەتەیەک تۆپ

Combinations in probability: the midterm committeeگونجێنەکان لە ئەگەردا: لیژنەکەی تاقیکردنەوەی نیوەی وەرز

Combinations in Pythonگونجێنەکان لە Pythonـدا

Common mistakesهەڵە باوەکان

Exercisesڕاهێنانەکان

Summaryپوختە

Watch a videoسەیری ڤیدیۆیەک بکە

Lesson complete!وانەکە تەواو بوو!

Key termsزاراوە سەرەکییەکان

Related lecturesوانە پەیوەندیدارەکان

From permutations to combinations: $60 = 10 \times 3!$ لە گۆڕینەکانەوە بۆ گونجێنەکان: $60 = 10 \times 3!$

Computing $C(n,r)$ without huge numbersژماردنی $C(n,r)$ بەبێ ژمارەی زۆر گەورە

Choosing $r$ is leaving $n - r$ هەڵبژاردنی $r$ واتە بەجێهێشتنی $n - r$