DM - Generalized Permutations and Combinations: NGUYEN Hoang Thach

DM – Generalized permutations and combinations
NGUYEN Hoang Thach

nhthach@math.ac.vn
23/04/2020
Outline
1 Generalized permutations and combinations

Repeating objects
Identical objects
Balls and boxes
2 Generating permutations and combinations

Generating permutations
Generating combinations
H.-T. Nguyen Generalized permutations and combinations 23/04/2020 2 / 19

Outline

Repeating objects
Identical objects
Balls and boxes


Permutations with repetition
Examples:
The number of different outcomes when two dice are rolled:
6 × 6 = 36.
The number of possible three-letter initials: 263 = 17576.
Theorem
The number of r -permutations of n elements with repetition allowed is nr .
Proof: By the product rule.

Combinations with repetition
Example: Find the number of outcomes when two dice are rolled, if the
order of the results does not matter (ie. (1, 2) and (2, 1) count as one
outcome).
List all possible outcomes and count: 21 outcomes.

Example: Suppose that a cookie shop has four different kinds of cookies.
How many different ways can six cookies be chosen? Assume that only the
type of cookie, and not the individual cookies or the order in which they
are chosen, matters.
If we sort the cookies by kind then arrange them into a row and put a
separator between neighboring kinds, then each way to take the cookies
can be represented as a row of 6 stars and 3 separators. For instance, (2,
1, 1, 2) is represented as follows:
∗ ∗ | ∗ | ∗ | ∗ ∗
Each way to take the cookies corresponds to a way to arrange 6 stars and
3 bars into a row, which corresponds to a choice of the three positions of
the bars out of nine places.
Answer: C (9, 3) = 84.

Theorem
The number of r -combinations of n elements when repetition is allowed is
C (n + r − 1, r ) = C (n + r − 1, n − 1).
Example: Find the number of non-negative integer solutions of the

equation
x1 + x2 + x3 = 11 .
Each solution corresponds to a choice of 11 units from three types. There

are in total C (11 + 3 − 1, 11) = C (13, 11) = 78 ways.

Outline

Repeating objects
Identical objects
Balls and boxes


Permutations with identical objects
Example: How many strings can be made by shuffling the letters of

SUCCESS?
There are two ways to answer the question:

Count the number of permutations of the letters, then divide that
number by the number of duplicates of each string.
Count the number of ways to choose three positions for S out of 7
available positions, then one position for U, then two pisitions for C,
and so on.
7!
Either way, the results is 3!2!1!1! = 420.

Theorem
The number of different permutations of n objects, among which are n1
identical objects of type 1, n2 identical objects of type 2, etc. is
n!
.
n1 !n2 ! . . . nk !
Proof: Consider the following procedure to form such a permutation:

Step 1: Choose n1 positions among the n available positions for the
type 1 objects, there are C (n, n1 ) choices;
Step 2: Choose n2 positions among the n − n1 remaining positions
for the type 2 objects, there are C (n − n1 , n2 ) choice;
...
n!
In total, there are C (n, n1 ) × C (n − n1 , n2 ) × · · · × C (nk , nk ) = n1 !n2 !...nk !
choices.
Outline

Repeating objects
Identical objects
Balls and boxes


Distinguishable balls, distinguishable boxes
Theorem
The number of ways to distribute n distinguishable balls into k
distinguishable boxes so that ni objects are placed into box i, i = 1, 2, ..., k
is
n!
.
n1 !n2 ! . . . nk !
(Note: In this scenario, the number of balls in each box is fixed.)
Example: The number of ways to organize 32 teams in to 8 groups of

32!
four is (4!)8.

Identical balls, distinguishable boxes
The number of ways to put n identical balls into r distinguishable boxes is

the number of combinations with repetitions of r types.
(Note: In this scenario, there is no restriction on the number of balls in
each box.)

Distinguishable balls, identical boxes
Example: How many ways are there to put four different employees into
three indistinguishable offices, when each office can contain any number of
employees?
Answer: 14 ways (list and count).
(4, 0, 0): 1 way.
(3, 1, 0): 4 ways.
(2, 2, 0): 3 ways (why is it not 6?)
(2, 1, 1): 6 ways (why is it not 12?)

In general, the number of ways to put n distinguishable balls into k

identical boxes so that every box is not empty is called the Stirling
numbers of the second kind S(n, k).
A general formula for S(n, k) is:
1 k−1
!
X k
S(n, k) = (−1)i (k − i)n .
k! i=0 i
The number of ways to put n distinguishable balls into k boxes (some of

which may be empty) is
k
X
S(n, j) .
j=1

Example: How many ways are there to put four different employees into
three indistinguishable offices, when each office can contain any number of
employees?
1 non-empty office: S(4, 1) = 1.

Total: 1 + 7 + 6 = 14 ways.

Identical balls, identical boxes
A way to put n identical balls into k identical boxes corresponds to a

partition of n into k positive integers, that is one way to write
n = a1 + a2 + · · · + ak , where ai are positive integers and
a1 ≥ a2 ≥ · · · ≥ ak .
Unfortunately, there is no known closed-form formula for the number of
partitions.

Outline

Repeating objects
Identical objects
Balls and boxes


Outline

Repeating objects
Identical objects
Balls and boxes


DM - Generalized Permutations and Combinations: NGUYEN Hoang Thach

Uploaded by

Copyright:

Available Formats

DM - Generalized Permutations and Combinations: NGUYEN Hoang Thach

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DM - Generalized Permutations and Combinations: NGUYEN Hoang Thach

Uploaded by

Copyright:

Available Formats

DM – Generalized permutations and combinations

NGUYEN Hoang Thach

1 Generalized permutations and combinations

2 Generating permutations and combinations

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 2 / 19

1 Generalized permutations and combinations

2 Generating permutations and combinations

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 3 / 19

Proof: By the product rule.

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 4 / 19

List all possible outcomes and count: 21 outcomes.

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 5 / 19

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 6 / 19

Example: Find the number of non-negative integer solutions of the

Each solution corresponds to a choice of 11 units from three types. There

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 7 / 19

1 Generalized permutations and combinations

2 Generating permutations and combinations

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 8 / 19

Example: How many strings can be made by shuffling the letters of

There are two ways to answer the question:

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 9 / 19

Proof: Consider the following procedure to form such a permutation:

1 Generalized permutations and combinations

2 Generating permutations and combinations

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 11 / 19

(Note: In this scenario, the number of balls in each box is fixed.)

Example: The number of ways to organize 32 teams in to 8 groups of

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 12 / 19

The number of ways to put n identical balls into r distinguishable boxes is

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 13 / 19

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 14 / 19

In general, the number of ways to put n distinguishable balls into k

The number of ways to put n distinguishable balls into k boxes (some of

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 15 / 19

1 non-empty office: S(4, 1) = 1.

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 16 / 19

A way to put n identical balls into k identical boxes corresponds to a

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 17 / 19

1 Generalized permutations and combinations

2 Generating permutations and combinations

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 18 / 19

1 Generalized permutations and combinations

2 Generating permutations and combinations

H.-T. Nguyen Generalized permutations and combinations 23/04/2020 19 / 19

You might also like