شرح التوافيق: عد الاختيارات

Combinations: Counting Selections

يأتي في امتحانات IGCSE Additional Maths 0606

الشرح بالعربية، والرياضيات كما تظهر في ورقة الامتحان بالإنجليزية، لأن الامتحان بالإنجليزية.

1. Choosing, not arranging

إذا اخترت ثلاثة أصدقاء من خمسة للذهاب إلى السينما، فالمجموعة نفسها مهما كان ترتيب أسمائهم؛ الترتيب لا يهم. هذا هو التوافيق، أما التباديل فالترتيب فيه مهم، مثل الصف أو الرمز السري أو الجوائز الأولى والثانية والثالثة. والتوافيق تكون في اختيار فريق أو لجنة أو مجموعة أو أوراق لعب. لعدّ المجموعات نبدأ بما نعرف: نعدّ الترتيبات لثلاثة من الخمسة، لكن كل مجموعة تظهر في هذه القائمة بعدد طرق ترتيب أفرادها الثلاثة، أي مضروب ثلاثة، فنقسم عليه. القاعدة: اسأل نفسك، إذا بدّلت عنصرين من المختارين هل يتغير الجواب؟ إن تغيّر فهي تباديل، وإن لم يتغير فهي توافيق. التوافيق إذن تباديل حُذف منها الترتيب بالقسمة على عدد طرق ترتيب العناصر المختارة.

You pick 3 friends from 5 to come to the cinema. Picking Ali, Badr and Celine is the same group as picking Celine, Ali and Badr. The order does not matter.

Permutation: order matters

Arranging in a line, codes, passwords, numbers, 1st, 2nd and 3rd prizes.

Combination: order does not matter

Choosing a team, a committee, a group, a hand of cards.

Count the groups using what you already know. Arranging 3 of the 5 friends in order gives $^{5} P_{3} = 60$ . But each group of 3 appears in that list $3! = 6$ times, once for each order.

Worked example

1
How many different groups of 3 can be chosen from 5 friends?
2
$^{5} P_{3} = 5 \times 4 \times 3 = 60$ — Ordered lists of 3 friends.
3
$3! = 6$ — Each group appears in 6 different orders.
4
$60 \div 6 = 10$ — So there are 10 different groups.

Rule

Ask: if I swap two of the chosen items, is it a different answer? Yes: permutation. No: combination.

Key idea

A lottery where you choose 6 numbers from 49 has 13 983 816 possible tickets. The order you pick the numbers in does not matter, so it is a combination.

Key idea

A combination is a permutation with the order removed. Divide by the number of ways to order the chosen items.

2. The nCr formula

القسمة على مضروب عدد العناصر المختارة كل مرة تعطي قانون التوافيق: عدد طرق اختيار عدد من العناصر من مجموعة يساوي مضروب عدد عناصر المجموعة، مقسومًا على مضروب عدد المختارين في مضروب عدد المتروكين. هذا القانون مطبوع في كامبريدج ضمن نظرية ذات الحدين، وللآلة الحاسبة زر خاص به في الورقة الثانية. في المثال نختار لجنة من عشرة أشخاص، فيُختصر مضروب المتروكين، وبدون آلة اختصر قبل أن تضرب. وحقيقتان توفّران الوقت: اختيار من تأخذهم هو نفسه اختيار من تتركهم، فالعددان متساويان؛ وهناك طريقة واحدة لاختيار لا شيء وطريقة واحدة لاختيار الكل. الخطأ الشائع استعمال التباديل لفريق أو لجنة؛ الفريق لا ترتيب فيه، فاستخدم التوافيق.

Dividing by $r!$ every time gives the formula for combinations. The number of ways to choose r items from n is written $^{n} C_{r}$ or $(r n)$ .

Formula

^{n} C_{r} = \frac{n !}{r ! ( n - r )!}

$n$ — how many different items there are to choose from.
$r$ — how many you choose.
$r!$ — removes the orders of the chosen items, because order does not matter.

Rule

