Counting special paths on a certain rectangle integer grid (binary matrix)

Question

Crossposted to MO.

Definitions, examples and observations

Matrix

Let $n$ be a positive integer.

Denote by $B_n$ the matrix of dimensions $ 2^n \times \left( n+1 \right) $ with entries from $ \{0,1\} $ such that it satisfies the recursive block relation $$B_n = \left[ \begin{array}{c|c} \underline{0}_{\left(2^{n-1} \times 1\right)} & B_{n-1}\\ \hline \underline{1}_{\left(2^{n-1} \times 1\right)} & B_{n-1} \end{array} \right] $$

with the condition

$$ B_1 \equiv \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ \end{bmatrix} $$

Matrix examples

For $ n \in \{2,3,4\} $ obtain $$ B_2 = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \\ \end{bmatrix}, \, B_3 = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ \end{bmatrix}, \, B_4 = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ \end{bmatrix} $$

Explicit formula for the matrix elements

It's not hard to show that $$ \left(B_n\right)_{i,j} = \lfloor {i-1 \over 2^{n-j}} \rfloor \pmod{2} $$

Path

A $B_n$-path $P$ is a set of size $2^n$ where each element is an ordered pair, where the first element is a row index of $B_n$, and the second element is a column index of $B_n$, so that each row index of $B_n$ appears exactly once in the elements of $P$.

Notice that $P$ has the form $$ \{ \left(i_1,j_1\right),\left(i_2,j_2\right), \ldots , \left(i_{2^n},j_{2^n}\right) \} $$ where the row indices from all the pairs are pairwise distinct.

In other words, a $B_n$-path is equivalent to choosing exactly one element from each and every row of $B_n$ in some order.

Obviously $\left(B_n \right)_{i_{1},j_{1}} = \left(B_n \right)_{i_{2},j_{2}}$ does not imply that $\left(i_1,j_1 \right) = \left(i_2,j_2 \right)$.

Weighted path

A $B_n$-weight $w$ is an $\left(n+1\right)$-tuple with non-negative integer entries, such that the sum of its entries is equal to $2^n$.

Fix a $B_n$-weight $w \equiv \left(\mu_1, \mu_2, \ldots , \mu_{n+1} \right) $, so $\mu_j \in \mathbb{Z}_{\ge 0}, \, j \in \{1,2, \ldots, n+1 \}$ and $\sum_{j=1}^{n+1}{\mu_j} = 2^n$.

A $B_n$-path with $B_n$-weight $w$, denoted by $P_w$, is a $B_n$-path such that $\mu_1$ of its pair elements have column indices which are equal to $1$, $\mu_2$ of the remaining pair elements have column indices which are equal to $2$, and so on, until finally the remaining $\mu_{n+1}$ pair elements have column indices which are equal to $n+1$.

Notice that if $\mu_k = 0$ for some $ k \in \{1,2,\ldots,n+1\} $ then $P_w$ does not have an element pair with $k$ as a column index.

Notice that the number of distinct $B_n$-paths with a fixed weight $w$ is given by the multinomial coefficient $$ \binom{\mu_1+\cdots+\mu_{n+1}}{\mu_1,\ldots,\mu_{n+1}}=\binom{2^n}{\mu_1,\ldots,\mu_{n+1}} $$

Weighted path examples

