# Find number of ways to seat $n$ boys and $n$ girls in a row so that every boy has at least one girl sitting beside him.

My attempt: I am getting $2^n(n!)^2$ .

First I paired $n$ boys and $n$ girls in $n!$ ways then these pairs can be arranged in $n!$ ways and in each of these pairs boy and girl can arrange themselves in $2!$ ways.

• Do it with $2,3$ (girls boy) and then generalize – Archis Welankar Feb 5 '16 at 5:07
• You can never get GGBBGB in your count, but it is valid and has the same number of girls and boys like you require – Ross Millikan Feb 5 '16 at 5:19
• I also get $2^n(n!)^2$, by taking $n = 1, 2, 3$. – Max Payne Feb 5 '16 at 6:07
• @Tim: Well how are you getting it? Is your method counting GGBBBG as a solution (incorrectly) and also missing Ross's solution? – user21820 Feb 5 '16 at 6:10
• @user21820 Why would i count GGBBBG? no 3 boys could occur together, and 2 boys cant be at terminal end. keeping that in mind, i found it to be $2^n(n!)^2$ And yes GGBBGB will be a valid count, but what i think Ross means is that we will be unable to count GGBBGB.. – Max Payne Feb 5 '16 at 6:24

Begin with seating $n$ indistinguishable girls leaving ample space between and around them, like so: $$\ \underline{\ \ }\ G\ \underline{\ \ }\ G\ \underline{\ \ }\ G\ \underline{\ \ }\ \ldots\ \underline{\ \ }\ G\ \underline{\ \ }\ G\ \underline{\ \ }\quad .$$ An admissible seating pattern can then be constructed as follows:

• Choose an $r$ with $0\leq2r\leq n$.

• Choose $r$ of the $n-1$ inner spaces between the $G$s, and write $B^2$ there. This can be done in ${n-1\choose r}$ ways.

• Choose $n-2r$ of the remaining $n+1-r$ spaces, and write a single $B$ there. This can be done in ${n+1-r\choose n-2r}$ ways.

The total number $P(n)$ of admissible seating patterns therefore comes to $$P(n)=\sum_{r=0}^{\lfloor n/2\rfloor}{n-1\choose r}\>{n+1-r\choose n-2r}\qquad(n\geq1)\ ,$$ producing the sequence $(2,4,10,26,70,192,\ldots)$, as in Markus Scheuer's answer. Making girls as well as boys distinguishable then gives the number
$$N=(n!)^2 P(n)$$ of personalized seatings.

• Very nice. I was already curious and awaiting your answer similar to your answer of the question I'm referring to :-) (+1) – Markus Scheuer Feb 12 '16 at 14:55

Note: Here we state generating functions for OPs sequence $(g_n)_{n\geq 1}=(2,4,10,26,\ldots)$ and show that the numbers are the sum of consecutive central trinomial coefficients.

If we encode boys with $0$ and girls with $1$, we are looking for binary strings of length $2n$ with the following constraints:

• The number of $0$'s is equal to the number of $1$'s, since we have the same number of boys and girls.

• A substring $000$ is not contained, which corresponds to a configuration BBB and the boy in the middle has not a girl beside him.

• The string must not start with $00$ and must not end with $00$, since then a boy at the beginning resp. at the end has not a girl beside him.

According to my computations the sequence $(g_n)_{n\geq 1}$ starts with \begin{align*} 2,4,10,26,70,192,534,1500,4246,12092 \end{align*}

The valid configurations for small $n=1,2,3$ are \begin{align*} n=1\qquad&01,10\\ n=2\qquad&0101,0110,1001,1010\\ n=3\qquad&010011,010101,010110,011001,011010\\ &100101,100110,101001,101010,110010 \end{align*}

Feeding OEIS with these values gives us the sequence A025565. Denoting this sequence with $a_n, n\geq 1$, the entries $a_{n+1}$ give the number of UDU free paths of $n$ upsteps (U) and n downsteps (D).

The generating function is \begin{align*} A(x)&=\sum_{n=1}^{\infty}a_nx^n=x\sqrt{\frac{1+x}{1-3x}}\\ &=x+2x^2+4x^3+10x^4+26x^5+70x^6+192x^7+\cdots \end{align*}

[2016-02-12]

A regular expression

We can find a regular expression for all binary strings which do not contain three consecutive $0$'s and which do also not contain $00$ at the beginning and at the end of the string. This was already stated by @gar in the related example as

\begin{align*} ((1+01)1^*0)^*(\varepsilon+(1+01)1^*)\tag{1} \end{align*}

Comment:

• $(1+01)$ means we can either start with a girl or a boy followed by a girl

• This may be followed by zero or more occurrences of girls followed by a boy

• This expression may occur zero or more times which gives $((1+01)1^*0)^*$

• The string may end this way $(\varepsilon)$ or end with the sequence $(1+01)1^*$

Note the binary strings described by (1) do not respect that we need the same number of boys and girls. We will deal with it somewhat later.

Using the notation from P. Flajolet's and R. Sedgewicks Analytic Combinatorics we can write the regular expression as

\begin{align*} SEQ((y+xy)SEQ(y)x)(1+(y+xy)SEQ(y)) \end{align*}

with the sequence $SEQ(x)$ defined as \begin{align*} SEQ(x)=1+x+x^2+\cdots=\frac{1}{1-x} \end{align*}

We can now state for (1) the corresponding generating function \begin{align*} S(x,y)&=\frac{1}{(y+xy)\frac{1}{1-y}x}\left(1+(y+xy)\frac{1}{1-y}\right)\\ &=\frac{1+xy}{1-y(1+x+x^2)}\tag{2} \end{align*}



Another generating function

