A probability problem by Akshat Sharda

For any $0 < x < \tfrac{1}{32}$ define the function $f_x(t) = t(1+x)^4 - x(1+t)^4$ . Since $f_x'(t) = (1+x)^4 - 4x(1+t)^3$ is it clear that $f_x$ has a unique maximum at some real point $\xi$ , and that $f_x$ is increasing on $(-\infty,\xi)$ , and decreasing on $(\xi,\infty)$ . Since $0 < 4x(1+t)^3 < 32x < 1 < (1+x)^4 \hspace{2cm} 0 < t < 1$ we deduce that $f_x'(t) > 0$ for $0 < t < 1$ , so that $\xi \ge 1$ . Thus $f_x$ has exactly two real roots. One of these is $x$ , and the other is some value $y > 1$ . The other two roots $u,v$ are complex, with $v = u^\star$ . Since $-4 \; = \; x + y + u + v \; > \; 1 + 2\mathrm{Re}\,u$ we deduce that $\mathrm{Re}\,u < -\tfrac52$ , and hence $|u|, |v| > 1$ . Thus $x$ is the only zero of $f_x(t)$ of modulus less than $1$ , and $\frac{1}{f_x(z)}$ has a simple pole at the point $x$ , so that $\frac{1}{2\pi i}\int_{|z|=1} \frac{dz}{f_x(z)} \; = \; \mathrm{Res}_{z=x} \frac{1}{f_x(z)} \; = \; \frac{1}{f_x'(x)} \; = \; \frac{1}{(1+x)^3(1-3x)}$

---

Now suppose that $A_n \; = \; \sum_{r=0}^n (-1)^r \binom{n}{r} \binom{4n-3r}{n} \; = \; \sum_{r=0}^n (-1)^{n-r} \binom{n}{r} \binom{n+3r}{n}$ for any nonnegative integer $n$ , and define $\begin{aligned} F(x) & = \; \sum_{n=0}^\infty A_n x^n \; = \; \sum_{n=0}^\infty \sum_{r=0}^n (-1)^{n-r} \binom{n}{r}\binom{n+3r}{n} x^n \; = \; \sum_{r=0}^\infty \sum_{n=r}^\infty (-1)^{n-r} \binom{n}{r}\binom{n+3r}{n} x^n \\ & = \; \sum_{r=0}^\infty \sum_{n=0}^\infty (-1)^n \binom{n+r}{r} \binom{n+4r}{n+r} x^{n+r} \; = \; \sum_{r=0}^\infty \frac{x^r}{r! (3r)!} \sum_{n=0}^\infty \frac{(-1)^n (n+4r)!}{n!} x^n \\ & = \; \sum_{r=0}^\infty \binom{4r}{r} x^r \sum_{n=0}^\infty (-1)^n \binom{n+4r}{n}x^n \; = \; \sum_{r=0}^\infty \binom{4r}{r} \frac{x^r}{(1+x)^{4r+1}} \end{aligned}$ for all $|x| < \tfrac13$ . But then, at least for $0 < x < \tfrac{1}{32}$ , $\begin{aligned} F(x) & = \; \frac{1}{2\pi i}\sum_{r=0}^\infty \frac{x^r}{(1+x)^{4r+1}} \int_{|z|=1}\frac{(1+z)^{4r}}{z^{r+1}}\,dz \; = \; \frac{1}{2\pi i}\int_{|z|=1} \sum_{r=0}^\infty \frac{x^r(1+z)^{4r}}{z^{r+1}(1+x)^{4r+1}}\,dz \\ & = \; \frac{1}{2\pi i}\int_{|z|=1}\frac{(1+x)^3\,dz}{z(1+x)^4 - x(1+z)^4} \; = \; \frac{(1+x)^3}{2\pi i}\int_{|z|=1}\frac{1}{f_x(z)}\,dz \; = \; \frac{1}{1-3x} \end{aligned}$ Note that the condition $0 < x < \tfrac{1}{32}$ is strong enough to ensure that the series $\sum_{r=0}^\infty \frac{x^r(1+z)^{4r}}{z^{r+1}(1+x)^{4r+1}}$ is uniformly convergent for $|z| = 1$ , so that we can safely interchange the integration and the summation.

This is enough to tell us that $A_n = 3^n$ for all integers $n \ge 0$ , and hence that $\log_3 A_{81} = \boxed{81}$ .

Here's a purely combinatorial solution, as an alternative approach to @Mark Hennings ' analytic combinatorial solution (using generating functions and complex analysis).

---

Consider an $n \times 4$ table, whose cells are identified by $(r,c)$ with $1 \le r \le n$ and $1 \le c \le 4$ . We want to color some of these cells black (and the rest white), and mark some others with X, under the following conditions:

• There are exactly $n$ black cells.
• No black cell is marked X.
• No cell in the 4th column ( $c = 4$ ) is marked X.
• If a cell $(r,c)$ is marked X, then all of $(r,1), (r,2), (r,3)$ are marked X.

Basically, X indicates a blanked row, where no black cell may go, except to the fourth column.

Now define $A_k$ to be the set of all colorings such that there are exactly $k$ rows containing some cell marked X. (If $k > n$ , then we simply have $A_k = \emptyset$ .) Observe that $|A_k| = \binom{n}{k} \binom{4n-3k}{n}$ as follows: there are $\binom{n}{k}$ ways to choose the rows marked X, and among the remaining $4n-3k$ non-X cells, we want to shade $n$ of them black. Then $f(n) = \sum_k (-1)^k |A_k|$ .

Then define $S = A_0 \cup A_2 \cup A_4 \cup \ldots$ be the set of colorings with even $k$ , and $T = A_1 \cup A_3 \cup A_5 \cup \ldots$ be the set of colorings with odd $k$ . Then we can simplify further to $f(n) = |S| - |T|$ , since all of $S$ have $(-1)^k = 1$ and all of $T$ have $(-1)^k = -1$ .

Now, we use a method called "sign-reversing involution", or D.I.E. . Here, we want to make a partial injection between $S$ and $T$ : each element of $S$ will (hopefully) be paired with some element of $T$ , and no two elements are paired to the same element. The idea is, since each member in $S$ counts positively to the sum and each member in $T$ counts negatively to the sum, any paired elements cancel each other and we're just left with the unpaired elements, which (hopefully) are easier to count.

The following is the pairing. Given a coloring $C$ , its pair $C^+$ is defined like this: first, find the smallest $r'$ , if any, such that none of $(r',1), (r',2), (r',3)$ are black. (That might be because they are marked X, or they are simply missed by the coloring.) Now, toggle the states of these three cells: if they were marked X in $C$ , then in $C^+$ they are simply blank, neither black nor marked X; and if they were blank in $C$ , then they become marked X in $C^+$ .

