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

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

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

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

• I guess the notion of path can be simplified to a vector of length $2^n$ with entries from $\{1, 2,\dots,n+1\}$ such that the difference between each two consecutive entries is at most $1$. – Alex Ravsky Sep 11 '20 at 6:27
• @AlexRavsky Consider the matrix $B_2$ and the weight $w \equiv \left( 2,0,2\right)$. Now consider the weighted path $p_w \equiv \left(\left(1,1\right),\left( 2,1\right),\left( 3,3\right),\left( 4,3\right)\right)$. I think your suggestion fails to capture the aforementioned path. Am I misunderstanding? – Hellbound Sep 11 '20 at 11:34
• Yes, it fails. But is $p_w$ a path? All paths in your examples are continuous. – Alex Ravsky Sep 12 '20 at 2:01
• The verbose setup obscures the content quite a bit. The rows of your recursively defined matrices just count up in binary, with an extra $0$ appended to the end of each row. Your "$B_n$-paths" are really just ways to choose a subset $S$ of the $2^n$ length $n$ binary strings and then choose a single bit from each element of $S$. Your "parity" is the sum of the chosen bits (mod $2$), and your "weight" is the list of the number of times each bit has been chosen (which implicitly encodes $n$ and $|S|$). – Joshua P. Swanson Sep 15 '20 at 7:29
• Please, avoid making several edits. – Aloizio Macedo Sep 16 '20 at 13:23

## 2 Answers

$$\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?

• You proved Q1 only in one direction. – Max Alekseyev Sep 15 '20 at 12:10
• I appreciate the simple arguments! Unfortunately, your reformulation gets me to square one:) @MaxAlekseyev is correct. – Hellbound Sep 16 '20 at 3:43
• The polynomial $P(x_1, \ldots, x_{n+1})$ is the defining polynomial of the hyperplane arrangement whose normal vectors are all $\pm 1$ vectors, which Gutekunst--M\'esz\'aros--Petersen call the threshold arrangement $\mathcal{T}_{n+1}$. It's not clear if this is useful, but it does connect things to existing work. Unfortunately nobody seems to have examined the threshold arrangements much aside from trying to compute the number of chambers, which appears hard. – Joshua P. Swanson Sep 16 '20 at 7:11
• My couple of cents: (i) the proof holds if we fix $x_{n+1}=1$; (ii) the polynomial $P$ is similar the total Boolean product polynomial although I do not right away how to transform one into the other. – Max Alekseyev Sep 16 '20 at 13:40
• @JoshuaP.Swanson: No surprise, they say that Boolean product polynomial is also the defining polynomial of a certain hyperplane arrangement. – Max Alekseyev Sep 16 '20 at 13:42

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.