Since we are looking for strings with the same number of $0$'s and $1$'s we extract the diagonal from $S(x,y)$. We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. We obtain

A generating function $G(t)=\sum_{n\geq 1}g_nt^n$ for OPs sequence $2,4,10,26,70,192,\ldots$ is \begin{align*} G(t)&=[x^0]S\left(x,\frac{t}{x}\right)\\ &=[x^0]\frac{1+x\frac{t}{x}}{1-\left(x+1+\frac{1}{x}\right)t}\\ &=[x^0]\frac{1+t}{1-\left(x+1+\frac{1}{x}\right)t}\tag{3}\\ \end{align*}

Central trinomial coefficients

Note the coefficient of $x^0$ in \begin{align*} [x^0](x+1+\frac{1}{x})^k\qquad\qquad k\geq 0 \end{align*} are the centrial trinomial coefficients.

We obtain from (3) for $n\geq 1$ \begin{align*} [t^n]G(t)&=[t^n][x^0](1+t)\sum_{k\geq 0}\left(x+1+\frac{1}{x}\right)^kt^k\\ &=[t^n+t^{n-1}][x^0]\sum_{k\geq 0}\left(x+1+\frac{1}{x}\right)^kt^k\\ &=[x^0]\left(x+1+\frac{1}{x}\right)^n+[x^0]\left(x+1+\frac{1}{x}\right)^{n-1} \end{align*}

Since for $n\geq 0$ \begin{align*} [x^0]\left(x+1+\frac{1}{x}\right)^n &=[x^0]\sum_{k=0}^n\binom{n}{k}\left(x+\frac{1}{x}\right)^k\\ &=[x^0]\sum_{k=0}^n\binom{n}{k}\sum_{j=0}^k\binom{k}{j}x^{2j-k}\\ &=[x^0]\sum_{k=0}^{n}\binom{n}{2k}\sum_{j=0}^{2k}\binom{2k}{j}x^{2j-2k}\\ &=\sum_{k=0}^{n}\binom{n}{2k}\binom{2k}{k} \end{align*}

We finally obtain the following expression for OPs sequence $(g_n)_{n\geq 1}$ \begin{align*} g_n=[t^n]G(t)&=\sum_{k=0}^{n}\binom{n}{2k}\binom{2k}{k} +\sum_{k=0}^{n-1}\binom{n-1}{2k}\binom{2k}{k} \end{align*}

The central trinomial coefficients $c_n$ can be found in OEIS as A002426. We get \begin{array}{rlllllll} c_n&1&1&3&7&19&51&141\\ g_n=c_n+c_{n-1}&&2&4&10&26&70&192 \end{array}

With a perspective of keeping it simple and $z$ representing boys and $w$ representing girls we get the generating function

$$(1+z) \left( \sum_{q\ge 0} \left(\frac{w}{1-w} (z+z^2)\right)^q \right) \frac{w}{1-w} (1+z).$$

This is $$(1+z)^2 \frac{w}{1-w} \frac{1}{1-w(z+z^2)/(1-w)} = w (1+z)^2 \frac{1}{1-w-w(z+z^2)}.$$

Extracting coefficients from this we get

$$[w^n] w (1+z)^2 \frac{1}{1-w-w(z+z^2)} = (1+z)^2 [w^{n-1}] \frac{1}{1-w(1+z+z^2)} \\ = (1+z)^2 (1+z+z^2)^{n-1} = (1+z+z^2)^{n} + z (1+z+z^2)^{n-1}.$$

This yields as the answer the two trinomial coefficients $$[z^n] (1+z+z^2)^{n} + [z^n] z (1+z+z^2)^{n-1} \\ = [z^n] (1+z+z^2)^{n} + [z^{n-1}] (1+z+z^2)^{n-1}.$$

Extracting coefficents we get for the first term $$[z^n] \sum_{q=0}^n {n\choose q} z^q (1+z)^q = \sum_{q=0}^n {n\choose q} {q\choose n-q}$$

$$\sum_{q=0}^n {n\choose q} {q\choose n-q} + \sum_{q=0}^{n-1} {n-1\choose q} {q\choose n-1-q}.$$

Given that we have an excellent answer the above can perhaps provide a slightly different perspective, thereby facilitating a better understanding of the computation.

• Thanks for your nice comment. Maybe you also would like to present the corresponding regular expression $(\varepsilon+0)(1^+0(\varepsilon+0))^*1^+(\varepsilon+0)$ in your answer, which could be nice for comparison. (+1) – Markus Scheuer Feb 13 '16 at 22:15
• I checked your RE and I will keep it in the comments. – Marko Riedel Feb 13 '16 at 22:31

Start with two lines, one of boys and one of girls, and imagine constructing the arrangement by picking the first person in one of the lines. You get a factor of 2 every time the choice can be from either line.

This construction is useful because no seating arrangement is double counted, which can be seen by noting that you can retrieve the order the boys (or girls) were in in their monogender lines by skipping the people of another gender.

• Beautiful! So it's $n! \cdot n! \cdot 2^\text{(however many times the choice can be from either line)}$? Is there a nice closed form? – Eli Rose -- REINSTATE MONICA Feb 5 '16 at 5:59
• No form fixed its wrong – Archis Welankar Feb 5 '16 at 7:55
• @EliRose: It's not even of that form. See my answer. – user21820 Feb 5 '16 at 7:56
• @user21820: Interesting. I can see that some of the numbers in your table are odd, so it must not be, but why isn't it? Does it have to do with the fact that whether the current choice can be from either line depends on the last choice? – Eli Rose -- REINSTATE MONICA Feb 5 '16 at 15:08
• @EliRose: Absolutely right. You can't multiply when the number of ways of performing each subtask is not independent of the history of choices. – user21820 Feb 5 '16 at 15:11