Home
Combinatorics

Combinatorics

Combinatorics is a branch of mathematics that deals with counting and arranging objects in a systematic way.

Index

Pigeonhole principle

If {5} objects are placed into {4} boxes, then, of course, at least one box must contain two or more objects.

This idea is generalized as the “pigeonhole principle”:

The pigeonhole principle states that if {n} objects are arranged into {k} groups, where {k < n,} then at least one group must contain two or more objects.

Here, “groups” can mean subsets, containers, categories, or any other way of dividing up objects.

Here are some more examples of the pigeonhole principle:

  1. In a room with {13} people, at least two of them will have their birthdates in the same month.

Reason: If you group people by their birthdate month, there are {12} groups, and there are {13} people to distribute among those {12} groups.

  1. If a group of people all shake hands with each other, there are always two or more people who will shake hands with the same number of people.

Reason: Assume there are {n} people. If you group the people by the number of hands they shake, there are {n-1} groups. (A person cannot shake their own hand.) Therefore, you are placing {n} people into {n-1} groups.

The name “pigeonhole principle” comes from the observation that if {n} pigeons are placed into {n-1} pigeonholes, then at least one pigeonhole must contain two or more pigeons.

More generally, we can say:

If {n} objects are arranged into {k} groups, then at least one group will contain [[ \vphantom{\large {0 \over 0}} \left \lceil {{n} \over {k}} \right \rceil ]] or more objects.

The notation [[ \vphantom{\large {0 \over 0}} \left \lceil {{n} \over {k}} \right \rceil ]] means [[ \vphantom{\large {0 \over 0}} {{n} \over {k}} ]] rounded up to the next higher integer, if it’s not already an integer.

For example, suppose there are exactly {8{,}000{,}000{,}000} people on earth, and that no person has more than {150{,}000} hairs on their head. Therefore, there are at least [[ \vphantom{\Large {0 \over 0}} \left \lceil {{8{,}000{,}000{,}000} \over {150{,}000}} \right \rceil = 53{,}334 ]] people who have the same number of hairs.

Inclusion-exclusion principle: example

Consider the following:

In a sports club with {43} members:

(Note that some members might not play either sport.)

1. How many members play either golf or tennis?

2. How many of the {43} members play neither golf nor tennis?

Inclusion-exclusion principle

We can generalize the result from the previous section to get the inclusion-exclusion principle:

The inclusion-exclusion principle states that the number of objects that satisfy a set of conditions is equal to:

Here’s a problem that can be solved using this principle:

How many integers from {1} to {30} are divisible by either {2,} {3,} or {5?}

This diagram shows how the numbers from {1} to {30} are distributed into these divisibility groups:

To find how many numbers are in any of the three circles, we sum these terms:

{+ 15} of the numbers {1} to {30} are divisible by {2}   (note that {30 / 2 = 15})
{+ 10} of the numbers {1} to {30} are divisible by {3}   (note that {30 / 3 = 10})
{+ \phantom{0} 6} of the numbers {1} to {30} are divisible by {5}   (note that {30 / 5 = 6})
{- \phantom{0} 5} of the numbers {1} to {30} are divisible by {2} and {3}, that is, divisible by {6}
{- \phantom{0} 3} of the numbers {1} to {30} are divisible by {2} and {5}, that is, divisible by {10}
{- \phantom{0} 2} of the numbers {1} to {30} are divisible by {3} and {5}, that is, divisible by {15}
{+ \phantom{0} 1} of the numbers {1} to {30} are divisible by {2}, {3}, and {5}, that is, divisible by {30}

and we find there are a total of {22} numbers between {1} and {30} that are divisible by either {2,} {3,} or {5.}

Exercises (part 1)

  1. Suppose a drawer contains {24} socks: {6} red, {6} white, {6} blue, and {6} green. If you pull socks out of the drawer without looking, what is the minimum number of socks you need to guarantee a pair of the same color?

  2. How many {2}-digit numbers ({00} to {99}) contain the digit {5}?

  3. What is the minimum number of people required to guarantee that at least {3} of them have first names that start with the same letter?

The fundamental counting principle

The fundamental counting principle

If there are {m} ways of making one selection, and {n} ways of making another selection, then there are {m \times n} ways of making both selections together.

