Suppose S is a set with s elements. We often need to know how many k-element ordered subsets or k-sequences or arrangements of size k can be chosen from S.

This number is denoted P(s,k). For example, if S is the three-element set {x,y,z}, the possible two-element ordered subsets are xy,yx,xz,zx,yz and zx; so P(3,2) = 6.

In particular P(s,s) denotes the number of s-sequences that can be chosen from an s-set, or the number of arrangements of the set S. But these are precisely the permutations of S. It follows that P(s,s) = s!. For this reason arrangements of size k are often called permutations of size k.

Given an s-set S = {x1,x2,...,xs}, there are s different sequences of length 1 on S, namely (x1), (x2), ..., and (xs). So P(s,1) = s. There are s× (s− 1) sequences of length 2, because each sequence of length 1 can be extended to length 2 in s−1 different ways, and no two of these s × (s − 1) extensions will ever be equal. So

                                 P(s,2) = s(s−1). Similarly we find

                                  P(s,3) = s×(s−1)×(s−2),

                                 P(s,4) = s×(s−1)×(s−2)×(s−3),

                                   ...,

                               P(s,k) = s×(s−1)×(s−2)...(s−k +1).

So P(s,k) is calculated by multiplying, s, s−1, s−2,... until there are k factors.

It follows that

                                P(s,k) = s!/(s−k)!.                                                      (1.1)

Sample Problem 1.1 Calculate P(10,3).

Solution. There are two ways to calculate P(10,3). We could say P(10,3) = 10×9×8 = 720. Or we could use the formula:

                               P(10,3) = 10!/7! = 362880/5040 = 720.

The first way is easier

Several of the problems in the preceding section, such as those on selecting a committee, asked for the number of sequences of a certain length, and their solutions can sometimes be stated compactly by using arrangements.

Sample Problem 1.2 A committee of three people—chair, secretary, and treasurer—is to be elected by a club with 14 members. If every member is eligible to stand for each position, how many different committees are possible?

Solution. We can treat the committee as an ordered set of three elements chosen from the 14-element set of members. So the answer is P(14,3), or 2,184.

Sometimes an added condition makes the solution of a problem easier, not harder.

For example, arranging people around a circular table is no more difficult than arranging them in a line, and sometimes easier.

Suppose n people are to sit around a circular table. We start by arbitrarily labeling one seat at the table as “1,” the one to its left as “2,” and so on. Then there are n!  different ways of putting the n people into the n seats. However, we have counted two arrangements as different if one is obtained from the other by shifting every person one place to the left, because these two arrangements put different people in “1”; but they are clearly the same arrangement for the purposes of the question.

Each arrangement is one of a set of n, all obtained from the others by shifting in a circular fashion. So the number of truly different arrangements is n!/n, which equals  (n−1)!.

Sample Problem 1.3 How many ways can you make a necklace by threading together seven different beads?

Solution. Suppose you put the beads on a table before threading them.

There would be (n − 1)! = 6! = 720 ways to arrange them in a circle.

However, after the beads are threaded, the necklace could be flipped over, so every necklace has been counted twice (for example, abcde f g and ag f edcb are the same necklace). Therefore, the total number is 6!/2 = 360.

Sample Problem 1.4 Colette’s Copying Company has eight photocopying machines and seven employees who can operate them. There are four copying jobs to be done simultaneously. How many ways are there to allocate these jobs to operators and machines?

Solution. Call the jobs A,B,C,D. Choose two arrangements: first, which four operators should do the jobs; second, which machines should be used. The operator choice can be made in P(7,4) ways, and the machines in P(8,4) ways.

In each case, the first member of the sequence is the one allocated to job A, the second to job B, and so on. There are P(7,4)×P(8,4) = 7×6×5×4×8×7×6×5 = 1,411,200 ways.

Sample Problem 1.5 The club in Sample Problem 1.2 wishes to elect a bylaws committee with three members—Chair, Secretary, and Legal Officer—and requires that no members of the main club committee be members of the by-laws committee. In how many different ways can the two committees be chosen?

Solution. Suppose the main committee is chosen first. There are P(14,3) = 2,184 ways to do this. After the election, there are 11 members eligible for election to the by-laws committee, so it can be chosen in P(11,3) = 990 ways.

So there are a grand total of 2,184×990 = 2,162,160.

In the preceding Sample Problem we see that, even in small problems, the numbers get quite large. It might be better to report the answer in its factored form, as 14 × 13 × 12 × 11 × 10 × 9. This form of answer also makes it clear that we could have solved the problem by treating the two committees as one six-member sequence, with P(14,6) possible solutions.

In some cases, we want to talk about collections of objects with repetitions. For example, consider the letters in the word ASSESS. In how many ways can you order these letters? The set of letters involved is {A,S,E}, but there are six letters in the word, and the orderings will have six elements. For clarity, we often talk of distinguishable and indistinguishable elements. We could say the set of letters in ASSESS has six elements: four (indistinguishable) S’s, an A, and an E.

One way to tackle these problems is to assume the “indistinguishable” objects can be distinguished, and then take this into account. For example, if the letters in the word ASSESS were written on tiles with numbers as subscripts, like scrabble tiles, we could label them so that no two copies of the same letter get the same subscript, for example A₁S₁S₂E₁S₃S₄. Then all the six letters are different, and there are 6! orderings. Say you have each of these orderings written on slips of paper.

Now collect together into one pile all the slips that differ only in their subscripts.

For example, A₁E₁S₁S₂S₃S₄ and A₁E₁S₂S₁S₃S₄ will be in the same pile, as will A₁E₁S₂S₃S₁S₄, A₁E₁S₄S₂S₃S₁, and several others. In fact, we can work out how many slips there are in a pile. There are four letters S, and one each of the others.

Two slips will be in the same pile when they have the letters in the same order, but the subscripts on the S’s are in different order. There are 4! = 24 ways to order the four subscripts, so there are 4! slips in each pile. Therefore, there are 6!/4! = 30 piles. Two orderings can be distinguished if and only if their slips are in different piles, so there are 6!/4! = 30 distinguishable orderings of ASSESS.

The same principle can be applied with several repeated letters. For example, if SUCCESS is written as S₁U₁C₁C₂E₁S₂S₃, we see that there are 2! ways of ordering the C’s and 3! ways if ordering the S’s, so each pile will contain 3! × 2! slips, and the number of distinguishable orderings is 7!/(3!×2!) = 420.

Sample Problem 1.6 In how many distinguishable ways can you order the letters of the word MISSISSIPPI?

Solution. There are one M, four I’s, four S’s and two P’s, for a total of 11 letters.