Chapter
Theory
A permutation is an arrangement of objects in order. The key difference from simple selection is that order is part of the object. If all objects are distinct, \(n\) objects can be arranged in \(n!\) ways. If some objects are identical, overcounting from permuting identical copies must be removed.
Olympiad permutation problems rarely reduce to one formula. More often, one needs the right device: glue a block, subtract forbidden adjacencies, fix a rotation in circular seating, or split by positions.
If objects must be together, try a block. If objects must not be together, it is often easier to subtract cases where they are together. If the arrangement is circular, first fix one object or use \((n-1)!\). If there are identical letters, first count as if they were distinct and then divide by permutations of identical copies.
For forbidden positions, ask whether the restrictions are independent or overlap. If they overlap, inclusion-exclusion may be needed.
Examples
Basic technique: each next choice reduces the number of options.
Problem. In how many ways can \(6\) different books be arranged on a shelf?
The first position has \(6\) choices, the second \(5\), then \(4,3,2,1\). Total: \(6!=720\).
Comment. This is a linear arrangement of distinct objects.
Identical letters create overcounting.
Problem. How many distinct words can be obtained by rearranging the letters of \(BANANA\)?
There are \(6\) letters. The letter \(A\) appears \(3\) times and \(N\) appears \(2\) times. If all copies are treated as distinct, there are \(6!\) arrangements, but each word is counted \(3!\cdot2!\) times. Answer: \(6!/(3!\cdot2!)=60\).
Comment. Divide only by permutations of identical letters.
If two objects must stand together, glue them.
Problem. In how many ways can \(6\) people stand in a row if Anton and Boris must stand together?
Glue Anton and Boris into a block. Then there are \(5\) objects: the block and \(4\) other people. They can be arranged in \(5!\) ways. Inside the block there are \(2\) orders. Answer: \(2\cdot5!=240\).
Comment. Do not forget the internal order of the block.
A prohibition is often easier as all minus bad.
Problem. In how many ways can \(6\) people stand in a row if Anton and Boris must not stand together?
There are \(6!=720\) total arrangements. They stand together in \(2\cdot5!=240\) ways. Therefore the number not together is \(720-240=480\).
Comment. This is the complement of the previous problem.
In a circle, rotations are considered the same.
Problem. In how many ways can \(5\) distinct people sit at a round table?
Fix one person. The remaining \(4\) people can be arranged around that person in \(4!\) ways. Answer: \(24\).
Comment. Fixing one person removes rotation.
Blocks also work at a round table.
Problem. In how many ways can \(6\) people sit at a round table if two specified people must sit together?
Glue the two people into a block. We get \(5\) objects around a circle, which can be arranged in \((5-1)!=24\) ways. The block has \(2\) internal orders. Answer: \(48\).
Comment. First handle the circle, then the block order.
Half of all permutations have \(A\) before \(B\).
Problem. How many permutations of \(1,2,3,4,5\) have \(1\) before \(2\)?
In all \(5!\) permutations, the numbers \(1\) and \(2\) are symmetric: in exactly half, \(1\) comes before \(2\), and in half the reverse happens. Answer: \(5!/2=60\).
Comment. This is not an adjacency condition.
Forbidden fixed points overlap.
Problem. How many permutations of \(1,2,3,4\) leave no number in its own position?
There are \(4!=24\) total permutations. Subtract those with at least one fixed point: \(4\cdot3!\). Add back intersections of two fixed points: \(6\cdot2!\). Subtract three: \(4\cdot1!\). Add four: \(1\). Answer: \(24-24+12-4+1=9\).
Comment. This is the first derangement problem.
Problems
In how many ways can \(5\) different books be arranged on a shelf?
This is a permutation of \(5\) distinct objects.
The answer is \(5!=120\).
How many distinct words can be obtained by rearranging the letters of \(MAMA\)?
There are two \(M\)'s and two \(A\)'s.
If all \(4\) letters were distinct, there would be \(4!=24\) arrangements. Each word is counted \(2!\cdot2!=4\) times. Answer: \(24/4=6\).
In how many ways can \(3\) different students be chosen and ordered from \(7\)?
Choose first, second, third.
The first can be chosen in \(7\) ways, the second in \(6\), the third in \(5\). Total: \(7\cdot6\cdot5=210\).
In how many ways can \(5\) different people sit at a round table?
Fix one person.
Fix one person to remove rotations. Arrange the remaining \(4\) people in \(4!=24\) ways.
In how many ways can \(6\) people stand in a row if two specified people must stand together?
Glue the two specified people into a block.
The block and \(4\) other people make \(5\) objects, arranged in \(5!\) ways. The block has \(2\) internal orders. Answer: \(2\cdot5!=240\).
In how many ways can \(6\) people stand in a row if two specified people must not stand together?
Subtract cases where they are together.
There are \(6!=720\) total arrangements. They stand together in \(2\cdot5!=240\) ways. Therefore the answer is \(720-240=480\).
How many distinct permutations of the letters of \(BANANA\) are there?
The letter \(A\) appears \(3\) times, \(N\) appears \(2\) times.
There are \(6\) letters. Divide \(6!\) by \(3!\) for the \(A\)'s and by \(2!\) for the \(N\)'s. We get \(6!/(3!\cdot2!)=60\).
Seven students stand in a row. In how many ways can this be done if two specified students must not stand next to each other?
Total minus adjacent.
Total: \(7!=5040\). If the two are adjacent, glue them: \(6!\cdot2=1440\). Answer: \(5040-1440=3600\).
On a shelf there are \(3\) math books, \(2\) physics books, and \(2\) history books, all distinct. In how many ways can they be arranged so that books of each subject stand together?
Treat each subject as a block.
The three subject blocks can be arranged in \(3!\) ways. Inside the blocks: \(3!\), \(2!\), \(2!\). Total: \(3!\cdot3!\cdot2!\cdot2!=144\).
In how many ways can \(6\) people sit at a round table if two specified people must sit together?
Glue the pair and use circular permutation.
The pair forms a block. There are \(5\) objects around a circle, arranged in \((5-1)!=24\) ways. The block has \(2\) internal orders. Answer: \(48\).
How many permutations of \(1,2,3,4\) leave no number in its original position?
Use inclusion-exclusion over fixed points.
Total: \(24\). With one specified fixed point: \(3!\), and there are \(4\) choices. With two: \(2!\), and \(6\) pairs. With three: \(1!\), and \(4\) choices. With four: \(1\). Answer: \(24-4\cdot6+6\cdot2-4\cdot1+1=9\).
How many permutations of \(1,2,3,4,5\) have \(1\) before \(2\)?
For every permutation with \(1\) before \(2\), there is a paired one with \(2\) before \(1\).
There are \(5!=120\) permutations. By symmetry, exactly half have \(1\) before \(2\). Answer: \(60\).
In how many ways can \(5\) boys and \(4\) girls stand in a row so that no two girls are adjacent?
First arrange the boys, then choose gaps for the girls.
The boys can be arranged in \(5!\) ways. Around them are \(6\) gaps: before the first, between neighbors, and after the last. Choose \(4\) gaps for the girls and arrange the girls in \(4!\) ways. Answer: \(5!\cdot15\cdot4!=43200\).
How many permutations of \(A,A,B,B,C,C\) have no two equal adjacent letters?
Subtract cases where \(AA\), \(BB\), or \(CC\) forms a block.
Total: \(6!/(2!2!2!)=90\). If \(AA\) is adjacent, count the block \(AA\), \(B,B,C,C\): \(5!/(2!2!)=30\), and there are \(3\) letters. If two pairs are adjacent, for example \(AA\) and \(BB\), we get \(4!/2!=12\), with \(3\) choices. If all three pairs are adjacent, \(3!=6\). Answer: \(90-3\cdot30+3\cdot12-6=30\).
How many four-digit numbers with distinct digits can be formed from \(0,1,\ldots,6\) if the number is divisible by \(5\)?
The last digit is \(0\) or \(5\).
If the last digit is \(0\), the first digit has \(6\) choices, then \(5\) and \(4\): \(120\). If the last digit is \(5\), the first digit is not \(0\) or \(5\): \(5\) choices, then \(5\) and \(4\): \(100\). Total: \(220\).
In how many ways can \(8\) people sit at a round table if two specified people must not sit together?
Total circular seatings minus those where they are adjacent.
Total: \((8-1)!=5040\). If the two are adjacent, glue them into a block: \(7\) objects around a circle, \((7-1)!=720\), and \(2\) internal orders. Bad cases: \(1440\). Answer: \(5040-1440=3600\).
There are \(8\) distinct books on a shelf. In how many ways can they be arranged so that books \(A,B,C\) appear in the order \(A\) before \(B\) before \(C\), not necessarily consecutively?
Among the \(3!\) relative orders of \(A,B,C\), exactly one works.
There are \(8!\) arrangements. The relative orders of \(A,B,C\) are equally likely, and there are \(3!=6\). Exactly one order works, so the answer is \(8!/6=6720\).
How many permutations of \(1,2,\ldots,7\) have the even numbers exactly in even positions?
There are three even positions and three even numbers.
The even numbers \(2,4,6\) can be placed in positions \(2,4,6\) in \(3!\) ways. The odd numbers \(1,3,5,7\) occupy the remaining positions in \(4!\) ways. Answer: \(3!\cdot4!=144\).
How many words of length \(5\) over \(\{A,B,C,D\}\) contain exactly two \(A\)'s, and they are not adjacent?
First choose two non-adjacent positions for the \(A\)'s.
There are \(10\) pairs of positions for the two \(A\)'s. Adjacent pairs: \(4\), so non-adjacent pairs: \(6\). The remaining \(3\) positions can be filled independently with \(B,C,D\): \(3^3=27\). Answer: \(6\cdot27=162\).
In how many ways can \(5\) people sit at a round table if exactly one person must sit between Anton and Boris?
Fix Anton.
Fix Anton. Boris has \(2\) seats at distance two around the circle from Anton. Arrange the remaining \(3\) people in \(3!\) ways. Answer: \(2\cdot3!=12\).
How many permutations of \(1,2,3,4,5\) leave no number in its original position?
Apply inclusion-exclusion over fixed points.
Total: \(5!=120\). By inclusion-exclusion over specified fixed points: \(120-5\cdot4!+10\cdot3!-10\cdot2!+5\cdot1!-1=120-120+60-20+5-1=44\).
In how many ways can \(6\) boys and \(6\) girls sit around a round table so that boys and girls alternate?
First seat the boys around the table, then place girls in the gaps.
The boys can be seated around the table in \((6-1)!=120\) ways. This creates \(6\) gaps, into which the \(6\) girls can be placed in \(6!\) ways. Answer: \(120\cdot720=86400\).
How many permutations of \(1,2,\ldots,8\) have the property that no two of \(1,2,3\) are adjacent?
First arrange the other five numbers.
The numbers \(4,5,6,7,8\) can be arranged in \(5!\) ways. They create \(6\) gaps, including the ends. Choose \(3\) gaps for \(1,2,3\) and arrange these numbers in \(3!\) ways. Answer: \(5!\cdot20\cdot6=14400\).
How many permutations of \(A,A,B,B,C,C,D,D,E,E\) have no two identical adjacent letters?
Use inclusion-exclusion over the events \(AA\), \(BB\), \(CC\), \(DD\), \(EE\) are adjacent.
There are \(10!/(2!^5)=113400\) total permutations. If \(k\) letters are chosen whose pairs are glued, we get \(C(5,k)(10-k)!/(2!^{5-k})\) arrangements. Inclusion-exclusion gives \(113400-113400+50400-12600+1800-120=39480\).
Ladders