number of possibilities to distribute k balls in 2n boxes with condition

Question

I'm trying to find the number of possibilities to distribute $k$ balls to $2n$ boxes such that for every $i$ between $1$ and $n$ the sum of the balls in the $i$ box and the $n+i$ box isn't equal to $6$. I tried writing the equation: $$x_1+x_2+...+x_{2n} = k$$, but I don't know how to progress further and it seems like it should be solves with recursion, can someone direct me?

Answer 1

By stars-and-bars there are $\binom{k+2n-1}{2n-1}$ ways to distribute the $k$ balls into $2n$ boxes where we don't care whether or not any box and its pair had six put in it.

The number of ways where boxes $1,n+1$ had $6$ balls collectively between them is $7\times \binom{k-6+2n-3}{2n-3}$ as there are $7$ ways to distribute the six balls into these two boxes, and then we have $k-6$ remaining balls and $2n-2$ remaining boxes to deal with. This is similarly the same result for had we been talking about any other pair of boxes.

The number of ways where boxes $1,n+1$ as well as boxes $2,n+2$ each collectively had $6$ balls between them would be $7^2\times \binom{k-2\times 6 + 2n-1-2\times 2}{2n-1-2\times 2}$ by similar logic and this generalizes to if we had $\ell$ pairs of boxes having six balls in each pair to be $7^\ell\times \binom{k-6\ell + 2n-1-2\ell}{2n-1-2\ell}$

Applying inclusion-exclusion and simplifying a bit, this gives:

$$\sum\limits_{\ell=0}^n(-7)^\ell\binom{n}{\ell}\binom{k+2n-1-8\ell}{2n-1-2\ell}$$

Answer 2

Using generating functions

The number of ways to fill in box $i$ and $n+i$ is given by:

$$ 1x^0 + 2x^1 + 3x^2 + 4x^3 + 5x^4 + 6x^5 + 0x^6 + 8x^7 + 9x^8 + \ldots = \frac{ 1}{(1-x)^2 } - 7x^6.$$

The number of ways to fill in all $2n$ boxes is given by:

$$(\frac{ 1}{(1-x)^2 } - 7x^6)^n.$$

We are interested in the coefficient of $x^k$.

Expanding out via the binomial theorea, we get

$$(\frac{ 1}{(1-x)^2 } - 7x^6)^n = \frac{1}{(1-x)^{2n}} - {n \choose 1}7x^6\frac{1}{(1-x)^{2n-2} } + { n\choose 2} (7x^{6})^2\frac{1}{(1-x)^{2n-2}} + \ldots + (-7x^6)^{2n}. $$

Then, finidng the coefficient of $x^k$ in each term gives us:

$$\sum\limits_{\ell=0}^n(-7)^\ell\binom{n}{\ell}\binom{k+2n-1-8\ell}{2n-1-2\ell}$$