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


  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.


1 Answer 1


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.


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=0$) a=1($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 n=31 rotated

This looks nice and suggestive, but is perhaps a little wide. We can use hexagonally packed circles to view this a little better: n=31 with circles

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. n=15 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. overlaps

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: doubled rows

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.


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


Here's a picture of $n=255$: blue-yellow 255


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.