Permutations when repetitions are allowed

This sub-section proves Theorem 2: when repetitions ARE allowed, the number of arrangements of $n$ distinct objects taken $r$ at a time is $n^r$.

Proof. The problem is again the same as filling $r$ places in a row, but now with repetitions of the $n$ available objects permitted. Consider the same style of table as in §3.5.1, listing the $r$ places across the top and the number of ways to fill each place across the bottom — but this time, BECAUSE repetitions are allowed, using an object at one place does not remove it from the pool available for the next place, so every single place, from 1st through to $r$th, independently has all $n$ objects available. By the Multiplication Principle, the total is $n\times n\times\cdots\times n \ (r \text{ times}) = n^r.$

Solved Example 1. It is required to arrange 8 books on a shelf; find the number of ways if two specified books are (i) always together, (ii) never together. (i) Treat the two specified books as a single combined unit — this leaves 7 items to arrange (the combined unit plus the other 6 books), giving $7!$ ways; the 2 books WITHIN the combined unit can themselves be swapped in $2!$ ways. Total $=2!\times7!=2\times5040=10080$. (ii) One method: take one of the two specified books together with the other 6 (i.e. 7 books), arrange these 7 in $7!$ ways; then the REMAINING (second specified) book must be placed so as to avoid the 2 positions immediately adjacent to the first specified book — leaving 6 valid positions out of the gaps created — giving $6\times7!=6\times5040=30240$. Alternative method: subtract the 'always together' count from the unrestricted total: $8!-2\times7!=(8-2)\times7!=6\times7!=6\times5040=30240$, confirming the same answer by the complement approach.

Solved Example 2. In how many ways can 7 examination papers be arranged so that papers 6 and 7 are never together? By the same reasoning as the previous example's alternative method, the count of arrangements where any two specified papers (out of 7 total) are never together is $(7-2)\times(7-1)! = 5\times6! = 5\times720=3600$.

Solved Example 3. A family of 3 brothers and 5 sisters is to be arranged for a photograph so that (i) all brothers sit together, (ii) no two brothers sit together. (i) Treating the 3 brothers as one combined unit gives $5+1=6$ 'persons' to arrange, in ${}^6P_6=6!=720$ ways; the 3 brothers within their unit can then be arranged among themselves in ${}^3P_3=3!=6$ ways. Total $=6!\times3!=720\times6=4320$. (ii) First arrange the 5 sisters among themselves: ${}^5P_5=5!=120$ ways. This creates a pattern with a gap before, between, and after each sister — shown as $*S_1*S_2*S_3*S_4*S_5*$, where each $*$ marks a position where at most one brother could be placed so that no two brothers end up adjacent. Since there are 6 such gap-positions and 3 brothers to place into them (at most one per gap, and order matters since the brothers are distinct), the number of ways is ${}^6P_3=\dfrac{6!}{3!}=120$. The required total is then $5!\times{}^6P_3 = 120\times120=14400$.

A general Theorem follows for when some of the $n$ objects must always stay together: the number of permutations of $n$ objects taken all at a time, when $m$ specified objects among them must always come together, is $m!\,(n-m+1)!$. Proof: since the $m$ specified objects always come together, treat them as a SINGLE combined object — this reduces the count of distinct objects (for permutation purposes) from $n$ down to $n-m+1$. These $n-m+1$ objects can be arranged, taken all at a time, in $(n-m+1)!$ ways. Within any one such arrangement, the original $m$ specified objects (still together as a block) can be rearranged among THEMSELVES in $m!$ ways. Since this internal rearrangement is possible for each and every one of the $(n-m+1)!$ outer arrangements, the total number of permutations is $m!\,(n-m+1)!$. …