Vtyjkyuk

In the book titled 'Combinatorics- A Guided Tour' by David Majur', there is
stated on pg. #18, #19 regarding a case of misapplication of product
principle, for the problem of counting number of $4$ lists from $[9]$ having at
least one pair of adjacent elements equal.

The $3$ steps are :

1. Which of the $3$ possible adjacent elements are equal. It may be :

(i) the first two,

(ii) the second & third,

(iii) the last two.

Any number of adjacent elements can be equal from min. of $2$ to max. of $4$.

The maximum number of adjacent locations can be : $3$.

2 . Specify the value of those equal elements, from the set of values $[1-9]$.

3 . Specify the value of other elements, i.e. again from the set of values $[1-
9]$.

The product of these gives : $3*9*9^2 = 2187$ (denoted by let, $a$) is wrong as
fails to account for the common cases generated again as shown by the below
examples.

(i) $aabc$ generates $aa11$ to $aa99$, i.e. a total of $9*9=81$ lists.
This is shown with $a=4$ for $aabc$ list type as below:
$$4411, 4412, 4413, 4414, 4415, cdots, 4497, 4498, 4499$$

(ii) Common cases between lists of form $aabc$ & $abbc$:
This is shown for $abbc$ list type as below:
$$1441, 1442, 1443, 1444, 1445, cdots, 9447, 9448, 9449$$

(ii) Common cases between lists of form $aabc$ & $abcc$:
This is shown for $c=9$ for $abcc$ list type as below:
$$1199, 1299, 1399, 1499, 1599, cdots, 9799, 9899, 9999$$

The correct solution approach is by subtracting the case of :'No adjacent equal equal elements in $4$ lists taken from $[9]$ = $9.8^3$',
from the case of 'all possible $4$ lists from $[9] = 9^4$'.

This leads to : $9^4 - 9.8^3$ leading to correct count $(let, b=)1953$.

I tried the detailed analysis for the reason for incorrect count ($a=2187$), & the difference ($c = a-b = 2187-1953 = 234$) below:

The wrong approach takes three possible positions of adjacent equal elements, &
ignores the common permutations generated by other pairs of adjacent equal
elements, as say :

$aabc$ ignores many common elements as below for the particular case of $a=1,
b,c = [1-9]$

Let us take $a=1$ case, for sample case below:

1. $a=b$: These cases are common to those generated by the cases when first
   three positions have equal elements.
   
   $1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119,$ i.e. a total of $8$ cases;


2. $a=b=c$: These cases are common to those generated by the cases when all four
   positions have equal elements.
   $1111,$ i.e. a total of $1$ case;


3. $b=c$ : $1122, 1133, 1144, 1155, 1155, 1166, 1177, 1188, 1199,$ i.e. a total
   of $8$ cases.

The sum of the $3$ cases above = $8+1+8=17$.

For the $9$ values possible for $a$, have $17*9 = 153$ values.

Still need $81 = (234 - 153)$ values more.

Next consider that similar error occurs for $abbc, abcc$ list types.

Also, have only $9$ possible numbers for $aabc$, with $a=b=c$ & they have been all accounted in case $2$ above.

For the rest $81$ values by the analysis of common extra cases generated by $abbc, abcc$ list types, see as below:

1 . There are $9$ cases given by the lists of type $abbc$ with $b=c$.

2 . There are $72$ lists of the type given by $abcc$ with $a=bne c$, as there are $8$ such cases for each of the $9$ values of $c$.

We shouldn't be looking for $234$ objects that are counted multiple times, because there are only $225$ of them.

Define $A$, $B$, $C$ those sets of elements where their first two, second two, and the last two positions are to be the same respectively.

We have $|A|+|B|+|C|=2187$.

but actually, the quantity of interest is

$$|A|+|B|+|C|- [|A cap B| + |B cap C| + |A cap C| -|A cap B cap C| ]=1953$$

We have

$$|A cap B| + |B cap C| + |A cap C| -|A cap B cap C| = 234$$

Note that

• $(A cap B) setminus (A cap B cap C), $


• $(B cap C) setminus (A cap B cap C)$


• $(A cap C) setminus (A cap B cap C), $


• $A cap B cap C$

are disjoint and computing the sum of their cardinality is just computing the quantity of those elements that are counted for more than once.

The quantity that are over counted is

$$|A cap B| + |B cap C| + |A cap C| -2|A cap B cap C| = 234- |A cap B cap C|$$

$$81+81+81 - 2(9)=234-9=225$$

Those $225$ elements consists of the form of $aaab, aabb, abbb$ where $ a ne b$ each of them have $72$ elements and $9$ copies of the form of $aaaa$.

$$72 times 3 + 9 =225$$

Edit:

Let $R_i$ denotes region $i$.

$|A|= sum_i in 1,2,4,5|R_i|$, do the same thing for $|B|$ and $|C|$ and we can see how many times region $5$ is counted.