Overview

This chapter will look at situations where you want to know the total number of possible combinations of any size that you could choose from a given number of items, where some may be identical.

Diction

• Total set of items is referred to as ‘n’.

• Items being chosen from a set are referred to as ‘r’.

• A null set of items is a set that has no elements.(ie. 6C0=1)

-Retain the null set when the question implies that no object at all can also be selected or states: up to, maximum of…
- Remove the null set when the question implies that some objects (at least 1) have to be selected.

· When using combinations you can:

1. Choose a specific number of objects ‘r’ from the set ‘n’.
2. Choose a different ‘r’ in each case.

-Use cases in questions with terminology like:

-Either/or
- At least 1,
-1 or more
-2 or more
- Minimum of
- Maximum of
- Up to

• The terminology has a great importance in getting an answer correct or incorrect. Pay attention to it.

Formula

1. Combination notation nCr--> = n! (see example 2 and flowchart)

(n-r)!r!
2. Combinations in which some items are identical
§ (p+1) (q+1) (s+1) …-1 [to remove the null set] (see example 3)
§ (p+1) (q+1) (s+1) … [to include the null set] (see example 3)
3. Not choosing exactly ‘r’ objects, all distinct objects and including the null set: (2^n)
4. Not choosing exactly ‘r’ objects, all distinct objects and excluding the null set: (2^n) -1
5. Not choosing exactly ‘r’ objects, all distinct objects and at least 2 objects are selected: (2^n)- nCr = (2^n) – (nCr0+nCr1+…+ nCri)


NOTE: 2^n = 2 to the power of n

Combinations Lesson (Flowchart)

Examples

Example 1. Using exactly r objects, with identical items.

Problem - If you are dealing from a standard deck of 52 cards, how many 53 card hands could have at least one spade? Solution - recall from the flowchart, we use Cases.
Solution-

Step 1- Write out the cases.

Case 1: Only one spade from 13 spades, fourtwo other cards from remaining 39 cards.
Case 2: Two spades from 13 spades, threeone other cardscard from remaining 39 cards.
Case 3: Three spades from 13 spades, twozero other cards from remaining 39 cards.
Case 5: All five spades from 13 spades, no other cards. Step 2 - Use Additive counting principle (ACP)

1287 +
279 885633 + 211 9263042 + 712 842286 += 1 069 26312 961= 2 023 203

Therefore there are 2 02312 203961 combinations possible of dealing a 53 card hand from 52 cards and deal out at least 1 spade.

**this can be done with a 5 card hand. Just use the 3 card hand as a simpler model.**


Example 2. Using exactly ‘r’ objects, with no identical objects.

Problem - In how many ways can a 4 colors be drawn from a pack of 24 pencil crayons?
Solution - Recall from the flow chart, we use the formula nCr = n!

(n-r)!r!

n=24; r=4

Way1-performed using a calculator	Way 2-calculated by hand
nCr	= n! (n-r)!r!
= 24C4	= 24! (24-4)! 4!
= 10 626 ways	= 24! 20!4!
	= 10 626 ways

Either way there are 10 626 ways of drawing 4 pencils from a pack of 24 pencil crayons.


Example 3. Not using exactly ‘r’ objects, but with some identical objects.

Problem - How many sums of money can i make with 1 penny, 2 nickles and 1 dime .
Solution - Recall from flow chart we use the formula

Step 1 -

• Let p represent the number of pennies
• Let q represent the number of nickles
• Let s represent the number of dimes

Step 2 -
Lets substitute values into (p+1)*(q+1)*(s+1)

Step 3 -
= (1+1)*(2+1)*(1+1)
= (2)*(3)*(2)
=12

Since a combination of money is required, the null set cannot be used. [ (p+1)(q+1)(s+1) …-1 ]

Step 4 -
=12-1
=11

Therefore 11 sums of money can be made.


Example 4. Not using exactly ‘r’ objects and with no identical objects.

Problem - The school band consists of 11 members. In how many ways can a committee of at least one member be formed from the school band?
Solution - Recall from the flow chart, the formula (2^n)-1

n=11
2^11-1
= (2x2x2x2x2x2x2x2x2x2x2) -1
=2048 - 1
= 2047

Therefore 2047 committees can be formed from the group of 11 band members with at least one member on a committee.

References

Canton, Barbara J., Erdman, Wayne, Irvine, Jeff, Lim, Louis, Mclaren, Fran, Meisel,

Roland W., Miller, David T., Speijer, Jacob. (2002). Mathematics of Data
Management. Toronto: McGraw - Hill.

(2006, July 7). Combinations Flowchart. Retrieved 2006, Nov 18 from