Arithmetic problem for bicolored graphs

Question

A bicolored graph is a graph each vertex of which has been assigned one of two colors such that each edge connects vertices of different colors. A bipartite graph is a graph $G$ which admits such a coloring. Given $j$ white and $i$ black vertices, there are $2^{ji}$ ways to join vertices of different colors. Thus the number of (labeled) bicolored graphs on n vertices is $$b_n=\sum_{i+j=n}\binom{n}i2^{ij}.$$

Question. Is it true that $b_n$ is never divisible by $5$? If so, any proof?

Update. One combinatorial proof and two number-theoretic/algebraic proofs are supplied.

Answer 1

This follows from the fact that for any prime $p$, and any integer $n\ge0$, we have $b_{n+p}\equiv b_{n+1} \pmod p$. This can be proved by a straightforward, though not very interesting, computation, using Fermat's theorem $2^p\equiv 2 \pmod p$ and the fact that $\binom {n+p}{i} \equiv \binom ni + \binom n{i-p} \pmod p$.

More interesting is a combinatorial proof. (For similar proofs and further references, see my paper Combinatorial proofs of congruences, in Enumeration and Design, ed. David M. Jackson and Scott A. Vanstone, Academic Press, Toronto, 1984, pp. 157–197, especially section 5.)

We consider the cyclic group $C_p$ acting naturally on $[p]=\{1,2,\dots, p\}$. This extends to an action on bicolored graphs with vertex set $[n+p]=\{1,2,\dots, n+p\}$; the group permutes vertices $1, 2, \dots, p$, and does not change the other vertices. Since every orbit has size 1 or $p$, $b_{n+p}$ is congruent modulo $p$ to the number of bicolored graphs on $[n+p]$ fixed by this action of $C_p$. It is not hard to see that these fixed bicolored graphs are those in which all vertices in $[p]$ have the same color, no edges join two vertices in $[p]$, and all vertices in $[p]$ have the same neighborhood. By "contracting" all the vertices in $[p]$ to a single vertex, whose neighborhood is the same as the neighborhood of any of the vertices in $[p]$, we get a bicolored graph on $n+1$ vertices. Thus the number of fixed bicolored graphs is $b_{n+1}$, so $b_{n+p}\equiv b_{n+1}\pmod p$.

Answer 2

For even $i$ we have $2^{ij}=2^{ni-i^2}\equiv 2^{ni}\pmod 5$ and $2^{ij}\equiv 2^{ni-1} \pmod 5$ for odd $i$. In other words, $2^{ij}\equiv \frac34 2^{ni}+\frac14 (-2^n)^i$. Thus $$\sum_i \binom{n}i 2^{i(n-i)}\equiv \frac34(1+2^n)^n+\frac14(1-2^n)^n\pmod 5,$$ this depends only on $n$ modulo 4 and we may easily consider all 4 cases.

Answer 3

Here is an illustration of Ira Gessel's comment about a number-theoretic proof.

Lemma. For $n\geq1$ and an odd prime $p$, the sequence $b_n$ mod $p$ is periodic of period $p-1$.

Proof. Let $n=m(p-1)+r$, where $1\leq r\leq p-1$ and $m\geq0$. Proceed with a successive application of Fermat's, Lucas' and Chu-Vandermonde's theorems so that \begin{align*} b_n&=\sum_{j=1}^{p-1}\sum_{k=0}^m\binom{m(p-1)+r}{k(p-1)+j}2^{[k(p-1)+j][m(p-1)+r-k(p-1)-j]} \\ &\equiv_p\sum_{j=1}^{p-1}\sum_{k=0}^m\binom{m(p-1)+r}{k(p-1)+j}2^{j(r-j)} \\ &\equiv_p\sum_{j=1}^{p-1}2^{j(r-j)}\sum_{k\geq0}\binom{m}k\binom{r-m}{j-k}\\ &\equiv_p\sum_{j=1}^{p-1}2^{j(r-j)}\binom{r}j\\ &=\sum_{j=1}^r\binom{r}j2^{j(r-j)}=b_r. \end{align*} The proof is complete. $\square$

Example. The first 4 values of $b_n$ mod 5 are $[2,2,1,1]$, as Wojowu mentioned. By the Lemma, we conclude that $\nu_5(b_n)=0$, that is, $b_n$ is never divisible by $5$.