PERMUTATIONS WITH REPETITION

THEOREM 1: The number of r-permutations of a set of n objects with repetitions allowed is n^r.

EXAMPLE 1: How many strings of length n can be formed from the English alphabet? 26ⁿ

COMBINATIONS WITH REPETITION

THEOREM 2: There are C(n+r-1, r)

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

EXAMPLE 5: 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.

Solution: C(4+6-1, 6) = C(9,6) = 84.

TYPE	REPETITION ALLOWED?	FORMULA
r-permutation	No	n!/(n-r)!
r-combination	No	n!/[r!(n-r)!]
r-permutation	Yes	n^r
r-combination	Yes	(n+r-1)!/[r!(n-1)!]

PERMUTATIONS OF SETS WITH INDISTINGUISHABLE OBJECTS

THEOREM 3: The number of different permutations of n objects, where there are n₁ indistinguishable objects of type 1, where there are n₂ indistinguishable objects of type 2,…, and n_k indistinguishable objects of type k, is

n!/[n₁!n₂!….n_k!]

DISTRIBUTING OBJECTS INTO BOXES

THEOREM 4: The number of ways to distribute n distinguishable objects into k distinguishable boxes so that n_i objects are placed into box i, i = 1,2,…,k, equals n!/[n₁!n₂!….n_k!]