AP Notes, Outlines, Study Guides, Vocabulary, Practice Exams and more!

Permutations and Combinations

Permutations and Combinations

A permutation is an ordered arrangement of every or some elements of a set of objects. Order is important in a permutation; therefore, permutations with the same objects in a different order are considered distinct arrangements. Some of the objects in the set, as well in a permutation, may be indistinguishable from one another.

A permutation of n distinct objects taken r at a time is a subset, with r elements, of the n distinct objects. The number of these subsets, denoted by n Pr , is equal to

4probc6

EX. Given the letters A, B, C, D, E, F and G, there are

4probc7

arrangements of these 7 letter taken 4 at a time.

If all n distinct elements of a set are to be arranged, then each arrangement is a permutation of n distinct objects taken n at a time. The number of such permutations is

4probc8

Therefore, the number of permutations of n distinct objects is n!.

EX. There are 3! = 6 ways of using all three digits 1, 2 and 3 in a numeral. Namely, these are 123, 132, 213, 231, 312, and 321.

Circular permutations are ordered arrangements of objects in a circle. While order is still considered, a circular permutation is not considered to be distinct from another unless at least one object is preceded or succeeded by a different object in both permutations. In the set of objects, one object can be fixed, and the other objects can be arranged in different permutations. Thus, the number of permutations of n distinct objects that are arranged in a circle is (n-1) !.

EX. There are (6 - 1)! = 5! = 120 ways to seat 6 persons at a circular dinner table.

If there are identical or indistinguishable objects in the set, then the number of possible permutations in the set will be less than the number of permutations with distinct objects. This is true because permutations that are exactly alike, except that the identical objects have changed positions (e.g. an object switches position with an identical object), are considered to be the same arrangement.

The number of distinct permutations of n objects, of which n1 are of one kind, n2 are of a second kind, ......, nk are of a kth kind, is given by

4probc9

where n1 + n2 + ..... + nk = n

EX. The word TENNESSEE has 4 E's, 2 N's, 2 S's and 1 T. The number of 9-letter permutations that can be created from these set of letters is

4probc10

A partition of n objects into r cells is a division of the n objects into r subsets, such that the intersection of every possible pair of the r subsets is the null space, and the union of all the r subsets is the set of n objects. In this case, the order of the objects within each subset is not important. The number of ways to partition n objects into r cells, with n1 elements in the first call, n2 elements in the second cell, ......, nr elements in the rth cell, is

4probc11

where n1 + n2 + ..... + nr = n

EX. A deck of cards contains 13 clubs, 13 diamonds, 13 hearts and 13 spades, with 52 cards in all. In a game of bridge, 13 cards are dealt to each of 4 persons. The number of ways to deal 52 cards evenly to 4 bridge players is

4probc12

Indeed, card games are really games of chance (and luck too)!

A combination of n distinct objects taken r at a time is a subset of the n objects with r elements. A combination essentially creates a partition of the n r objects in the first cell and (n - r) objects in the second cell. Therefore, the number of combinations of n distinct objects taken r at a time is objects into 2 cells, with

4probc13

EX. In the game of bridge, each of 4 players is dealt 13 cards. The number of 13-card hands that can be dealt from a 52-card deck is

4probc14

Note that unlike a permutation, a combination does not take order into account; two permutations that have the exact same elements are considered the same combination. For each combination of r objects, there are r! ways of arranging the objects in different orders. In fact,

4probc15

This equality states that the number of permutation of n distinct objects taken r at a time is equal to the number of combinations of n distinct objects taken r at a time multiplied by the number of permutations of r objects (taken r at a time).

 

Subject: 
Subject X2: 

Comments

malinova's picture
Weiss01's picture

 The number of such queues of span r is able to follow by filling in the spots one at a time. - buying youtube view

fourth11's picture

I would like to congratulate the persons behind this wonderful blog. You've done a good job. how to buy soundcloud plays buy likes

Need Help?

We hope your visit has been a productive one. If you're having any problems, or would like to give some feedback, we'd love to hear from you.

For general help, questions, and suggestions, try our dedicated support forums.

If you need to contact the Course-Notes.Org web experience team, please use our contact form.

Need Notes?

While we strive to provide the most comprehensive notes for as many high school textbooks as possible, there are certainly going to be some that we miss. Drop us a note and let us know which textbooks you need. Be sure to include which edition of the textbook you are using! If we see enough demand, we'll do whatever we can to get those notes up on the site for you!