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


Crossposting from MSE after getting no answers. The bounty on the MSE question is still open, but not for long. Be advised that the comments of the MSE question regard an obsolete version, and that the issues which had arose from those comments were answered in subsequent edits.

This question arose in the context of studying reflections.

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 1right)} & B_{n-1}\
hline
underline{1}_{left(2^{n-1} times 1right)} & 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_nright)_{i,j} =
begin{cases}
lfloor {i-1 over 2^{n-j}} rfloor pmod{2}, & text{if $1 le j le n$}
\
0, & text{if $j=n+1$}
end{cases}
$$

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_1right),left(i_2,j_2right), 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+1right)$-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,1right),left( 2,2right),left( 3,2right),left( 4,3right)
}
$$

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,2right),left( 2,3right),left( 3,2right),left( 4,1right)
}
$$

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,1right),left( 2,1right),left( 3,3right),left( 4,3right),left( 5,3right),left( 6,3right),left( 7,3right),left( 8,4right)
}
$$

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,4right),left( 2,3right),left( 3,1right),left( 4,3right),left( 5,3right),left( 6,3right),left( 7,3right),left( 8,1right)
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_nright)_{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$.

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(2phi_1, 2phi_2, ldots , 2phi_{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}$.

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

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.