0606 and 4037 print this formula on the paper, inside the Binomial Theorem, written as $(r n)$ . Your calculator has an nCr key for Paper 2.

Worked example

1
A committee of 4 is chosen from 10 people. How many committees are possible?
2
$^{10} C_{4} = \frac{10 !}{4 ! 6 !}$ — n = 10, r = 4, so n − r = 6.
3
$= \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1}$ — The 6! cancels. Without a calculator, cancel before you multiply.
4
$= 210$ — 5040 ÷ 24 = 210.

Two facts save time. Choosing which r to take is the same as choosing which $n - r$ to leave behind.

Formula

^{n} C_{r} =^{n} C_{n - r}

$n - r$ — the number left out. For example, $^{10} C_{8} =^{10} C_{2} = 45$ .

Formula

^{n} C_{0} =^{n} C_{n} = 1

$0 or n$ — there is one way to choose nothing, and one way to choose everything.

Common mistake

Using $^{n} P_{r}$ for a team or committee. A team has no order, so use $^{n} C_{r}$ .

Key idea

$^{n} C_{r}$ counts groups. Use it whenever swapping two chosen items gives the same answer.

3. Must include, must not include

الشروط تغيّر عدد الأماكن الباقية وعدد من نختار منهم. إذا وجب أن يكون شخص معيّن موجودًا فضعه أولًا، ثم اختر الباقين من الآخرين. وإذا مُنع شخص فأخرجه من المجموعة. وإذا كان الاختيار من مجموعتين فاختر من كل واحدة ثم اضرب. في المثال الأول يأخذ القائد مكانًا، ونُخرج القائد واللاعب المصاب من المجموعة، ثم نختار الباقين. وفي الثاني نختار الأولاد ونختار البنات ونضرب العددين. وإذا كان شخصان يجب أن يكونا معًا أو لا يكونا أبدًا، فاحسب حالة وجودهما معًا وحالة غيابهما معًا ثم اجمع. للتذكّر: «و» تعني الضرب، و«أو» تعني الجمع. غيّر الأعداد أولًا، أي الأماكن الباقية ومن بقي للاختيار، ثم طبّق قانون التوافيق.

Conditions change how many you still need to choose, and from how many.

Steps

1
1. Must include someone: put them in. Choose the rest from the others.
2. Must not include someone: take them out of the pool.
3. Choose from two groups: choose from each group, then multiply.

Worked example

1
A team of 5 is chosen from 12 players. The captain must be in the team, and one injured player cannot be chosen. How many teams are possible?
2
$5 - 1 = 4 places left$ — The captain fills one place.
3
$12 - 2 = 10 players left$ — Remove the captain and the injured player from the pool.
4
$^{10} C_{4} = 210$ — Choose the other 4 from the 10.

Worked example

1
Choose 2 boys from 6 and 3 girls from 5. How many groups are possible?
2
$^{6} C_{2} = 15$ — Ways to choose the boys.
3
$^{5} C_{3} = 10$ — Ways to choose the girls.
4
$15 \times 10 = 150$ — Boys AND girls, so multiply.

Some people must stay together: both in, or both out. Count each case, then add.

Worked example

1
A team of 6 is chosen from 14 people. Two twins must be chosen together or not at all. How many teams are possible?
2
$Both in:^{12} C_{4} = 495$ — The twins take 2 places. Choose 4 more from the other 12.
3
$Both out:^{12} C_{6} = 924$ — Choose all 6 from the other 12.
4
$495 + 924 = 1419$ — One case OR the other, so add.

Memory trick

AND means multiply. OR means add.

Key idea

Change the numbers first: places left to fill, and people left to choose from. Then use $^{n} C_{r}$ .

4. At least: cases or the opposite

