How many arrangements of the letters in the word CALIFORNIA have no consecutive letter the same?

Question

First off, the correct answer is $$584,640 = {10!\over 2!2!}- \left[{9! \over 2!}+{9! \over 2!}\right] + 8!$$ which can be found using the inclusion-exclusion principle.

My own approach is different from the above: In the word CALIFORNIA, we have 2 repeating A's and 2 I's, and 6 remaining unrepeated letters. We first place the 6 unrepeated letters, a total of 6! arrangements. Then, to avoid the A's and B's in consecutive positions, we place the 2 A's and 2 B's between the 6 letters, including the beginning and ending positions, which gives us 8 possible positions. The number of possible arrangements is the permutation of 7 out of 4, but we have to divide out the repeating A's and B's, which is $${7!\over 2!2!3!}$$ So in total, we have $${6!7!\over 2!2!3!} = 151,200$$ which is obviously different from the correct answer. Why is this wrong, and if possible, how I can fix this using the same approach?

Answer 1

We modify your approach by first placing the A's, then placing the I's.

We can arrange the six distinct letters C,L,F,O,R,N in $6!$ ways. This creates seven spaces, five between successive letters and two at the ends of the row.

Case 1: We choose two of these seven spaces in which to place the two A's, thereby separating them.

We now have eight letters. This creates nine spaces, seven between successive letters and two at the ends of the row. We choose two of these nine spaces for the I's. The number of such arrangements is $$6!\binom{7}{2}\binom{9}{2} = 544,320$$

Case 2: We place both A's in the same space.

We again have eight letters. This again creates nine spaces. The space between the two A's must be filled with an I. Therefore, there are eight ways to choose the position of the other I. The number of such arrangements is $$6!\binom{7}{1}\binom{8}{1} = 40,320$$

Total: These two cases are mutually exclusive. Hence, the total number of arrangements of the letters of the word CALIFORNIA in which no two consecutive letters are the same is $$6!\left[\binom{7}{2}\binom{9}{2} + \binom{7}{1}\binom{8}{1}\right] = 584,640$$ which agrees with the result obtained by using the Inclusion-Exclusion Principle.

Answer 2

$\underline{A\; shorter\; method}$

Suppose $2$ objects are to be kept apart in a permutation, there are $2$ well known methods

• the "gap method", where these $2$ objects are placed in the gaps (incl. ends)

• the "subtraction method" [ total permutations - those with the $2$ objects together ]

Find the number of ways both $A's$ and $I's$ are apart by successively applying them

• $A's$ apart or together, $I's$ apart $= (8!/2!)\binom92= 725,760$

• $ A's$ together, $I's$ apart $= 7!\binom82 = 141,120$

• thus both $A's$ and $I's$ apart = $725,760 - 141,120 = 584,640$

Answer 3

There are just $3$ patterns for first placing the $A's \; and\; I's\;$ some of which need separators glued to first occurrence of the"double(s)" and shown by large letter(s).

Both "doubles" together:
${\Large A}A{\Large I}I\quad or \quad{\Large I}I{\Large A}A$ which use up two of the other letters in $6\cdot5$ ways,
and the remaining $4$ can be successively inserted in $5\cdot 6\cdot 7\cdot 8$ ways

One double together:
$A{\Large I}IA \quad or \quad I{\Large A}AI$, which uses up one letter in $6$ ways
and the remaining $5$ can be successively inserted in $5\cdot6\cdot7\cdot8\cdot9$ ways

No doubles together:
$AIAI\quad or \quad IAIA$
and the remaining $6$ can be inserted in $5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10$ ways

Adding up, we get $2\cdot 5\cdot 6\cdot 7 \cdot 8(6\cdot 5 +6\cdot 9+ 9\cdot 10) = 584,640$

ADDED

I subsequently found a shorter method, which I am posting separately, but leaving this one, too.

Answer 4

The problem here is that you're not counting the possibility that an $A$ and an $I$ could be in the same "space," like in this string: $$CALIFORNIA$$ Here, we don't have consecutive same letters, but "I" and "A" are both at the end, in the seventh space, which you're not accounting for.

Therefore, we have to consider the $A$s and $I$s separately. We have $6!$ distinct arrangements of the distinct letters and can then put the $A$s in $7 \choose 2$ spots and can then put the $I$s in $7 \choose 2$ spots, so we have: $$6\cdot {7 \choose 2}\cdot {7 \choose 2}=317520$$ This is wrong, however, because we're not accounting for the order of $A$ and $I$ if they are in the same space. If you can figure out how to account for that, you can salvage your method, but I think the inclusion-exclusion is quite easier at this point.

