5
$\begingroup$

The word 'KBCKBCKBC' is to be arranged in a row such that no word contains the pattern of KBC.

$Attempt$

Event $A$=1st KBC is in the pattern, $B$=2nd KBC is in the pattern and similar is the event C.

Now required is $n((notA) (notB) (notC)) =Total ways - [\sum n(A) - \sum n(AB)+ \sum n(ABC)] $

Total ways = $\frac{9!}{3!3!3!}$

$\sum n(AB) = \frac{5!}{2!}$

$\sum n(ABC) = 1$

But, my main doubt is that I am not able calculate $\sum n(A)$.

Any suggestion? Also please suggest about different method you know.

Thanks for the help.

$\endgroup$
  • $\begingroup$ The tag (self-learning) is intended to be used for questions about the pedagogy of learning on your own (e.g. "I am studying X subject on my own but don't have anyone to grade my work. How can I make sure I am improving?"). It is not to be used for a question about the topic you are studying just because you are studying on your own. $\endgroup$ – JMoravitz Jan 26 at 18:15
  • 3
    $\begingroup$ As for approaching this... my first impression would be to have events $A_1,A_2,A_3,\dots,A_7$ where the event $A_i$ corresponds to the event that positions $i,i+1,i+2$ contain the characters $K,B,C$ respectively and running inclusion-exclusion over this. Note: $|A_i|=\frac{7!}{2!2!2!}$ and $|A_i\cap A_j|=\begin{cases}0&\text{if they overlap}\\\frac{5!}{2!}\end{cases}$ $\endgroup$ – JMoravitz Jan 26 at 18:17
3
$\begingroup$

The number of valid words is \begin{align*} \frac{9!}{3!3!3!}-\frac{7!}{2!2!2!1!}+\frac{5!}{1!1!1!2!}-\frac{3!}{3!}=1\,680-630+60-1\color{blue}{=1\,109} \end{align*}

Comment:

  • We consider words of length $9$ built from three groups $BBB,CCC,KKK$, resulting in $\frac{9!}{3!3!3!}$.

  • We subtract all words which have at least one occurrence of $BCK$. We think of $BCK$ as a new character $X$. We consider words of length $7$ built from $4$ groups $BB,CC,KK,X$, resulting in $\frac{7!}{2!2!2!1!}$.

  • We have subtracted strings with occurrences of two times $BCK$ more than once. As compensation we add all words which contain at least two times $BCK$. We think of $BCK$ as a new character $X$. We consider words of length $5$ built from $4$ groups $B,C,K,XX$, resulting in $\frac{5!}{1!1!1!2!}$.

  • We have added strings with occurrences of three times $BCK$ more than once. As compensation we subtract all words which contain at least three times $BCK$. We consider words of length $3$ built from $1$ group $XXX$, resulting in $\frac{3!}{3!}$.

$\endgroup$
2
$\begingroup$

It seems you are considering only the three cases, when $KBC$ appears in the front, center and end. In fact, it may appear at other locations as noted by JMoravitz in the comment.

Let $A_1,A_2,...,A_7$ indicate the starting position of the block $KBC$. So, $A_1,A_4,A_7$ correspond to your cases $A,B,C$. Using inclusion-exclusion, the number of words with one, two or three word blocks $KBC$ is: $$|A_1|+|A_2|+|A_3|+|A_4|+|A_5|+|A_6|+|A_7|-\\ (|A_1A_4|+|A_1A_5|+|A_1A_6|+|A_1A_7|+|A_2A_5|+\\ |A_2A_6|+|A_2A_7|+|A_3A_6|+|A_3A_7|+|A_4A_7|)+\\ (|A_1A_3A_7|)=\\ 7\cdot \frac{6!}{(2!)^3}-10\cdot 3!+1=630-60+1=571.$$ Note: Many overlapping events such as $A_1A_2,A_1A_2A_3,A_1A_2A_3A_4,$ etc are dropped in the above expression and only the events with non-zero cardinality are preserved.

The total number of words is: $$\frac{9!}{(3!)^3}=1680.$$ Hence, the number of words without the word block $KBC$ anywhere in the $9$-letter word is: $$1680-571=1109.$$

$\endgroup$
  • $\begingroup$ Nice presentation. (+1) $\endgroup$ – Markus Scheuer Jan 27 at 13:16
  • 1
    $\begingroup$ Thank you for the appraisal! $\endgroup$ – farruhota Jan 27 at 13:44
  • $\begingroup$ @farruhota No, I considered all the situations like 'KBKBCKCB'. But, at that time, I was not able to figure out how to account these change in $\sum n(A)$. Also, I think I wrote less about my thinking and so, that may be generating the impression that I considered only selective examples. But, thanks for helping me and clearing my doubt and suggesting about the another method of just considering the places rather the whole pattern of KBC. Thanks a lot. :) $\endgroup$ – jayant98 Jan 27 at 18:26
2
$\begingroup$

This answer is based upon the Goulden-Jackson Cluster Method which is a convenient method to derive a generating function for problems of this kind.

We consider the set of words in $ \mathcal{V}^{\star}$ of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{B,C,K\}$$ and the set $\mathcal{B}=\{KBC\}$ of bad words, which are not allowed to be part of the words we are looking for.

We derive a function $F(x)$ with the coefficient of $x^n$ being the number of wanted words of length $n$ from the alphabet $\mathcal{V}$. According to the paper (p.7) the generating function $F(x)$ is \begin{align*} F(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})} \end{align*} with $d=|\mathcal{V}|=3$, the size of the alphabet and with the weight-numerator $\mathcal{C}$ with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[KBC]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[KBC])&=-x^3 \end{align*}

It follows with some help of Wolfram Alpha \begin{align*} F(x)&=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-3x+x^3}\\ &=1 + 3 x + 9 x^2 + 26 x^3 + 75 x^4 + 216 x^5+622 x^6 \\ &\qquad+ 1\,791 x^7 + 5\,157 x^8 + \color{blue}{14\,849} x^9+42\,756 x^10 +\cdots\tag{1}\\ \end{align*}

Denoting with $[x^n]$ the coefficient of $x^n$ in a series we see in (1) there are $\color{blue}{14\,849}$ words of length $9$ which do not contain the string $KBC$.

We want to find all words which have exactly three occurrences of each of the letters $B,C,K$. In order to find this number we have to keep track of the letters in the generating function $F(x)$. We do so be setting \begin{align*} \color{blue}{G(x)}&\color{blue}{=\frac{1}{1-(B+C+K)x+(BCK)x^3}} \end{align*} and we obtain by extracting the coefficient of $B^3C^3D^3x^9$ of $G(x)$ again with some help of Wolfram Alpha \begin{align*} [B^3C^3D^3t^9]G(x)\color{blue}{=1\,109} \end{align*}

Note this example is relatively simple, since we have only one bad word and this word has no overlapping. A situation with a bad word with overlapping for instance with $BCB$ is harder to calculate and in such cases this method shows more of its power.

$\endgroup$
  • $\begingroup$ wow! that worked relatively simpler for your example of bcb. thanks for the new method. $\endgroup$ – jayant98 Jan 27 at 18:21
  • $\begingroup$ @jayant98: You're welcome. $\endgroup$ – Markus Scheuer Jan 27 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.