Unlimited balls to $t$ cells with conditions

Question

Assuming an unlimited number of balls to be put into $t$ cells, such that each cell doesn't contain more than 2 balls - an empty cell will contain to balls, and a full cell will contain 2 balls. In how many ways can we put the balls in the cells such that the number of full cells will be even and the numer of empty cells will be odd ?

Attempt -

I thought about doing a double sigma, but i am not sure how to approach the problem and if my counting is even right -

$$\sum_{k=0}^t \sum_{n=0}^t \binom{t}{2k+1}\binom{t}{2n}$$

I know that this is not true, What do you think ?

Answer 1

A summation of trinomial coefficients:$$\sum_{k\in\mathbb Z}\sum_{n\in\mathbb Z}\binom{t}{2k+1,t-2k-2n-1,2n}\tag1$$

Here the term is taken to be $0$ if at least one of $2k+1$, $t-2k-2n$ and $2n$ takes a value that is not in $\{0,1,\dots,t\}$

You can also write $(1)$ as:$$\sum_{k\in\mathbb Z}\sum_{n\in\mathbb Z}\binom{t}{2k+1}\binom{t-2k-1}{2n}$$ where we use the convention that for nonnegative integer $n$ and integer $k$ we have $\binom{n}{k}=0$ if $k\notin\{0,\dots,n\}$

Answer 2

The first problem is that your first summation index should only go up to $\lfloor \frac{t}{2} \rfloor - 1$, not up to $t$. The second problem is that if you have chosen some cells to be empty, you can't choose them again to be full. So you get

$$ \sum_{k=0}^{\lfloor \frac{t}{2} \rfloor-1} \sum_{n=0}^{\lfloor \frac{t-2k-1}{2} \rfloor} {t \choose{2k+1}} {t-2k-1 \choose{2n}}.$$

Answer 3

The simplest form of the answer I could come up with is:

$$\tfrac{1}{4}(3^t-(-1)^t)\tag{Answer}$$

assuming the cells are distinct but the balls are not.

Which I arrive at through the exponential generating function

$$e^x\sinh(x)\cosh(x)\tag{1}$$

We see that

$$\sinh(x)=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots$$

has even powers of $x$ and so coefficients of $x^k/k!$ represent the possible number of ways of having even full cells.

Then

$$\cosh(x)=\frac{x^1}{1!}+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots$$

has odd powers of $x$ and so represents the number of ways of having odd empty cells.

Finally

$$e^x=1+\frac{x^1}{1!}+\frac{x^2}{2!}+\cdots$$

represents the possible numbers of ways of having any number of cells with a single ball.

The coefficient of $x^t/t!$ in $e^x\sinh(x)\cosh(x)$ therefore gives the required count.

Well, since $\sinh(x)=(e^x-e^{-x})/2$ and $\cosh(x)=(e^x+e^{-x})/2$ our exponential generating function $(1)$ becomes:

$$\begin{align}e^x\sinh(x)\cosh(x)&=\tfrac{1}{4}e^x(e^x-e^{-x})(e^x+e^{-x}) \\ &=\tfrac{1}{4}(e^{3x}-e^{-x})\end{align}$$

taking the $x^t/t!$ coefficient:

$$\begin{align}[x^t/t!]e^x\sinh(x)\cosh(x)&=[x^t/t!]\tfrac{1}{4}(e^{3x}-e^{-x})\\&=\tfrac{1}{4}(3^t-(-1)^t)\end{align}$$

which is our result at the top.