Here, we interpret the word “selection” broadly — it can be a choice made by you, or it can be the outcome of an event, such as rolling a pair of dice.

Here’s a typical problem that illustrates this principle:

A car dealership offers you {5} different models of cars, each available in {3} different colors. How many different car-color combinations can you choose from?

Let’s call the {5} models {\lbrace}M1, M2, M3, M4, M5{\rbrace,} and let’s call the {3} colors {\lbrace}C1, C2, C3{\rbrace.}

The following table shows the {3 \mathord{\times} 5 = 15} possible choice combinations you can make:

M1 M2 M3 M4 M5
C1 (M1,C1) (M2,C1) (M3,C1) (M4,C1) (M5,C1)
C2 (M1,C2) (M2,C2) (M3,C2) (M4,C2) (M5,C2)
C3 (M1,C3) (M2,C3) (M3,C3) (M4,C3) (M5,C3)

Selection without replacement

There’s common type of counting problem that assumes selection without replacement.

When we perform selection without replacement, we select objects one at a time from a set, and once an object is selected, it’s no longer available for future selections. We can only choose each object once, and the number of available objects decreases with each choice.

Here’s an example of this type of problem:

There are {3} runners competing against each other in a race. How many different ways can they finish in {1}st, {2}nd, and {3}rd place, assuming no ties?

Here’s how to solve this problem:

A, B, C
A, C, B
B, A, C
B, C, A
C, A, B
C, B, A

Here’s a diagram showing (from left to right) that there’s a choice of {3,} then a choice of {2,} then a choice of {1}:

Selection with replacement

In the previous section, we looked at selection without replacement.

In this section, we’ll look at selection with replacement. Here, objects are selected one at a time from a set, and each selected object continues to be available for future selections.

Here’s an example:

How many different {3}-letter words can we construct using only the letters A, B, and C, if we allow duplicate letters? (For example, “AAB” is a valid word.)

Here’s how to solve this problem:

Comparing this result with the previous section, we find that:

Exercises (part 2)

Here are some exercises that can be solved using the fundamental counting principle:

  1. How many {4}-digit even numbers are there? The number is not allowed to begin with a {0} digit.

  2. There are {7} runners competing in a race. How many different ways can they finish in {1}st, {2}nd, and {3}rd place, assuming no ties?

  3. Every license plate begins with {3} uppercase letters, which are followed by {4} digits. What expression would you enter into a calculator to find the total number of different license plates?

  4. How many different flags designs are possible if the flag must have 3 vertical bars, each of which is either red, white, or blue, and no two adjacent bars are allowed to be the same color?
    (For example, red/red/white is not allowed, but red/white/red is allowed.)

Factorial

In the previous section on selection without replacement, we found that there are {3 \mathord{\times} 2 \mathord{\times} 1 = 6} ways of arranging the letters {\lbrace}A, B, C{\rbrace} in all possible orders:

A, B, C
A, C, B
B, A, C
B, C, A
C, A, B
C, B, A

Let’s generalize this to any number of objects: The number of ways of arranging {n} different objects in all possible orders is:

{n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1}

This result is called “{n} factorial,” and is written as {\text{“}\,n!\,\text{”}.} The factors are usually written in ascending order:

{n! \ = \ 1 \times 2 \times 3 \times \cdots \times (n-2) \times (n-1) \times n}

Factorial: recursive definition

The factorial can also be defined recursively:

{n! \ = \ (n-1)! \times n}

The definition of an operator is recursive if it’s defined in terms of itself. In the above definition, the factorial on the left side of the equation is defined in terms of the factorial on the right side of the equation.

We can derive the recursive definition like this:

{n! \ = \ 1 \times 2 \times 3 \times \cdots \times (n-2) \times (n-1) \times n} (the definition of factorial)
{n! \ = \ } [ { 1 \times 2 \times 3 \times \cdots \times (n-2) \times (n-1) } ] { \mathop{\times} n} (group the first {n-1} factors)
{n! \ = \ (n-1)! \times n} (simplify inside the brackets)

We can use the recursive definition to find a meaningful way to define {0!,} like this:

{n! \ = \ (n-1)! \times n} (given, from above)
[[{{n!} \over n} \ = \ (n-1)!]] (divide both sides by {n})
[[{{1!} \over 1} \ = \ (1-1)!]] (let {n = 1})
[[1 \ = \ 0!]] (simplify)