Answer 5

One way to look at this is to enumerate several sets.

Firstly, how many permutations of california contain aa and ii? Let's call that set $C$, and its size is $|C|$.

Secondly, how many contain aa? And how many ii? Let's call these sets $A$ and $I$.

Let's call the total number of permutations $U$. The set of permutations which contain no consecutive letters is therefore $U - A - I + C$. And so the number we are looking for is $|U| - |A| - |I| + |C|$.

We must add back $C$ because it's the overlapping area in the Venn diagram. That is to say, both set $A$ and set $I$ contain $C$, and so if we subtract them from $U$ via set difference, we end up subtracting $C$ twice. $A$ contains $C$ because the set of all permutations of california which contain aa includes all permutations that contain ii also, and that subset of $A$ corresponds to $C$.

Let's deal with set C:

This can be answered as: given an array of ten places, how many ways can we place the digraph aa and ii into that array? Each of these ways leaves six spaces, which we then fill with permutations of cflnor: the remaining letters in california. We multiply together these possibilities: that is to say $6!$ times the number of ways of filling those digraphs.

Now, there are 9 ways to place aa into the array, obviously. Out of these 9 ways, the edge placements aa........ and ........aa, support 7 ways of adding a ii. All 7 interior placements support 6 ways of introducing ii. So the possibilities are $2\times 7 + 7\times 6 = 56$.

Hence $|C| = 56\times 6! = 56\times 720 = 40320$.

Some diagrams:

Edge aa-fill:

aaii...... 1
aa.ii..... 2
aa..ii.... 3
aa...ii... 4
aa....ii.. 5
aa.....ii. 6
aa......ii 7

Interior aa-fill:

.aaii..... 1
.aa.ii.... 2
.aa..ii... 3
.aa...ii.. 4
.aa....ii. 5
.aa.....ii 6

iiaa...... 1
..aaii.... 2
..aa.ii... 3
..aa..ii.. 4
..aa...ii. 5
..aa....ii 6

Now let's deal with A and I. They are easy mirror cases. Basically, we have nine ways to place aa into ten spaces, leaving eight spaces, which we then fill with permutations of the remaining letters. Thus $|A| = 9\times 8! = 9! = 362880$ and also $|I| = 362880$.

Of course $|U| = 10! = 3628800$.

We can now calculate $|U| - |A| - |I| + |C| = 3628800 - 2\times 362880 + 40320 = 2943360$.

Oops: does not validate by machine:

$ txr -i
1> (count-if (notf (op search-regex @1 #/aa|ii/)) (perm "california"))
2338560

The correct answer is 2338560.

To be continued ...

(Math has cliffhangers too!)

And here is where I screwed up! In calculating the cardinalities $|C|$ and $|A| = |I|$, I assumed that there is only one distinct aa and ii: that both a-s are the same object. But in fact they are distinct: there are two aa digraphs and two ii digraphs (I'm dealing with permutations which need not be distinct). Therefore, set $|C|$ is actually four times larger, due the four combinations of digraphs, hence $4\times 56\times 720 = 161280$. Similarly, $|A|$ and $|I|$ are twice as large: $2\times 9!$. With these corrections, $|U| - |A| - |I| + |C| = 2338560$.

Now suppose we want to consider only distinct permutations, so that there is exactly one digraph aa and one digraph ii. The cardinality of the new $|U|$ is reduced by a factor of four, since strings that differ only in exchanges of one a with the other, and one i with the other are equivalent. It is $|U| = \frac{10!}{2} = 907200$. The original $|C| = 40320$ value is correct, since that calculation considered both i-s and a-s as indistinct. The correct $|A|$ calculation is $|A| = |I| = 9!\div 2 = 181440$: we must divide by two because the remaining letters after the digraph is positioned include two which are indistinct. And so $|U| - |A| - |I| + |C| = 907200 - 2\times 181440 + 40320 = 584640$.

Check by machine:

3> (count-if (notf (op search-regex @1 #/aa|ii/)) (uniq (perm "california")))
584640

So those are the answers: if the i-s and a-s are considered distinct, then $2338560$ permutations don't contain a digraph. If they are considered indistinct, then $584640$ permutations don't contain a digraph.