Consider the matrix $B_2$ and the $B_2$-weight $w \equiv \left(1,2,1 \right)$. A $B_2$-path with $B_n$-weight $w$, denoted by $P_w$, can be, for instance, the set $$ \{ \left( 1,1\right),\left( 2,2\right),\left( 3,2\right),\left( 4,3\right) \} $$ Graphically, this $B_2$-path looks like the following (in red): $$ \begin{bmatrix} \color{red}{0} & 0 & 0 \\ 0 & \color{red}{1} & 0 \\ 1 & \color{red}{0} & 0 \\ 1 & 1 & \color{red}{0} \\ \end{bmatrix} $$ Another possiblity for $P_w$ is the set $$ \{ \left( 1,2\right),\left( 2,3\right),\left( 3,2\right),\left( 4,1\right) \} $$ which looks like the following: $$ \begin{bmatrix} 0 & \color{red}{0} & 0 \\ 0 & 1 & \color{red}{0} \\ 1 & \color{red}{0} & 0 \\ \color{red}{1} & 1 & 0 \\ \end{bmatrix} $$ Consider the matrix $B_3$ and the $B_3$-weight $w \equiv \left(2,0,5,1 \right)$. A $B_3$-path with $B_n$-weight $w$, denoted by $P_w$ can be, for instance, the set $$ \{ \left( 1,1\right),\left( 2,1\right),\left( 3,3\right),\left( 4,3\right),\left( 5,3\right),\left( 6,3\right),\left( 7,3\right),\left( 8,4\right) \} $$ Graphically, this $B_3$-path looks like the following (in red): $$ \begin{bmatrix} \color{red}{0} & 0 & 0 & 0 \\ \color{red}{0} & 0 & 1 & 0 \\ 0 & 1 & \color{red}{0} & 0 \\ 0 & 1 & \color{red}{1} & 0 \\ 1 & 0 & \color{red}{0} & 0 \\ 1 & 0 & \color{red}{1} & 0 \\ 1 & 1 & \color{red}{0} & 0 \\ 1 & 1 & 1 & \color{red}{0} \\ \end{bmatrix} $$ Another possiblity for $p_w$ is the set $$ \left( \left( 1,4\right),\left( 2,3\right),\left( 3,1\right),\left( 4,3\right),\left( 5,3\right),\left( 6,3\right),\left( 7,3\right),\left( 8,1\right) \right) $$ which looks like the following: $$ \begin{bmatrix} 0 & 0 & 0 & \color{red}{0} \\ 0 & 0 & \color{red}{1} & 0 \\ \color{red}{0} & 1 & 0 & 0 \\ 0 & 1 & \color{red}{1} & 0 \\ 1 & 0 & \color{red}{0} & 0 \\ 1 & 0 & \color{red}{1} & 0 \\ 1 & 1 & \color{red}{0} & 0 \\ \color{red}{1} & 1 & 1 & 0 \\ \end{bmatrix} $$

Parity of a path

The parity of a $B_n$-path $P$ is the sum modulo $2$ of the elements of $B_n$ with row-column indices which correspond to the elements of $P$.

Summation modulo 2 is commutative, so the parity of a $B_n$-path $P$ is given by $$ \sum_{i=1}^{2^n}{\left( B_n\right)_{i,j_i}} \pmod 2 $$ where $j_i$ is the column index in the element pair of $P$ with row index $i$.

Notice that when calculatiing this sum we may ignore the elements of $P$ with column index $j_i=n+1$, because the corresponding elements of $B_n$ are all equal to $0$.

Parity of a path examples

Consider the following $B_2$-path and $B_3$-path and just take the sum of the red colored $0$'s and $1$'s modulo 2.

The $B_2$-path described graphically by $$ \begin{bmatrix} 0 & \color{red}{0} & 0 \\ 0 & 1 & \color{red}{0} \\ \color{red}{1} & 0 & 0 \\ 1 & 1 & \color{red}{0} \\ \end{bmatrix} $$ has parity equal to $1$.

The $B_3$-path described graphically by $$ \begin{bmatrix} 0 & \color{red}{0} & 0 & 0 \\ 0 & \color{red}{0} & 1 & 0 \\ 0 & 1 & \color{red}{0} & 0 \\ 0 & 1 & \color{red}{1} & 0 \\ 1 & 0 & \color{red}{0} & 0 \\ 1 & 0 & \color{red}{1} & 0 \\ 1 & 1 & \color{red}{0} & 0 \\ 1 & 1 & 1 & \color{red}{0} \\ \end{bmatrix} $$ has parity equal to $0$.

