7
$\begingroup$

Find the number of ways of selecting k cells from a $(2\times n)$-board such that no two selected cells share a side (non-adjacent).

For $n=3$ and $k=2$, the answer is $8$; for $n=5$ and $k=3$, the answer is $38$.

Counting manually works for small numbers.

Question. Is there any formula that can be derived for large numbers?

$\endgroup$
4
  • $\begingroup$ @JoeSilverman: I was about to suggest that too, however, this is quite specialized, I'd say. But routine for those who have done it before... $\endgroup$ Oct 12, 2018 at 15:17
  • $\begingroup$ For small values of k you can use N(n,1)=2n and the recursion N(n,k)=N(n-1,k)+2*N(n-1,k-1). This is like Per's solution, using top-bottom symmetry, but hides some detail (and I left out a piece for you to find). This would be a good exercise for a beginning combinatorics class. If you can fully explain the recursion above, you have solved the exercise. Gerhard "Do I Get An Apple?" Paseman, 2018.10.12. $\endgroup$ Oct 12, 2018 at 16:03
  • $\begingroup$ Oops. I miscounted. N(n,k)=N(n-1,k-1)+N(n-1,k). The full explanation of the previous recursion becomes a bonus problem. Gerhard "Always, ALWAYS Check Your Work" Paseman, 2018.10.12. $\endgroup$ Oct 12, 2018 at 16:21
  • $\begingroup$ Btw, should you not solve the homework given by Petter Branden by yourself? $\endgroup$ Oct 17, 2018 at 11:02

3 Answers 3

9
$\begingroup$

$\dots$ continued from above: to find the coefficient of $t^nq^k$, rewrite the generating function as \begin{align}G(t,q):=\frac{t+(2t+t^2)q}{1-t-(t+t^2)q} &=\frac{t+(2t+t^2)q}{1-t}\cdot\frac1{1-\left(\frac{t+t^2}{1-t}\right)q} \\ &=\frac{t+(2t+t^2)q}{1-t}\sum_{j\geq0}\left(\frac{t+t^2}{1-t}\right)^jq^j \\ &=\sum_{k\geq0}\left(\frac{2t^k(1+t)^{k-1}}{(1-t)^{k+1}}\right)q^k. \end{align} Further calculation reveals that $$\frac{2t^k(1+t)^{k-1}}{(1-t)^{k+1}} =\sum_{n\geq0}\left(2\sum_{r=0}^{n-k}\binom{n-r}k\binom{k-1}r\right)t^n.$$ In summary, the enumeration you seek becomes the coefficient of $t^nq^k$ given by $$2\sum_{r=0}^{n-k}\binom{n-r}k\binom{k-1}r.$$ This confirms your calculations: if $n=3, k=2$ then you get $8$; if $n=5, k=3$ then you get $38$.

$\endgroup$
4
  • 1
    $\begingroup$ That sum may have a combinatorial proof. $\endgroup$ Oct 12, 2018 at 19:05
  • 1
    $\begingroup$ That is what I anticipate. Go for it. :-) $\endgroup$ Oct 12, 2018 at 19:40
  • $\begingroup$ So that summation can be reduced to an identity? $\endgroup$ Oct 12, 2018 at 21:10
  • $\begingroup$ No, it can not be reduced. $\endgroup$ Oct 12, 2018 at 21:40
8
$\begingroup$

Let $P_n(q)$ be the polynomial such that the coefficient of $q^k$ is the number of $2\times n$-strips with $k$ selected boxes.

Furthermore, let $A_n(q)$, $B_n(q)$ and $C_n(q)$ be the same sequences but with restriction that the strip ends with A) one selected square at the top, B) one selected square at the bottom, and C) no selected squares.

We have due to symmetry that $A_n(q)=B_n(q)$. Also, $A_1(q)=q$, $C_1(q)=0$.

We can then quite easily see that $$ A_n(q) = q B_{n-1}(q)+qC_{n-1}(q), B_n(q) =A_{n-1}(q)+ B_{n-1}(q)+C_{n-1}(q) $$ or $$ A_n(q) = q B_{n-1}(q)+q A_{n-1}(q), B_n(q) =2A_{n-1}(q)+ B_{n-1}(q). $$ From this, (with some algebra) we can then conclude that $$ A_n(q) = (q+1)A_{n-1}(q) + q A_{n-2}(q) \qquad (\ast) $$ and $$ B_{n}(q)= (2+1/q)A_{n-1}+A_{n-2} $$ so if we can solve the recursion in $(\ast)$, we are done. With some generating functions, you can see that $$ \sum_{j=0}^\infty A_j(q)t^j = \frac{q t}{1-(q+1)t-qt^2} \quad \sum_{j=0}^\infty B_j(q)t^j = \frac{q t^2+t}{1-(q+1)t-qt^2}. $$ It follows that the series you seek is $$ \sum_{j=0}^\infty t^jP_j(q) = \frac{2 q t + q t^2 + t}{1 - (q + 1) t - q t^2}. $$ So, the answer to your original question is therefore $$ \frac{2 q t + q t^2 + t}{1 - (q + 1) t - q} {\Big\vert}_{t^nq^k} $$ so that the number of $2\times n$-strips with $k$ selected squares is the coefficient of $t^nq^k$ in the above rational function.

$\endgroup$
1
  • $\begingroup$ Say for eg n=5,k=3 how do I use this rational function to solve the problem? $\endgroup$ Oct 12, 2018 at 15:53
3
$\begingroup$

Index the chosen cells from left to right, and let $c_i$ and $r_i$ be the column and row of cell $i$. Consider how many times your chosen cells switch from being in the bottom row to being in the top as you go from left to right, and call the number of switches $s$. The configuration is uniquely specified by:

  • A choice of whether the first cell is in the top or bottom row.
  • Which cells are in the opposite row from the previous one.
  • The "distance" between subsequent cells, where distance between cell $i$ and $i+1$ is $c_{i+1}-c_{i}$ if they are in opposite rows and $c_{i+1}-c_{i}-1$ if they are in the same row. This definition ensures that distance 1 corresponds to the closest the two cells can be in either case. We must also specify the column of the first cell $c_1$ so we have a starting point.

Example:

enter image description here

The switches happen between cells 1 & 2 and between cells 3 & 4. The distances between successive cells are 1 (between cells 1 & 2), 1 (between 2 & 3), and 3 (between cells 3 & 4).

For fixed $s$, we can enumerate the number of possibilities for each of the above bullet points:

  • There are two choices for the first row.
  • There are $\binom{k-1}{s}$ ways to choose where the switches occur.
  • We can evaluate the sum of the distances plus $c_{1}$ plus $n-c_{k}$: If we switched rows between every two chosen cells, it would just be $n$, but every time we don't switch we lose $1$ because the cells can't be adjacent. So the sum is $n-\left(\text{number of non-switches}\right) = n-(k-1-s)$. This sum is split into $k+1$ boxes, with at least 1 in each of the first $k$ boxes. Hence there are $\binom{n+1+s-k}{k}$ choices here.

So the total number of combinations for fixed $s$ is $2\binom{k-1}{s}\binom{n+1+s-k}{k}$, and the total number of arrangements is the sum of this over $s=0,\dots,k-1$, $$\sum_{s=0}^{k-1} 2\binom{k-1}{s}\binom{n+1+s-k}{k}$$

Happily, this agrees with your calculations for $n=3,k=2$ and $n=5,k=3$.

$\endgroup$

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