عبارة «على الأقل اثنتان» تعني اثنتين أو ثلاثًا أو أكثر حتى الحد الممكن. اكتب كل حالة، واحسب كل واحدة بضرب عدد طرق اختيار النساء في عدد طرق اختيار الرجال، ثم اجمع الحالات. وإذا كثرت الحالات فاحسب العكس: عكس «امرأة واحدة على الأقل» هو «لا نساء أبدًا»، فيكون الجواب العدد الكلي دون شروط ناقص عدد المجموعات التي تخالف الشرط. في المثال الثاني نحسب كل المجموعات من الجميع ثم نطرح المجموعات المكوّنة من رجال فقط. على كل حاصل ضرب صحيح لحالة درجة، فاكتب الحالات بوضوح. الخطأ الشائع أن تختار امرأة أولًا ثم أي أشخاص آخرين، فتُعدّ المجموعة نفسها مرات كثيرة. والخطأ الثاني نسيان حالة، فتحقق أن أعداد كل حالة مجموعها حجم المجموعة.

“At least 2 women” means 2 women, or 3, or 4, and so on. List every case, count each one, then add.

Worked example

1
A group of 5 is chosen from 7 men and 4 women. How many groups have at least 2 women?
2
$2 women, 3 men:^{4} C_{2} \times^{7} C_{3}$ $= 6 \times 35 = 210$ — Choose the women AND the men, so multiply.
3
$3 women, 2 men:^{4} C_{3} \times^{7} C_{2}$ $= 4 \times 21 = 84$ — Same idea for the next case.
4
$4 women, 1 man:^{4} C_{4} \times^{7} C_{1}$ $= 1 \times 7 = 7$ — The last case: every woman is chosen.
5
$210 + 84 + 7 = 301$ — Add the cases.

When there are many cases, count the opposite instead. The opposite of “at least one woman” is “no women at all”.

Formula

at least one = total - none

$total$ — all selections, with no condition.
$none$ — the selections that break the rule.

Worked example

1
Same group of 7 men and 4 women. How many groups of 5 have at least one woman?
2
$^{11} C_{5} = 462$ — All groups of 5 from 11 people.
3
$^{7} C_{5} = 21$ — Groups with no women: all 5 are men.
4
$462 - 21 = 441$ — Total minus none.

The mark scheme gives a mark for each correct case product, or for total minus the opposite. Write each case clearly.

Common mistake

Choosing 1 woman first and then any 4 others: $4 \times^{10} C_{4} = 840$ . This counts the same group many times. A group with two women is counted once for each of them.

Common mistake

Missing a case. Check that the numbers in each case add up to the group size, and that you have every case up to the limit.

Key idea

At least: add the cases. At least one: total minus none.

5. Equations with nCr

بعض الأسئلة تضع التوافيق في معادلة جبرية، غالبًا في الورقة بلا آلة حاسبة. اكتب كل توفيق بالمضروبات ثم اختصر. حقيقتان للاختصار: مضروب عدد يساوي العدد في مضروب العدد الذي قبله، ومضروب العدد مقسومًا على مضروب العدد الأصغر منه باثنين يساوي العدد في العدد الذي قبله. في المثال نكتب الطرفين بالقانون، ونختصر المضروب المشترك، ثم نقسم على العامل المشترك فتبقى معادلة بسيطة. وفي سؤال «بيّن أن» نعمل على الطرف الأيسر وحده: نكتب كل توفيق مختصرًا، ونطرح ونفكّ البسطين حتى نصل إلى الطرف الأيمن. الدرجات على سطر المضروبات ثم الجبر المبسّط ثم الجواب، فاكتب سطر المضروبات قبل الاختصار. الخطأ الشائع اختصار المضروبات كأنها أعداد عادية؛ اكتب البسط حتى تصل إلى مضروب المقام ثم اختصره.

Some questions use $^{n} C_{r}$ in algebra, often on the non-calculator paper. Write each one with factorials, then cancel.

Rule

Two cancelling facts: $(n + 1)! = (n + 1) \times n!$ , and $\frac{n !}{( n - 2 )!} = n (n - 1)$ .

Worked example