This result shows us that {0! = 1.}

In general:

{n!} is defined for all integers {n \ge 0.}
{n!} is undefined if {n < 0} or if {n} is not an integer.

Here’s a list of the factorials up to {10!}:

{0! } { \ = \ } {1 } { \ {\LARGE ⤸} \hspace-2pt {\raise 2pt {\times 1}} }
{1! } { \ = \ } {1 } { \ {\LARGE ⤸} \hspace-2pt {\raise 2pt {\times 2}} }
{2! } { \ = \ } {2 } { \ {\LARGE ⤸} \hspace-2pt {\raise 2pt {\times 3}} }
{3! } { \ = \ } {6 } { \ {\LARGE ⤸} \hspace-2pt {\raise 2pt {\times 4}} }
{4! } { \ = \ } {24 } { \ {\LARGE ⤸} \hspace-2pt {\raise 2pt {\times 5}} }
{5! } { \ = \ } {120 } { \ {\LARGE ⤸} \hspace-2pt {\raise 2pt {\times 6}} }
{6! } { \ = \ } {720 } { \ {\LARGE ⤸} \hspace-2pt {\raise 2pt {\times 7}} }
{7! } { \ = \ } {5{,}040 } { \ {\LARGE ⤸} \hspace-2pt {\raise 2pt {\times 8}} }
{8! } { \ = \ } {40{,}320 } { \ {\LARGE ⤸} \hspace-2pt {\raise 2pt {\times 9}} }
{9! } { \ = \ } {362{,}880 } { \ {\LARGE ⤸} \hspace-2pt {\raise 2pt {\times 10}}}
{10!} { \ = \ } {3{,}628{,}800 } { \phantom { \ {\LARGE ⤸} \hspace-2pt {\raise 2pt {\times 11}}}}

On the right side, you can see how the factorials are the result of a cascading pattern of products starting from {0! = 1.}

Factorial: arithmetic examples

Here are two examples that show how factorial expressions can be simplified or converted to different forms.

1.

2.

Permutation

In a previous section, we found that:

The number of ways of arranging {n} different objects in all possible orders is:

{n! \ = \ 1 \times 2 \times 3 \times \cdots \times (n-2) \times (n-1) \times n}

Each individual arrangement of the objects is called a permutation.

For example, here are all {4!} permutations of the digits {\lbrace 1, 2, 3, 4 \rbrace}:

{1234}   {1243}   {1324}   {1342}   {1423}   {1432}
{2134}   {2143}   {2314}   {2341}   {2413}   {2431}
{3124}   {3142}   {3214}   {3241}   {3412}   {3421}
{4123}   {4132}   {4213}   {4231}   {4312}   {4321}
{ \left. \vphantom { \begin{array} . \\[24pt] . \end{array} } \hspace+4pt \right\rbrace \hspace+2pt } the {24} permutations of {\lbrace 1, 2, 3, 4 \rbrace}

In this example, each object is a digit. But, in general, the objects could be anything, such as letters or names or physical objects. For example, recall that we had previously used the letters {\lbrace}A, B, C{\rbrace} as objects, and we found that they have {3! = 6} permutations:

ABC   ACB
BAC   BCA
CAB   CBA 		{ \left. \vphantom { \begin{array} . \\[10pt] . \end{array} } \hspace+4pt \right\rbrace \hspace+2pt } the {6} permutations of {\lbrace}A, B, C{\rbrace}

The number of permutations is {n!} only if each object has a unique identity. For example, if we wanted to count all the permutations of the {4} letters in the word “TREE”, the result would not be {4!,} because we would be unable to tell the difference between the two “E” letters.

Permutation: general case

The number of objects in a permutation is not required to be the same as the total number of objects that we can choose from.

For example, if you have {4} objects, you can create a permutation from just {2} of them. We can illustrate this by listing of all of the {2}-digit permutations that can be constructed from the digits {\lbrace 1, 2, 3, 4 \rbrace}:

{ \left. \begin{array}{lll} 12 & 13 & 14 \cr 21 & 23 & 24 \cr 31 & 32 & 34 \cr 41 & 42 & 43 \cr \end{array} \hspace+4pt \right\rbrace \hspace+2pt } the {12\,} {2}-digit permutations of {\lbrace 1, 2, 3, 4 \rbrace}

