Complex Permutation

How can we make $4$ letter words using $4$ letters (A,B,C,D) which satisfy following condition:

• The word cant starts or ends with A.
• A letter can be repeated more than once.
• Same letters can not seat together.

Example:

• BCDC (correct)
• ABCD (incorrect)
• BCDA (incorrect)
• BCCD (incorrect)

As A is not allowed at first position, the four positions of the word can be arranged in $3\cdot3\cdot3\cdot3=81$ ways.

Out of this, there will be $21$ cases where A will be at last position.

I have got those $21$ cases manually.

But I am looking for a formula or method which can be used for any $N$ and $R$.

Any help will be appreciated.

Solutions Collecting From Web of "Complex Permutation"

You didn’t say what $N$ and $R$ are; I’ll assume you mean $N$-letter words using $R$ letters of which one can’t start or end the word. (Four-letter words are bad, anyway.)

First disregard the special role of A. Let $a(N,R)$ be the number of admissible words in which the first and last letters are identical, and let $b(N,R)$ be the number of admissible words in which the first and last letters are different. Then

\begin{align}
a(N+1,R)&=b(N,R)\;,\\
b(N+1,R)&=(R-1)a(N,R)+(R-2)b(N,R)\;,
\end{align}

or

$$\pmatrix{a\\b}\to\pmatrix{0&1\\R-1&R-2}\pmatrix{a\\b}\;.$$

In your case, with $R=4$, we have

\begin{array}{c|cc}
N&a&b\\\hline
1&4&0\\
2&0&12\\
3&12&24\\
4&24&84\\
5&84&240
\end{array}

Now of the words counted by $a(N,R)$, we have to exclude $1$ in $R$ because they start and end with the wrong letter, and of the words counted by $b(N,R)$ we have to exclude $2$ in $R$ because they start or end with the wrong letter, so the number you want is

$$\frac{R-1}Ra(N,R)+\frac{R-2}Rb(N,R)=\frac{b(N+1,R)}R\;,$$

which in your case is $\frac{240}4=60$.

The first and last letter cannot be $A$, so both must be one of $B,C,D$. $3^2$ ways to select them.

• If they are the same letter ($3$ of those ways), then the middle two letters can be selected in $3\times 2$ ways (selecting from three remaining letters with no repetition).
• If they are different letters ($3^2-3$ of those ways), then if the second letter is:
• the same as the last, then there are three options for the third place.
• one of the two other letters, then there are two options for the third place.
$$3\times(3\times 2)+(3^2-3)\times(1\times 3+2\times 2)$$

Consider permutations without $A$ and with $A$

Without $A$, easy to get $3\cdot2\cdot2\cdot2 = 24$

Now A can be at position $2$ or $3$, giving rise to $2\times(3\cdot1\cdot3\cdot2) =36$

so valid permutations = $60$

The first position can be filled in 3 ways (because A is not a valid option)

The second position can be filled by 3 ways (because the letter in the first cannot repeat)

Let’s us take two cases:

Case-I- The second position is filled with A

Then the third position can be filled by 3 ways and the fourth can be filled by 2 ways

Case-II The second position is not filled with A (There are two such choices)

Let us again take two cases

Case-II (a): The third position is filled with A

Then there are three choices for the fourth position.

Case II (b) The third position is not filled with A (There are two such choices)

Then there are two choices to fill the fourth position.

The total number of possible ways are

$3\times (3\times 2 + 2 (3+2\times 2 ) ) =60$

In order to get the number of ways end with A, you have 3 ways to start, one way to end and there are two cases for the third position.

(1) If the third letter is the same as the first letter, then we have three ways left for the second letter. This gives you $3\times3\times1\times1=9$ ways.

(2) If the third letter is different from the first letter, then we have two ways for the third letter and two ways for the second letter. This gives you $3\times2\times2\times1=12$ ways.

In total, there are 21 ways which end with A.

Let $n$ be the size of the word and $r$ the number of letters.

Let $f(n)$ be the number of solutions where the word does not start with A, but is allowed to end with that letter. It is easy to see that
$$f(n) = (r-1)^n$$

Let $g(n)$ be the desired number of solutions, where the word neither starts nor ends with A.

$f(n) – g(n)$ counts the number of solutions where the word ends with A. Note that this is exactly $g(n-1)$ for $n \geq 2$, and 0 for $n = 1$. That is,
$$g(n) = f(n) – g(n-1)$$
$$g(n) = \sum_{k=1}^n (-1)^{n-k}f(k)$$
$$g(n) = \frac{(r-1)^{n+1} + (-1)^{n+1}(r-1)}{r}$$

This is the number of circular arrangements of $n+1$ letters with no adjacent repetitions where assignment at position 0 is fixed to the letter A.

Plugging $n = r = 4$, we get $g(n) = 60$, as others have explained for this specific case.