Number of Derangements of the word BOTTLE

Solution 1:

The following answer is quite long but introduces a general method for solving problems of this kind.

The answer to your question can be stated very succinctly as

$$\frac{1}{2!}\int_{0}^{\infty}e^{-x}\left(x-1\right)^4\left(x^2-4x+2\right)\, dx=84\tag{*}\label{*}$$

But how do we get there?

An amazingly versatile approach which encompasses problems of permutations with restricted positions is that of rook polynomials.

The first step is to re-frame the whole problem in terms of a 2-dimensional array called a "chess-board" or just a "board". Along the top and the side of the board are the objects (which are temporarily made distinct) to be permuted.

On the board we will place non attacking, identical "rooks" which specify a permutation. We can then cater for our restrictions on position by greying out forbidden squares. This collection of grey squares forms what is called the forbidden subboard.

Instead of explaining further consider how the board for your problem would look

\begin{array}{c|c|c|c|c|c|c|} &\textbf{B}&\textbf{O}&\textbf{T}_\mathbf{1}&\textbf{T}_\mathbf{2}&\textbf{L}&\textbf{E}\\ \hline \text{B}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}&&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}\\ \hline \text{O}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}\\ \hline \text{T}_1&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&&\\ \hline \text{T}_2&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&&\\ \hline \text{L}&&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}\\ \hline \text{E}&\bbox[white,15px]{\phantom{H}}&&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}\\ \hline\end{array}

Along the top are your letters in their original positions and along the side are the letters to be permuted, we will position 6 rooks, 1 in each row avoiding grey squares.

We place rooks so the horizontal positions of rooks in each row give the new location for the letter of that row. The greyed out "forbidden" squares clearly prevent letters from being placed in their original locations, and in the case of the two Ts neither is allowed in their own original position or that of their twin. for example the following arrangement of rooks

\begin{array}{c|c|c|c|c|c|c|} &\textbf{B}&\textbf{O}&\textbf{T}_\mathbf{1}&\textbf{T}_\mathbf{2}&\textbf{L}&\textbf{E}\\ \hline \text{B}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}&\Huge\unicode{x265c}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}\\ \hline \text{O}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&\Huge\unicode{x265c}&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}\\ \hline \text{T}_1&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&\Huge\unicode{x265c}&\\ \hline \text{T}_2&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&&\Huge\unicode{x265c}\\ \hline \text{L}&\Huge\unicode{x265c}&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}\\ \hline \text{E}&\bbox[white,15px]{\phantom{H}}&\Huge\unicode{x265c}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}\\ \hline\end{array}

represents the valid permutation

\begin{array}{c|c|c|c|c|c|c} \text{Original positions}&\textbf{B}&\textbf{O}&\textbf{T}_\mathbf{1}&\textbf{T}_\mathbf{2}&\textbf{L}&\textbf{E}\\ \hline \text{Permutation}&\text{L}&\text{E}&\text{B}&\text{O}&\text{T}_1&\text{T}_2\end{array}

Okay, now that we have set up our board, how can we use it to count our valid permutations?

We need to talk about rook polynomials

A standard rook polynomial is really quite a simple idea, if we have some chess board of any configuration then the rook polynomial for that board

$$R(x)=1+r_1x^1+r_2x^2+\ldots +r_kx^k+\ldots +r_nx^n$$

lists the number of ways $r_k$ that $k$ non-attacking rooks can be placed on it. Note that $n$ is the smallest dimension of the board.

For square boards of dimension $n$ it is easy to verify that

$$R(x) = \sum_{k=0}^{n}\binom{n}{k}^2k!\, x^k$$

by arguing that we may choose $k$ rows in which to place $k$ rooks in $\binom{n}{k}$ ways, then order those $k$ rooks (each in a different row) in $n$ columns in $\binom{n}{k}k!$ ways.

You can see that your forbidden subboard is composed of four $1\times 1$ square boards and one $2\times 2$ square board and that these boards are all disjunct (that is: they have no common rows or columns).

Each $1\times 1$ board has rook polynomial

$$1+x$$

and the $2\times 2$ board has rook polynomial

$$1+4x+2x^2$$

Without too much effort we can see that if we have two disjunct boards $\mathscr{B_1}$ and $\mathscr{B_2}$ or subboards then multiplying their rook polynomials gives the rook polynomial of the union of the two boards

$$R_{\mathscr{B_1}}(x)R_{\mathscr{B_2}}(x)=R_{\mathscr{B_1}\cup\mathscr{B_2}}(x)$$

So the rook polynomial for your entire forbidden subboard is

$$R_{\mathscr{S}}(x)=(1+x)^4(1+4x+2x^2)$$

Now, once we have our rook polynomial for the forbidden subboard we want to use it to count the ways in which our rooks can be placed so that none are on it.

This is where inclusion-exclusion comes in. If we define the sets of rook placements

$$A_k=\text{rook placements where the rook in row }k\text{ is on the forbidden subboard}$$

For a general forbidden subboard $\mathscr{S_g}$ with $n$ rows ($\le\text{number of columns}$) and rook polynomial