It's easy to see that the above pairing is an involution: if $C^+$ is defined, then $(C^+)^+$ is also defined, and moreover $(C^+)^+ = C$ . This means we do have an injection: no two elements map to the same element. Also, $C, C^+$ have opposite signs; if $C \in S$ , then $C^+ \in T$ , and vice versa. Thus we have a sign-reversing involution.

The only cases where $C^+$ is not defined, and hence the elements remain unpaired, are when there doesn't exist such $r'$ . In order to do this, this means we need at least one black cell among $(r,1), (r,2), (r,3)$ , for all $r$ . Since there are $n$ rows and $n$ black cells, it follows that we need exactly one black cell among $(r,1), (r,2), (r,3)$ , for all $r$ . There are $3^n$ ways to do this (for each row, pick which column, other than the last, has its cell black; all choices are independent from each other). All of them are in $S$ , since there are no rows marked X. Thus $f(n) = |S| - |T| = 3^n$ ; only these $3^n$ colorings count to the sum, since the rest are canceled.

Finally, $\log_3 f(81) = \log_3 3^{81} = \boxed{81}$ .

Finding $f(n)$ is same is finding the coefficient of $x^{n}$ in $\displaystyle \sum^{n}_{r=0} (-1)^r \binom{n}{r} (1+x)^{4n-3r}$ .

So, doing as stated above,

$x^{n}: \displaystyle \sum^{n}_{r=0} (-1)^r \binom{n}{r} (1+x)^{4n-3r} \\ x^n: (1+x)^n \displaystyle \sum^{n}_{r=0} (-1)^r \binom{n}{r} (1+x)^{3n-3r} \\ x^n : (1+x)^n \displaystyle \sum^{n}_{r=0} \binom{n}{r} \left[(1+x)^3\right]^{n-r} (-1)^r \\ x^n : (1+x)^n \left[ (1+x)^3-1\right]^n \\ x^n: (1+x)^nx^n(x^2+3x+3)^n$

Therefore, $f(n)=3^n$ .

$f(n)$ is same as the coefficient of $x^{3n}$ in $\frac{(1-x^{3})^n}{(1-x)^{n+1}}$

which is coefficient of $x^{3n}$ in $\frac{(1+x+x^2)^n}{1-x} = (1+x+x^2)^n(1+x+x^2+... )$

We see that for each term (after collecting same powers of $x$ together) of $(1+x+x^2)^{n}$ we have a term in $1+x+x^+..$ to make the power of $x$ as 3n.

So our answer is the sum of all coefficient of $(1+x+x^2)^n$ which is obtained by putting x=1.

$f(n)=3^n$

$f(81)=3^{81}$

and our answer is thus $\boxed{81}$