Notice the following:

Permutation: counting the general case

In the previous section, we listed all the {2}-digit permutations that can be constructed from the digits {\lbrace 1, 2, 3, 4 \rbrace}. We found that there were {4 \mathord{\times} 3 = 12} such permutations.

Expressing this more generally, we can ask:

How many permutations are there of {k} objects that are chosen from a set of {n} objects?

We can answer this with the fundamental counting principle, using selection without replacement:

{ \underbrace{ n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) {\vphantom{\Large 0}} } _ {\large k \text{ factors }} }

which can be simplified like this:

[[ n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) ]] (given)
[[ {n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) \times (n-k)!} \over {(n-k)!} ]] (multiply by [[ {(n-k)!} \over {(n-k)!} ]])
[[ {n!} \over {(n-k)!} ]] (simplify the numerator)

We use the notation {P(n,k)} as shorthand for this. So we can say:

The number of permutations of {k} objects that are chosen from a set of {n} objects is:

[[ P(n,k) = {{n!} \over {(n-k)!}} ]]   for {0 \le k \le n}
There are several common ways of describing this:

The notation {P(n,k)} is also sometimes written as { \, _ {\Large \lower 2pt {n}} P _ {\Large k} \, } or { \, ^ {\Large n} P _ {\Large k} \, . }

Exercises (part 3)

  1. What expression would you enter into a calculator to find how many {7}-digit numbers there are that contain no duplicate digits? The number is allowed to begin with {0} digit.

  2. What expression would you use if the number is not allowed to begin with a {0} digit?

Permutation: duplicates

In a previous section, we observed that there are {n!} permutations of {n} objects, but only if each object has a unique identity.

For example, the {4} letters in the word { \hspace+1pt \text{“} \text{T} \hspace+1pt \text{R} \hspace+2pt \text{E} \hspace+2pt \text{E} \hspace+1pt \text{”} } cannot be arranged in {4!} different permutations, because we’re unable to tell the difference between the two {\text{“E”}} letters.

To analyze this case further, let’s look instead at the permutations of the word { \hspace+1pt \text{“} \text{T} \hspace+1pt \text{R} \hspace+1pt \boxed{\text{E}} \hspace+1pt \text{E} \hspace+1pt \text{”} }, where one of the duplicate letters has been specially marked with a box. We can now tell the difference between all the letters, so we now have {4! = 24} permutations:

Let’s now remove the box around each {{\raise 3pt \text{“}} \hspace+1pt \boxed{\text{E}} \hspace+1pt {\raise 3pt \text{”}}}. This eliminates our ability to tell the difference between the two {\text{“E”}} letters, which causes every permutation to be duplicated. Here, we can see all the duplicates grouped together in pairs:

If we eliminate all the duplicates, the number of permutations will be cut in half. The reason it’s cut in half is because the two {\text{“E”}} letters have {2! = 2} possible permutations, which we can’t tell apart anymore. So the number of permutations of the letters in the word { \hspace+1pt \text{“} \text{T} \hspace+1pt \text{R} \hspace+2pt \text{E} \hspace+2pt \text{E} \hspace+1pt \text{”} } is:

[[ {{4!} \over {2!}} \ = \ {{24} \over {2}} \ = \ 12 ]]

We can generalize this result by saying:

The number of permutations of {n} objects in which {k} of them are duplicates of each other (and the rest are distinct) is:

[[ {{n!} \over {k!}} ]]

Permutation: multiple duplicates

In the previous section, we looked at the number of permutations of {n} objects, where one of the objects has {k} duplicates.

Let’s now look at the case where there are several objects that have duplicates.

The letters in the word { \hspace+1pt \text{“} \text{M} \hspace+1pt \text{I} \hspace+1pt \text{S} \hspace+1pt \text{S} \hspace+1pt \text{I} \hspace+1pt \text{S} \hspace+1pt \text{S} \hspace+1pt \text{I} \hspace+1pt \text{P} \hspace+1pt \text{P} \hspace+1pt \text{I} \hspace+1pt \text{”} } have these duplicates:

First, let’s give unique identities to each letter by attaching a subscript number to the duplicates:

{ \hspace+1pt \text{“} \text{M} \hspace+3pt \text{I} _ {\large 1} \hspace+2pt \text{S} _ {\large 1} \hspace+2pt \text{S} _ {\large 2} \hspace+2pt \text{I} _ {\large 2} \hspace+2pt \text{S} _ {\large 3} \hspace+2pt \text{S} _ {\large 4} \hspace+2pt \text{I} _ {\large 3} \hspace+2pt \text{P} _ {\large 1} \hspace+2pt \text{P} _ {\large 2} \hspace+2pt \text{I} _ {\large 4} \hspace+1pt \text{”} }

Now that all the letters are all distinct, we can arrange them in {11! = 39{,}916{,}800} permutations.

Let’s now remove the subscripts — this will cause many duplicate permutations, which must all be eliminated. Here’s how this affects the number of permutations:

Performing these reductions, we get the following result:

The number of permutations of the letters of the word { \hspace+1pt \text{“} \text{M} \hspace+1pt \text{I} \hspace+1pt \text{S} \hspace+1pt \text{S} \hspace+1pt \text{I} \hspace+1pt \text{S} \hspace+1pt \text{S} \hspace+1pt \text{I} \hspace+1pt \text{P} \hspace+1pt \text{P} \hspace+1pt \text{I} \hspace+1pt \text{”} } is:

[[ { {11!} \over { 2! \hspace+2pt 4! \hspace+2pt 4! \hspace+2pt 1! \hspace+2pt } } \ = \ { {39{,}916{,}800} \over {2 \times 24 \times 24 \times 1} } \ = \ { {39{,}916{,}800} \over {1{,}152} } \ = \ { 34{,}650 } ]]

We can generalize this result by saying:

The number of permutations of {n} objects in which:
{\raise 1pt \scriptsize \bullet \ } one type of object has {k_{\large 1}} duplicates
{\raise 1pt \scriptsize \bullet \ } another type of object has {k_{\large 2}} duplicates
{\raise 1pt \scriptsize \bullet \ } another type of object has {k_{\large 3}} duplicates
{ \phantom{\scriptsize \bullet} \ } {\cdots}
{\raise 1pt \scriptsize \bullet \ } another type of object has {k_{\large m}} duplicates
is:

[[ { {n!} \over { k_{\large 1}! \hspace+3pt k_{\large 2}! \hspace+3pt k_{\large 3}! \hspace+3pt \cdots \hspace+3pt k_{\large m}! } } ]]

where:

{ k_{\large 1} + k_{\large 2} + k_{\large 3} + \cdots + k_{\large m} \ = \ n }

This expression is sometimes written using the following notation:

[[ { \binom {n} { k_{\large 1}, \hspace+2pt k_{\large 2}, \hspace+2pt k_{\large 3}, \hspace+2pt \cdots, \hspace+2pt k_{\large m} } } \ = \ { {n!} \over { k_{\large 1}! \hspace+3pt k_{\large 2}! \hspace+3pt k_{\large 3}! \hspace+3pt \cdots \hspace+3pt k_{\large m}! } } ]]

Circular permutation

In a circular permutation, we place the objects in a circle, instead of in a straight line.

For example, we know that there are {3! = 6} linear permutations of {\lbrace}A, B, C{\rbrace}:

A, B, C
A, C, B
B, A, C
B, C, A
C, A, B
C, B, A
 { \left. \vphantom { \begin{array} . \\[48pt] . \end{array} } \hspace+4pt \right\rbrace \hspace+2pt } the {6} linear permutations of {\lbrace}A, B, C{\rbrace}

If we arrange these {6} permutations in a circle, they look like this:


{ \raise 8pt {\underbrace{\hspace+200px}} }
rotationally equivalent

{ \raise 8pt {\underbrace{\hspace+200px}} }
rotationally equivalent

Notice that they form two groups of rotationally equivalent arrangements.

In a circular permutation, all arrangements that are rotationally equivalent are considered to be the same permutation. That’s because a circle doesn’t have a start or end point, so there’s no way to identify where a permutation “starts” on the circle.

Because of rotational equivalence, there are really only two circular permutations of {\lbrace}A, B, C{\rbrace}. Here they are, listed with the linear permutations that are contained within them:

1: 
 contains “ABC”, “BCA”, and “CAB”, going clockwise