Problems

Consider the matrix $B_n$.

Fix a $B_n$-weight $w \equiv \left(\mu_1, \mu_2, \ldots,\mu_{n+1} \right)$, so $\mu_j \in \mathbb{Z}_{\ge 0}, \, j \in \{1,2, \ldots, n+1\}$ and $\sum_{j=1}^{n+1}{\mu_j} = 2^n$.

1. Show that the number of all distinct $B_n$-paths with weight $w$ and parity equal to $0$ is equal to the number of all distinct $B_n$-paths with weight $w$ and parity equal to $1$, if and only if at least one of the entries of the weight $w$ is an odd integer.

Now consider a weight with only even entries.

Fix a weight $\varpi \equiv \left(2\phi_1, 2\phi_2, \ldots , 2\phi_{n+1} \right) $, so $\phi_j \in \mathbb{Z}_{\ge 0}, \, j \in \{1,2, \ldots, n+1 \}$ and $\sum_{j=1}^{n+1}{\phi_j} = 2^{n-1}$.

2. Count the number all distinct $B_n$-paths with weight $\varpi$ and parity equal to $0$. Count the same for when the parity is equal to $1$.
3. Show that the difference between the number of all distinct $B_n$-paths with weight $\varpi$ and parity equal to $0$, and the number of all distinct $B_n$-paths with weight $\varpi$ and parity equal to $1$, is invariant under any permutation of the entries of $\varpi$.

What I am asking for

I am looking for references to this kind of problems. I'd appreciate to know about equivalent problems which require less setup, perhaps stated as a problem in graph theory. I am also hoping for some input or hints for these problems. Problem 2 seems to be the most difficult.

Answer 1

$\let\eps\varepsilon$The difference of the numbers of even and odd paths of weight $w=(\mu_1\dots,\mu_{n+1})$ is the coefficient of $$ x^\mu:=\prod_{j=1}^{n+1}x_j^{\mu_j} $$ in the polynomial $$ P(x_1,x_2,\dots,x_{n+1})=\prod_{\eps_1,\dots,\eps_n\in\{-1.1\}} \left(x_{n+1}+\sum_{j=1}^n\eps_jx_j\right); $$ recall the standard notation $[x^\mu]P$ for that cofficient. Indeed, each path corresponds to a choice of a variable from each bracket in order to get such a monomial, and the sign of the resulting monomoal represents the parity of the path.

To answer Q1, assume that $\mu_i$ is odd for some $i\leq n$, and pair up the brackets differing by $\eps_i$ only; you will get the product of differences of squares, which depend on $x_i^2$ only. Hence the coeficient of $x^\mu$ is zero.

To answer Q3, note that the polynomial $P$ is invariant under an arbitrary permutation of $x_1,\dots,x_n$. To see the whole symmetry, multiply all brackets with $\eps_1=-1$ by $-1$; this will turn the polynomial into $P(x_{n+1},x_2,\dots,x_n,x_1)$.

Perhaps, the answer to Q2 is also known after this reformulation?

Answer 2

This is just a follow-up to Ilya's answer.

Here is my SageMath code that provides functions polyP(n) that computes polynomial $P(x_1,x_2,\dots,x_{n+1})$ and function testQ1(n) for verifying the "only if" direction of question Q1 for a given $n$. As an example, by default the code computes the polynomial for $n=3$, which contains 35 nonzero terms.

In fact, to verify Q1 it's enough to compute $P$ at $x_{n+1}=1$, which is a symmetric polynomial in $x_1,\dots,x_n$. I've verified Q1 for $n\leq 5$.

It's also worth to notice that $P$ evaluated at $x_{n+1}=0$ is also a symmetric polynomial, which satisfies $$P(x_1,x_2,\dots,x_n,0) = P(x_1,x_2,\dots,x_{n-1},x_n)^2,$$ and which is similar to the total Boolean product polynomial with deep combinatorial properties.