$$R_{\mathscr{S_g}}(x)=\sum_{k=0}^{n}r_kx^k\tag{1}\label{1}$$

Then we have that the number of placements of rooks so that none of the rooks are on the subboard is:

$$|(A_1\cup A_2\cup\ldots\cup A_n)'|=$$ $$n!-\left(\sum_{i}|A_i|-\sum_{i_1<i_2}|A_{i_1}\cap A_{i_2}|+\ldots +(-1)^{n-1}|A_1\cap A_2\cap\ldots\cap A_n|\right)$$

Where we can see that

$$\sum_{i}|A_i|=r_1(n-1)!$$ $$\sum_{i_1<i_2}|A_{i_1}\cap A_{i_2}|=r_2(n-2)!$$ $$\vdots$$ $$|A_1\cap A_2\cap\ldots\cap A_n|=r_n(n-n)!$$

We can also see that (since $r_0=1$)

$$n! = r_0(n-0)!$$

so

$$|(A_1\cup A_2\cup\ldots\cup A_n)'|=$$ $$r_0(n-0)!-r_1(n-1)!+r_2(n-2)!-\ldots +(-1)^nr_n(n-n)!$$ $$=\sum_{k=0}^{n}(-1)^kr_k(n-k)!$$

This can be compared with the rook polynomial $\eqref{1}$ for $\mathscr{S_g}$ so that all we need to do is replace each $x^k$ with $(-1)^k(n-k)!$. This is quite an acceptible way of calculating and if you do this with your example you get

$$(1+x)^4(1+4x+2x^2)= 1+ 8 \, x+ 24 \, x^{2}+ 36 \, x^{3}+ 29 \, x^{4}+ 12 \, x^{5}+2 \, x^{6}$$ $$\implies|(A_1\cap A_2\cap A_3\cap A_4\cap A_5\cap A_6)'|$$ $$=6!- 8 \cdot 5!+ 24 \cdot 4! - 36\cdot 3! + 29 \cdot 2!- 12 \cdot 1!+2 \cdot 0!=168$$

remembering the two T's are actually identical we divide by $2!$ to give $\bbox[yellow, 5px]{84}$.

To make this answer look like the one at the top we note that by modifying the rook polynomials so that we have

$$(x-1)^4(x^2-4x+2)\text{ instead of }(1+x)^4(1+4x+2x^2)$$

Then multiplying these modified polynomials out gives

$$(x-1)^4(x^2-4x+2)=x^{6} - 8 \, x^{5} + 24 \, x^{4} - 36 \, x^{3} + 29 \, x^{2} - 12 \, x + 2$$

so that all we need to do to get our inclusion-exclusion formula is replace each $x^k$ with $k!$. Well if we remember

$$\int_{0}^{\infty}e^{-x}x^k\, dx=k!$$

For non-negative integer $k$, then $\eqref{*}$ follows immediately.

There is an excellent rook polynomial solver that will output both the standard rook polynomial and the number of rook placements that avoid the user defined subboard.

For more on rook polynomials an Internet search will yield a plethora of results or for a good book see John Riordan's Introducton to Combinatorial Analysis in which he devotes 2 whole chapters to the topic.

Solution 2:

There are $\left\lfloor \frac{6!}{e}\right\rfloor = 265$ derangements of a 6-element set, but applying that formula to the letters of "BOTTLE" has two problems:

1. Some of these "derangements" move the T in the fourth position to the third position, or vice versa, or both, so once we take that into account, they're no longer actual derangements.

2. Of the valid derangements, each is counted twice: if you switch the two T's, that's a different permutation of a $6$-element set, but shouldn't be a different derangement of the letters of "BOTTLE".

We begin by fixing the first problem. There are three cases:

• The false derangement actually swaps the two T's. This case is in bijection (by swapping the two T's) with permutations that fix both T's and derange everything else, so there are $\left\lfloor \frac{4!}{e}\right\rfloor = 9$ of these.
• The false derangement moves the first T to the second T's place, and the second T to somewhere other than the first T's place. This case is in bijection (by swapping the two T's) with permutations that fix the second T and derange everything else, so there are $\left\lfloor \frac{5!}{e}\right\rfloor = 44$ of these.
• Same as the previous case, but with the second T going to the first T's place; also $44$ of these.

This leaves us with $265-44-44-9 = 168$ actual derangements.

The second problem is easy to fix; now we can divide by $2$ and get $84$ as our final answer.

(I also cheated and confirmed this by brute force in Mathematica.)

Solution 3:

Choose two valid locations for the letters $T$, $\binom 42$ ways. The letters that started at those locations are "free", the other two are "unfree".

Choose a location for the first unfree letter from the the $3$ available to it. Two cases:

• choose one of the two $T$ start positions, in which case the other unfree letter has only two choices, or
• choose the other unfree letter start position, in which case that letter is free.

Remaining $n$ free letters go as $n!$.

Over all we have $\binom 42(2\cdot2\cdot 2! + 1\cdot 3!) = 6\cdot (8+6) = 84$.

Steampunk Solutions Inc