6.5 Generalized Permutations and Combinations

Question 1

Thm 1:

The number of r-permutations of a set with n elements when repetition is allowed is given
in Theorem 1.

Proof?

Answer 1

The number of r-permutations of a set of n objects with repetition allowed is n^r.

Product rule.

Question 2

Theorem 2:

r-combinations from a set with n elements
when repetition of elements is allowed.

proof:

Answer 2

There are C(n + r − 1, r) = C(n + r − 1, n − 1)
r-combinations from a set with n elements
when repetition of elements is allowed.

Question 3

Permutations with Indistinguishable Objects

Thm 3:

Answer 3

The number of different permutations of n objects, where there are n1 indistinguishable objects of type 1, n2 indistinguishable objects of type 2, … , and nk indistinguishable objects of
type k, is
= n! / n1! n2! ⋯ nk!

Question 4

Distinguishable and indistinguishable

Answer 4

The objects can
be either distinguishable,labeled, that is, different from each other, or indistinguishable,unlabeled, that is, considered identical.

Question 5

Closed Formula:

Answer 5

A closed formula is an expression that can be evaluated using a finite number of
operations and that includes numbers, variables, and values of functions, where the operations
and functions belong to a generally accepted set that can depend on the context. In this book, we
include the usual arithmetic operations, rational powers, exponential and logarithmic functions,
trigonometric functions, and the factorial function. We do not allow infinite series to be included
in closed formulae

Question 6

How many ways are there to distribute hands of 5 cards to each of four players from the standard
deck of 52 cards?

Answer 6

The solution to Example 8 equals the number of permutations of 52 objects, with
5 indistinguishable objects of each of four different types, and 32 objects of a fifth type. This
equality can be seen by defining a one-to-one correspondence between permutations of this
type and distributions of cards to the players. To define this correspondence, first order the
cards from 1 to 52. Then cards dealt to the first player correspond to the cards in the positions
assigned to objects of the first type in the permutation. Similarly, cards dealt to the second,
third, and fourth players, respectively, correspond to cards in the positions assigned to objects
of the second, third, and fourth type, respectively. The cards not dealt to any player correspond
to cards in the positions assigned to objects of the fifth type. The reader should verify that this
is a one-to-one correspondence.

Question 7

Theroem 4:

Distribute distinguishable objects in distinguishable boxes:

Solve Example 8 using this:

Answer 7

The number of ways to distribute n distinguishable objects into k distinguishable boxes so
that ni objects are placed into box i, i = 1, 2, … , k, equals
n! / n1! n2! ⋯ nk!

Example 8 is a typical problem that involves distributing distinguishable objects into distinguishable boxes. The distinguishable objects are the 52 cards, and the five distinguishable
boxes are the hands of the four players and the rest of the deck.

Question 8

INDISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES

Answer 8

Counting the number of ways of placing n indistinguishable objects into k distinguishable boxes turns out to be
the same as counting the number of n-combinations for a set with k elements when repetitions
are allowed. The reason behind this is that there is a one-to-one correspondence between n combinations from a set with k elements when repetition is allowed and the ways to place n
indistinguishable balls into k distinguishable boxes. To set up this correspondence, we put a
ball in the ith bin each time the ith element of the set is included in the n-combination.

Question 9

The indistinguishable office example key:

Answer 9

Another way to look at this problem is to look at the number of offices into which we put employees.

Question 10

Stirling numbers of the second kind

Answer 10

Let S(n, j) denote the number of ways to distribute n distinguishable objects into j indistinguishable boxes so that no box is empty. The numbers S(n, j) are called Stirling numbers of the second kind.

Question 11

DISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES

Answer 11

There is no simple closed formula for the number of ways to distribute n distinguishable objects into j indistinguishable boxes. However, there is a formula involving a summation.
We see that the number of ways to distribute n distinguishable objects into k
indistinguishable boxes (where the number of boxes that are nonempty equals k, k − 1, … , 2,
or 1) equals
k
∑j=1 S(n, j).

Question 12

After reading 8.6 formula.

Answer 12

complex, comback

Question 13

Stirling numbers of the first kind

Answer 13

ex 47

Question 14

INDISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES

just what its like, no solution

Answer 14

Observe that distributing n indistinguishable objects into k indistinguishable boxes is the
same as writing n as the sum of at most k positive integers in nonincreasing order.

Question 15

Partition:

Answer 15

If a1 + a2 + ⋯ + aj = n, where a1, a2, … , aj are positive integers with a1 ≥ a2 ≥ ⋯ ≥ aj
, we say that
a1, a2, … , aj is a partition of the positive integer n into j positive integers.

Question 16

Solution to INDISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES using paritions:

Answer 16

We see that if pk(n)
is the number of partitions of n into at most k positive integers, then there are pk(n) ways to
distribute n indistinguishable objects into k indistinguishable boxes.