# $f(x)=\sum_{t}{x \choose t}{n-x \choose k-t}$ - even or odd?

The following function popped in my research: $$f(x)=\sum_{\array{0\le t\le k \\ t\equiv_p a}}{x \choose t}{n-x \choose k-t}$$

Where:

1. $n,k$ are natural numbers and $k\le n$.
2. $t$ is taken over all integers between $0$ and $k$ such that $t$ is equivalent to $a$ modulo a prime $p$.
3. $x$ is a natural number between $0$ and $n$.

So the function is determined by the parameters $n,k,p,a$. I'm particularly interested in the case $p=3$ and $a=0$ (but also $a=1$ is relevant).

My main question is - is there a way to characterize (instead of simply computing) for which values of $x$ (given $n,k,p,a$) the values of $f(x)$ will be odd numbers?

The first step seems to be answering the question of when ${\alpha \choose \beta}$ is odd and when it is even. This question was asked here and received a beautiful solution; however, I fail to see a way in which to apply that solution to "my" function.

This certainly is far from a complete answer, but I hope it's helpful. I'll try to describe my thought process so it doesn't seem like this came out of nowhere.

## Experimentation

I fixed $$p=3$$ and initially tried to examine $$a=0$$ and $$a=1$$ by taking advantage of the corollary of Lucas' Theorem at the question you linked. Using black for "odd" and white for even, I got tables like the following for small $$n$$. $$n=0$$ is the top left table, $$n=3$$ is the top right one, $$n=31$$ is the bottom right one. Within a table, each row is a value of $$k$$ (starting from $$0$$) and each column is a value of $$x$$: ($$a=0$$) ($$a=1$$)

We have nice patterns when $$n$$ is one less than a power of $$2$$, especially in the top left portion of the tables (when $$x+k\le n$$) and for $$a=0$$ where it looks especially like the Sierpinski triangle or the Walsh matrix. In fact, upon inspection, your expression is a little weird for $$x+k>n$$ since then $$n-x$$ dips below $$k$$, but $$k-t$$ goes up to $$k$$. From now on I'll focus only on $$a=0$$ for $$x+k\le n$$.

For example, rotating the picture for $$n=31$$ gives us This looks nice and suggestive, but is perhaps a little wide. We can use hexagonally packed circles to view this a little better: Now, in order to see a pattern, we can try to relate this to the $$n=15$$ case, which is precisely the top quarter of the whole image. I thought to focus on the seven isolated 1s (brown dots) that appeared in $$n=31$$ "in" the large gap of $$n=15$$. Using different colors and some layer work in Gimp. This picture is a bit hard to analyze, but basically, when you align things just right, the isolated 1s that appear out of nowhere are at the centers of $$\lozenge$$s with 0s at the vertices of $$n=15$$. In fact, the centers of all $$\lozenge$$s (not just vertical ones) appear to follow a simple rule: it's a $$1$$ if there are zero or two $$\lozenge$$-vertices that are $$1$$, and and it's a $$0$$ otherwise. The small points that lie under a large point (so that they're not the centers of a $$\lozenge$$) share the same value.

Unfortunately, this $$\lozenge$$-in-every-direction idea is a bit hard to work with, and leaves a problem for recursion at the bottom of the triangle. If we align things a bit more naturally, we get this: That made it clear that every second row of $$n=31$$ is a row of $$n=16$$ but with every entry doubled: (1,0,1) became (1,1,0,0,1,1), etc.

## Recurrence

Putting these ideas together with a bit of trial and error led me to a recurrence with the power of 2 in $$n$$ as a parameter. But since $$n=15$$ is the top of $$n=31$$, etc. $$n$$ is actually not needed when it's restricted to be one less than a power of $$2$$. If the row of the triangle $$r$$ starts at $$1$$, and the column $$c$$ goes from $$1$$ to $$r$$ inclusive, then the parity $$b_{r,c}$$ is given by the following (I confirmed the pattern up to $$n=2^8-1$$, but this is ultimately conjecture):

To make the recurrence work, set $$b_{r,c}=0$$ for $$r<1$$ or $$c<1$$ or $$c>r$$. Then let $$R=\lceil r/2\rceil$$ and $$C=\lceil c/2\rceil$$ We have $$b_{1,c}=1$$ if $$c=1$$ and $$0$$ otherwise. Then, for $$r>1$$, $$b_{r,c}=b_{R,C}$$ when $$r$$ is even and when $$r$$ and $$c$$ are both odd. In the remaining case of $$r>1$$ where $$r$$ is odd and $$c$$ is even, we have $$b_{r,c}=f\left(b_{R-1,C},b_{R,C},b_{R,C+1},b_{R+1,C+1}\right)$$ where $$f$$ is a function that outputs $$1$$ when two or four of its arguments are $$0$$ and outputs $$0$$ otherwise. (Unfortunately, some experimentation suggests that any natural recurrence depending on at most three previous terms does not work.)

To connect this back to the original problem, $$c=x+1$$ (so $$x=c-1$$) and $$r=x+k+1$$ (so $$k=r-c$$). I admit I don't know how to begin solve this recurrence, and OEIS doesn't seem to shed any light on this (although it introduced me to the similar-looking Walsh matrix). I also have not proven that this works for all $$n$$ that are one less than a power of $$2$$.

## Bonus

Here's a picture of $$n=255$$: 