No. of ways to arrange 4R and 3L so that there is exactly 4 times change from L to R or R to L.

Question

I have to arrange 4R and 3L in such a way to know number of times there is 4 changes in the alphabet of sequence. For instance consider the sequence RLRLLRR, this sequence has 4 places where R and L are changing.Is there any way to find out using permutation and combination without actually writing all the sequences.

Answer 1

As a general remark, note that the number of ways to write $n$ as sum of $k$ positive integers is $n-1\choose k-1$: lay down $n$ tokens in a line and group them according to a way to write $n$ as sum of $k$ positive integers; then mark the first token in each of the $k$ summands. This effectively marks the first token as well as $k-1$ out of the $n-1$ remaining tokens, hence the total count is $n-1\choose k-1$.

For four changes the format of the string must be either $R^aL^bR^cL^dR^e$ with $a,b,c,d,e\ge 1$, $a+c+e=4$, $b+d=3$; or $L^aR^bL^cR^dL^e$ with $a,b,c,d,e\ge 1$, $a+c+e=3$, $b+d=4$.

For the first variant, we count the number of ways to write $4$ as a sum of three positive integers, that is: ${3\choose 2}=3$; and we count the number of ways to write $3$ as sum of two positive integers, that is: ${2\choose 1}=2$.

For the second variant, we count the number of ways to write $4$ as sum of two positive integers, that is: ${3\choose 1}=3$; and we count the number of ways to write $3$ as sum of $3$ positive integers, that is: ${2\choose 2}=1$.

Hence the total count is $$ 3\cdot 2+3\cdot 1=9.$$

Answer 2

The regular expression for the required sequence of exactly four such changes is:

\begin{align*} {\rm r\, r^{*}l\, l^{*}r\, r^{*}l\, l^{*}r\, r^{*}+l\, l^{*}r\, r^{*}l\, l^{*}r\, r^{*}l\, l^{*}} \end{align*}

As described in the book ``analytic combinatorics'' by Flajolet and Sidgewick, we can obtain the following bivariate generating function:

\begin{align*} G(x,y) &= \frac{x^2y^2\left(x+y-2\, x\, y\right)}{\left((1-x)\,(1-y)\right)^3} \end{align*}

The coefficient $[x^my^n]$ gives the number of sequences for $m$ R and $n$ L, and for this g.f, it's possible to extract the formula for the coefficients, which is:

\begin{align*} A\left(m,n\right) &= \binom{m-1}{2}\, \binom{n}{2}+\binom{m}{2}\, \binom{n-1}{2}-2\, \binom{m-1}{2}\, \binom{n-1}{2} \end{align*}

Hence,

\begin{align*} A(4,3) &= 9 \end{align*}