2
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ If $2k+1$ cells are empty then $t-2k-1$ can be used to carry $2$ balls. Not $t$ as you seem to think. So you get terms like $\binom{t}{2k+1}\binom{t-2k-1}{2n}$ $\endgroup$ – drhab Feb 9 '18 at 13:26
2
$\begingroup$

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\}$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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