2: 
 contains “ACB”, “CBA”, and “BAC”, going clockwise

In general, every circular permutation of {n} distinct objects contains {n} different linear permutations inside it, provided that you always go around the circle in the same direction.

This means that the number of linear permutations is {n} times larger than the number of circular permutations. That’s because any of the {n} objects in a circular permutation could serve as the start of a linear permutation,

Therefore, for {n} distinct objects, the number of circular permutations is { {\Large{{n!} \over {n}}} .} Rewriting this equivalently as {(n-1)!,} we get the following rule:

There are {(n-1)!} circular permutations of a set of {n} objects.

Exercises (part 4)

  1. You have {2} red marbles, {2} white marbles, and {2} blue marbles. There’s no way to tell the difference between two marbles of the same color. How many different ways can they all be arranged in a line?

  2. How many circular permutations are there that consist of exactly {4} letters out of the set {\lbrace \text{A, B, C, D, E, F} \rbrace,} where no letters are duplicated?

Combination

In a previous section, we introduced {P(n,k)}:

The number of permutations of {k} objects that are chosen from a set of {n} objects is:

[[ P(n,k) = {{n!} \over {(n-k)!}} ]]   for {0 \le k \le n}

In this section, we’ll look at a closely related question:

How many subsets of {k} objects can be chosen from a set of {n} objects, assuming the order of the objects doesn’t matter?

For example, let’s list all the subsets of {3} letters that we can choose from the set {\lbrace}A, B, C, D, E{\rbrace}, where the order doesn’t matter:

{\lbrace}A, B, C{\rbrace}
{\lbrace}A, B, D{\rbrace}
{\lbrace}A, B, E{\rbrace}
{\lbrace}A, C, D{\rbrace}
{\lbrace}A, C, E{\rbrace}
{\lbrace}A, D, E{\rbrace}
{\lbrace}B, C, D{\rbrace}
{\lbrace}B, C, E{\rbrace}
{\lbrace}B, D, E{\rbrace}
{\lbrace}C, D, E{\rbrace}
 { \left. \vphantom { \begin{array} . \\[100pt] . \end{array} } \hspace+4pt \right\rbrace \hspace+2pt } the {10} size-{3} subsets of {\lbrace}A, B, C, D, E{\rbrace}

How do we determine that there are {10} subsets in this case?

First, let’s observe that the number of permutations of {3} objects chosen from a set of {5} objects is {P(5,3) = 5 \mathord{\times} 4 \mathord{\times} 3 = 60.}

However, the above list doesn’t contain permutations — it contains combinations:

A combination is an unordered subset of objects that are chosen from a particular set.

Looking again at the {10} combinations:

{\lbrace}A, B, C{\rbrace}  {\lbrace}A, B, D{\rbrace}  {\lbrace}A, B, E{\rbrace}  {\lbrace}A, C, D{\rbrace}  {\lbrace}A, C, E{\rbrace} {\lbrace}A, D, E{\rbrace}  {\lbrace}B, C, D{\rbrace}  {\lbrace}B, C, E{\rbrace}  {\lbrace}B, D, E{\rbrace}  {\lbrace}C, D, E{\rbrace}

Notice the following:

  1. None of the {10} combinations are permutations of each other. That’s because they each contain a unique subset of letters.

  2. Each of the {10} combinations can be arranged into {3!} permutations. For example, the letters in the first combination {\lbrace}A, B, C{\rbrace} can be arranged in these {3!} different ways: ABC, ACB, BAC, BCA, CAB, and CBA.

These observations show us that if we count the number of permutations, it produces an “overcount” of the number of combinations by a factor of {3!.} If we correct for this “overcount”, we can find the number of combinations:

[[ {{P(5,3)} \over {3!}} \ \ = \ \ {{5!} \over {(5-3)!}} \times {{1} \over {3!}} \ \ = \ \ { {120} \over {2} } \times {{1} \over {6}} \ \ = \ \ 10 ]] combinations

In general:

The number of {k}-sized subsets that can be chosen from a set of {n} objects, where the order doesn’t matter, is:

[[ { {P(n,k)} \over {k!} } \ = \ ]]
the number of {k}-sized permutations of {n} objects
the number of permutations of each {k}-sized subset

Expanding this out, we get:

[[ { {P(n,k)} \over {k!} } \ = \ {{n!} \over {(n-k)!}} \times {{1} \over {k!}} \ = \ {{n!} \over {k! \hspace+1pt (n-k)!}} ]]   for {0 \le k \le n}

This formula is used often enough that it has a special notation:

The number of {k}-sized subsets that can be chosen from a set of {n} objects, where the order doesn’t matter, is:

[[ { {C(n,k)} } \ = \ {{n!} \over {k! \hspace+1pt (n-k)!}} ]]   for {0 \le k \le n}

It’s very common to use this notation as well:

[[ \binom{n}{k} \ = \ {{n!} \over {k! \hspace+1pt (n-k)!}} ]]   for {0 \le k \le n}
There are several common ways of describing this:

The notation {C(n,k)} is also sometimes written as { \, _ {\Large \lower 2pt {n}} C _ {\Large k} \, } or { \, ^ {\Large n} C _ {\Large k} \, . }

A common way to pronounce both {C(n,k)} and [[ \binom{n}{k} ]] is “{n} choose {k}”.

Exercises (part 5)

  1. A standard deck of playing cards contains {52} cards. A poker hand is created by choosing {5} of the cards at random. What expression would you enter into a calculator to find how many different poker hands are possible, assuming the order of the cards doesn’t matter?

  2. A group of {10} people attend a meeting, and every person shakes hands with every other person in the group. How many total handshakes occur?

Derangement

A derangement is a permutation in which no object is in its original position.

For example, the {9} derangements of {\lbrace 1, 2, 3, 4 \rbrace} are:

{ \left. \begin{array}{lll} 2143 & 2341 & 2413 \cr 3142 & 3412 & 3421 \cr 4123 & 4312 & 4321 \cr \end{array} \hspace+4pt \right\rbrace \hspace+2pt } the {9} derangements of {\lbrace 1, 2, 3, 4 \rbrace}

In general:

The number of derangements of a set of size {n} is:

[[ D_n = n! \left( 1 - {{1} \over {1!}} + {{1} \over {2!}} - {{1} \over {3!}} + \cdots + {{(-1)^n} \over {n!}} \right) ]]

Here’s an alternative definition that can be easier to calculate:

The number of derangements of a set of size {n \ge 1} is:

[[ D_n = {{n!} \over {e}} ]] rounded to the nearest integer

where:

{e \approx 2.718281828459045}

Review exercises

  1. Suppose a drawer contains {6} socks: {1} red, {2} blue, and {3} white. If you pull socks out of the drawer without looking, what is the minimum number of socks you need to guarantee a pair of the same color?

  2. How many different {3}-letter words can you make from the letters { \lbrace \text{A, B, C, D, E} \rbrace ?} Letters may be repeated — for example, { \text{“CCB”} } is a valid word.

  3. How many {4}-digit numbers are a multiple of {5}? The number is not allowed to begin with a {0} digit, so consider only the numbers between {1000} and {9999.}

  4. There are {5} runners competing in a race. How many different ways can they finish in {1}st, {2}nd, and {3}rd place, assuming no ties?

  5. How many {3}-digit numbers there are that contain no duplicate digits? The number is not allowed to begin with {0} digit, so consider only the numbers between {100} and {999.}

  6. How many different ways are there to arrange four marbles in a row? Each marble is a different color.

  7. How many permutations are there of the letters in the word “APPLE”?
    (Swapping the two “P” letters does not count as a separate permutation.)

  8. You have {3} red marbles and {3} blue marbles. How many different ways can they all be arranged in a line? There’s no way to tell the difference between two marbles of the same color.

  9. How many ways are there to seat {5} people around a circular table?
    If one arrangement is merely a rotation of another arrangement, it doesn’t count as a separate arrangement.

  10. How many circular permutations are there that consist of exactly {4} letters out of the set { \lbrace \text{A},\text{B},\text{C},\text{D},\text{E},\text{F} \rbrace }, where no letters are duplicated?

  11. In a group of {20} people, {12} people like pizza, {9} people like burgers, and {7} people like both pizza and burgers. How many people don’t like either pizza or burgers?

  12. How many two-digit numbers from {00} to {99} contain either the digits {8} or {9}?

  13. How many three-digit numbers from {000} to {999} contain the digit {5}?