Scribd
Upload
3 views4 pages

Generalized Permutations & Combinations

The document discusses permutations and combinations with repetition, illustrating how to count arrangements and selections when elements can be repeated. It provides examples, including the calculation of strings from the English alphabet and the selection of fruit, using the product rule and combinations formula. Additionally, it explains the distribution of cards among players using combinatorial methods.

Uploaded by

xotepav326
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views4 pages

Generalized Permutations & Combinations

The document discusses permutations and combinations with repetition, illustrating how to count arrangements and selections when elements can be repeated. It provides examples, including the calculation of strings from the English alphabet and the selection of fruit, using the product rule and combinations formula. Additionally, it explains the distribution of cards among players using combinatorial methods.

Uploaded by

xotepav326
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Generalized Permutations and Combinations

Permutations with Repetition:

Counting permutations when repetition of elements is allowed can easily be done using the product
rule.

EXAMPLE 1: How many strings of length r can be formed from the uppercase letters of the English
alphabet? Solution: By the product rule, because there are 26 uppercase English letters, and because
each letter can be used repeatedly, we see that there are 26r strings of uppercase English letters of
length r.

Combinations with Repetition

Consider these examples of combinations with repetition of elements allowed.

EXAMPLE 2 How many ways are there to select four pieces of fruit from a bowl containing apples,
oranges, and pears if the order in which the pieces are selected does not matter, only the type of
fruit and not the individual piece matters, and there are at least four pieces of each type of fruit in
the bowl?

Solution: To solve this problem we list all the ways possible to select the fruit.

There are 15 ways:

4 apples 4 oranges 4 pears

3 apples, 1 orange 3 apples, 1 pear 3 oranges, 1 apple 3 oranges, 1 pear


3 pears, 1 apple 3 pears, 1 orange

2 apples, 2 oranges 2 apples, 2 pears 2 oranges, 2 pears

2 apples, 1 orange, 1 pear 2 oranges, 1 apple, 1 pear 2 pears, 1 apple, 1 orange

The solution is the number of 4-combinations with repetition allowed from a three-element set,
{apple, orange, pear}

THEOREM: 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

Note: For the above example, n=3 (verities of fruits), r= 4.

Total number of ways = C (n + r − 1, r) = C (3+4-1,4) =C (6,4) =15.

EXAMPLE: How many solutions does the equation 11 x1 + x2 + x3 = have, where x1 , x2 , and x3 are
nonnegative integers?

Solution: To count the number of solutions, we note that a solution corresponds to a way of
selecting 11 items from a set with three elements so that x1 items of type one, x2 items of type two,
and x3 items of type three are chosen. Hence, the number of solutions is equal to the number of 11-
combinations with repetition allowed from a set with three elements.

It follows that there are C (3 + 11 − 1, 11) = C (13,11) =C (13,2) = 78 solutions.


DISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES

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

Solution: We will use the product rule to solve this problem. To begin, note that the first player can
be dealt 5 cards in C(52, 5) ways. The second player can be dealt 5 cards in C(47, 5) ways, because
only 47 cards are left. The third player can be dealt 5 cards in C(42, 5) ways. Finally, the fourth player
can be dealt 5 cards in C(37, 5) ways.

Hence, the total number of ways to deal four players 5 cards each is C(52,5)C(47,5)C(42,5)C(37,5) =

You might also like