Re-visit : Combinatorics involving 3 adjacent objects

Question

$\underline{\text{Overview}}$

This is a self-answer re-posting of this currently active MathSE question, which will likely be closed without an answer, since it violates MathSE protocol. I consider the question worthwhile, so I am re-posting, with a solution.

For what it's worth, I did try to check if the question/answer was a duplicate. I did find this answer, but I had trouble determining how to modify the answer to fit my problem.

---

$\underline{\text{The Problem}}$

If you have n books and m consecutive places, where m is bigger than n, how many combinations are there so that no 3 books sit next to each other? 2 books can be adjacent but not three in a row.

I am interpreting this question as intending that the books are indistinguishable from each other. For the alternative assumption, you can simply apply the $~n!~$ scalar to the answer.

Part of the reason that I value this question is because I find it much more difficult than the simpler question of no 2 books in a row. The simpler question immediately yields to Stars and Bars, which is also discussed here:

• $x_1 + x_2 + \cdots + x_n = m.$
• $x_1, x_n \in \Bbb{Z_{\geq 0}}.$
• $x_2, x_3, \cdots, x_{n-1} \in \Bbb{Z_{\geq 1}}.$

Simply apply the change of variables $~y_i = x_i - 1 ~: ~i \in \{2,3,\cdots, n-1\},~$ and everything falls into place.

That approach won't work with the current problem. Also, I think that Inclusion-Exclusion would be a nightmare, because you would have to make an attempt to diagnose varying patterns in the intersections of $~r~$ triplet subsets. A separate diagnosis would be needed for each $~r~$ in $~\displaystyle \left\{1,2,\cdots,(m-2)\right\}.$

Since I am ignorant of generating functions, I have no idea whether such an approach is viable.

For me, that leaves recursion. Solution follows.

Answer 1

Disclaimer

This answer does not provide a closed form solution, but hopefully provides some additional insights.

Set Up

Put the books into small and large boxes. Each small box stores one book and takes one place. Each large box stores two books and takes two places. There is at most one box between two consecutive empty places, at most one box before the first empty place, and at most one box after the last empty place.

Calculation

Put the books into $r$ large boxes and $n-2r$ small boxes, so we have a total of $n-r$ boxes. Since the books occupy $n$ places, there are $m-n$ empty places. The number of ways to put the box among the empty places is:

$$ \binom{m-n+1}{n-r} $$

After deciding where to put the box, we need to choose which boxes are the large boxes. The number of possibilities:

$$ \binom{n-r}{r} $$

Therefore, the total number of ways is the product of the two binomial coefficients above, summed over all possible $r$ values:

$$ f(m,n)= \sum_{r=0}^{\left\lfloor n/2\right\rfloor} \binom{m-n+1}{n-r}\binom{n-r}{r} $$

Answer 2

$\underline{\text{Upper Bound For} ~n}$

You are never allowed to place 3 books in a row. This means that for any $~3~$ consecutive places, at least one of them must be empty. Therefore, given $~m~$ places, at least $~\displaystyle \left\lfloor \frac{m}{3}\right\rfloor~$ places must be left empty.

Therefore, you must have

$$n \leq m - \left\lfloor \frac{m}{3}\right\rfloor. \tag1 $$

The following tableau illustrates that for both $~m = 6~$ and $~m = 5,~$ the maximum allowable value of $~n~$ is $~n=4.$

XX_XX
XX_XX_

So, without loss of generality, it is assumed that the inequality in (1) above holds.

---

$\underline{\text{Recursion Formulas}}$

Let $~P(m,n)~$ denote the set of all satisfying placements of $~n~$ books in $~m~$ positions, where $~n,m~$ are any two positive integers that satisfy the inequality in (1) above.

For $~k \in \{0,1,2\},~$ let $~P(m,n,k)~$ denote the subset of $~P(m,n)~$ where the rightmost $~k~$ positions each contain a book, and the position immediately preceding these $~k~$ positions is empty. For example, $~P(m,n,2)~$ represents that the rightmost $~2~$ positions have a book, and the 3rd position from the right is empty.

Let $~f(m,n)~$ denote the number of elements in $~P(m,n).~$
For $~k \in \{0,1,2\},~$ let $~f(m,n,k)~$ denote the number of elements in $~P(m,n,k).~$

To facilitate expressing formulas, I am going to expand the domain of the $~f(m,n)~$ and $~f(m,n,k)~$ functions:

$$\text{For} ~n > m - \left\lfloor \frac{m}{3}\right\rfloor, ~0 = f(m,n) = f(m,n,0) = f(m,n,1) = f(m,n,2). \tag2 $$

Then:

• $f(m,n) = f(m,n,0) + f(m,n,1) + f(m,n,2).$

• $f(m,n,2) = f(m-1,n-1,1).$
  That is, you form an element in $~P(m,n,2)~$ by adding a book to the end of an element in $~P(m-1,n-1,1).$

• $f(m,n,1) = f(m-1,n-1,0).$
  That is, you form an element in $~P(m,n,1)~$ by adding a book to the end of an element in $~P(m-1,n-1,0).$

• $\displaystyle f(m,n,0) = f(m-1,n)$
  That is, you form an element in $~P(m,n,0)~$ by adding an empty space to the end of any element in $~P(m-1,n).$

The above formulas imply that

• $~f(m,n,1) = f(m-1,n-1,0) = f(m-2,n-1).$
• $~f(m,n,2) = f(m-1,n-1,1) = f(m-3,n-2).$

Therefore:

$$f(m,n) = f(m,n,0) + f(m,n,1) + f(m,n,2) = f(m-1,n) + f(m-2,n-1) + f(m-3,n-2). \tag3 $$

The equation in (3) above can be used to enumerate $~f(m,n)~$ by recursively building a two dimensional table, that starts with the following initial formulas:

• $\displaystyle f(m,1) = \binom{m}{1}.$
• $\displaystyle f(m,2) = \binom{m}{2}.$

So, you start with a table that looks like this:

$f(m,n)~$ table: \begin{array}{| r | r | r |} \hline n\backslash m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 2 & 0 & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 \\ \hline 3 & 0 & 0 & 0 \\ \hline 4 & 0 & 0 & 0 \\ \hline 5 & 0 & 0 & 0 \\ \hline 6 & 0 & 0 & 0 \\ \hline 7 & 0 & 0 & 0 \\ \hline 8 & 0 & 0 & 0 \\ \hline \end{array}

Then, you apply the formula in (3) above, recursively to produce:

$f(m,n)~$ table: \begin{array}{| r | r | r |} \hline n\backslash m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 2 & 0 & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 \\ \hline 3 & 0 & 0 & 0 & 2 & 7 & 16 & 30 & 50 & 77 & 112 \\ \hline 4 & 0 & 0 & 0 & 0 & 1 & 6 & 19 & 45 & 90 & 161\\ \hline 5 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 16 & 51 & 126 \\ \hline 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 10 & 45 \\ \hline 7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 \\ \hline \end{array}

Answer 3

The number of ways to place $n$ books in $m$ spaces, with at most one book per space, such that no three books occupy three consecutive spaces, is equal to $$ \text{the coefficient of }\;\;x^ny^{m-n} \;\;\text{ in the bivariate series } \frac{1 + x + x^2}{1 - y(1 + x + x^2)}. $$ For example, when $n=3$ and $m=9$, this piece of Mathematica code evaluates to $77$, so there are $77$ ways in this case.

n = 3;
m = 9;
SeriesCoefficient[(1 + x + x^2)/(1 - y(1 + x + x^2), {x, 0, n}, {y, 0, n - m}]

You can check this on Wolfram Alpha.