1
Find n, given that $^{n + 1} C_{3} = 4 \times^{n} C_{2}$ .
2
$\frac{( n + 1 )!}{3 ! ( n - 2 )!} = 4 \times \frac{n !}{2 ! ( n - 2 )!}$ — Write both sides with the formula.
3
$\frac{( n + 1 ) n ( n - 1 )}{6} = \frac{4 n ( n - 1 )}{2}$ — Cancel (n − 2)! on each side.
4
$\frac{n + 1}{6} = 2$ — Divide both sides by n(n − 1), and 4 ÷ 2 = 2.
5
$n = 11$ — n + 1 = 12.

A “show that” question asks you to prove a result for every n. Work on the left side only until it becomes the right side.

Worked example

1
Show that $^{n + 1} C_{2} -^{n} C_{2} = n$ .
2
$^{n + 1} C_{2} = \frac{( n + 1 ) n}{2}$ — Cancel (n − 1)! from the factorials.
3
$^{n} C_{2} = \frac{n ( n - 1 )}{2}$ — Cancel (n − 2)!.
4
$\frac{n ^{2} + n - n ^{2} + n}{2}$ — Subtract. Expand both tops.
5
$= \frac{2 n}{2} = n$ — As required.

The marks go for the factorial form, then the simplified algebra, then the answer. Show the factorial line before you cancel.

Common mistake

Writing $\frac{n !}{( n - 2 )!} = \frac{n}{n - 2}$ . Factorials do not cancel like that. Write out the top until you reach $(n - 2)!$ : $\frac{n ( n - 1 ) ( n - 2 )!}{( n - 2 )!} = n (n - 1)$ .

Key idea

Write each $^{n} C_{r}$ with factorials, cancel the common part, and solve the ordinary equation that is left.

6. Which method? Read the question

الكلمات تقرّر هل ترتّب أم تختار. «رتّب» أو «في صف» أو رمز أو عدد: تباديل لأن الترتيب مهم. «اختر» أو فريق أو لجنة: توافيق. «يجب أن يشمل» شخصًا: ضعه أولًا واختر الباقين. «يجب ألّا يشمل»: أخرجه من المجموعة. الاختيار من مجموعتين: اختر من كل واحدة ثم اضرب. «معًا أو لا أحد منهما»: حالة وجودهما مع حالة غيابهما، ثم اجمع. «على الأقل اثنان»: اكتب الحالات ثم اجمع. «على الأقل واحد»: الكل ناقص حالة اللاشيء. معادلة فيها توافيق: اكتبها بالمضروبات واختصر ثم حلّ. الخطأ الشائع الخلط بين الاثنين، فاسأل سؤال التبديل في كل مرة: إذا بدّلت عنصرين مختارين ولم يتغير شيء فهي توافيق.

The words decide whether you arrange or choose, and how.

You see	You do
“Arrange”, “in a line”, a code or a number	Permutation: $^{n} P_{r}$
“Choose”, “select”, a team or a committee	Combination: $^{n} C_{r}$
“Must include” someone	Put them in, choose the rest
“Must not include” someone	Remove them from the pool
From two groups	Choose from each, then multiply
“Together or not at all”	Both-in case + both-out case
“At least two”	List the cases, then add
“At least one”	Total minus none
An equation with $^{n} C_{r}$	Factorials, cancel, solve

Common mistake

Mixing the two: using $^{n} P_{r}$ for a selection, or $^{n} C_{r}$ for an arrangement. Ask the swap question every time.

Key idea

If swapping two chosen items makes no difference, it is a combination. Then AND multiplies and OR adds.

تدرّب على التوافيق: عد الاختيارات

أسئلة امتحانات حقيقية تُصحَّح كما يصحّحها الممتحِن، مع شرح بالعربية لكل سؤال.

تدرّب مجاناً على Lemmara

شرح التوافيق: عد الاختيارات

1. Choosing, not arranging

2. The nCr formula

3. Must include, must not include

4. At least: cases or the opposite

5. Equations with nCr

6. Which method? Read the question

تدرّب على التوافيق: عد الاختيارات

أسئلة امتحانات سابقة على التوافيق: عد الاختيارات، محلولة ومشروحة بالعربي