Find number of ways to form a string of length n using k characters such that at most two adjacent characters can be same.
I tried to solve this problem in two parts:
1. Find number of strings of length n using k characters so that no adjacent character are same .
2. Find number of string of length n using k characters so that there exists at least one pair of exactly two adjacent same characters (and there cannot be more than two adjacent characters same) .
For the first part I approached it as:
no. of ways to put a character on string position 1 = k
no. of ways to put a character on string position 2 = k-1 (as it must be different from last used character)
.
.
no. of ways to put a character on string position n = k-1
:
So no. of strings = k(k-1)(k-1).... n-1 times = k(k-1)^(n-1)
Now for the second part there could be any(1 to n/2) number of pairs of same adjacent characters but I don't understand how to approach this.
Could anyone please help?
Best Answer
This question is kinda weird since you didn't say anything about repetition. Supposing our sequence of length n allows repetition, here is how I would approach it:
We want to create sequences of length n from a set of $k$ characters allowing repetition with the constraint that at most two adjacent characters can be the same.
Let's use the inclusion-exclusion principle.
First, the number of sequences of length $n$ from $k$ elements allowing repetition is: $k^n$.
Now let's define the following sets for $ 3 \leq p \leq n$: $$ S_p=\{\text{Sequences of length n with p adjacent characters the same}\} $$ Therefore our final answer is: $k^n- |\bigcup_{p=3}^n S_p|$. Let's then calculate the cardinality of that union.
Clearly those sets are all disjoint, therefore: $$ |\bigcup_{p=3}^n S_p| = |S_3| + |S_4| + \cdots + |S_n| $$ And we can use the following strategy to calculate the cardinality of $|S_p|$: From our $k$ characters, select $1$ and place it in $p$ adjacent positions. There are $n-p+1$ possibilities to choose adjacent positions. Now we need to let the remaining $n-p$ positions to select, without repetition, characters from the $k-1$ remaining, and that can be done in $(k-1)(k-2)\cdots (k-n+p)=\frac{(k-1)!}{(k-n+p-1)!}$ ways. Therefore, by multiplication principle we get: $$ |S_p|=k\cdot (n-p+1) \cdot \frac{(k-1)!}{(k-n+p-1)!} = \frac{k!(n-p+1)}{(k-n+p-1)!} $$ which follows that: $$ |\bigcup_{p=3}^n S_p| = \sum_{p=3}^{n} \frac{k!(n-p+1)}{(k-n+p-1)!} $$ Finally, our answer is: $$ k^n - \sum_{p=3}^{n} \frac{k!(n-p+1)}{(k-n+p-1)!} $$
Sanity Check: Suppose $n=4$ and $K=\{a,b\}$. Therefore all sequences are: \begin{align*} (a,a,a,a)&\\ (a,a,b,b)&,(a,b,a,b)\\ (a,a,a,b)&,(a,a,b,a),(a,b,a,a),(b,a,a,a)\\ (b,b,b,b)&\\ (b,b,a,a)&,(b,a,b,a)\\ (b,b,b,a)&,(b,b,a,b),(b,a,b,b),(a,b,b,b)\\ (b,a,a,b)&,(a,b,b,a) \end{align*} There are $2^4=16$ sequences. Removing the ones that we don't want to count, that is, sequences with three or more adjacent repetitions, we have the remaining sequences: $$ (a,a,b,b),(a,b,a,b)\\ (a,a,b,a),(a,b,a,a)\\ (b,b,a,a),(b,a,b,a)\\ (b,b,a,b),(b,a,b,b)\\ (b,a,a,b),(a,b,b,a) $$ There are $10$ sequences. Now let's check if our answer is going to validate to the same number: \begin{align*} k^n - \sum_{p=3}^{n} \frac{k!(n-p+1)}{(k-n+p-1)!} &= 2^4 - \frac{2!(4-3+1)}{(2-4+3-1)!} - \frac{2!(4-4+1)}{(2-4+4-1)!}\\ &= 16 - \frac{2!(2)}{(0)!} - \frac{2!(1)}{(1)!}\\ &= 16 - 4 - 2 = 10 \end{align*} So it seems to make sense. I'm not sure if it's 100% correct, but that's what I've done to try to solve it. Hope it helps!