Practice
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\).