Return to Question

Parity of a weighted path

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

The parity of a $B_n$-path with weight $w$ can be computed by doing the following:

Consider the the binary representation of the integers in the range $\left[0,2^{n}-1\right]$. Choose $\mu_1$ of them and do a logic shift right by $n-1$ on each, then choose $\mu_2$ of the remaining and do a logic shift right by $n-2$ on each,..., then finally do a logic shift right by $n-n=0$ on each of the last remaining $\mu_n$. Now look at the LSB of all the shifted integers, then count how many $1$'s there are. The parity of the count is the parity of the corresponding $B_n$-path with weight $w$, where we identify each integer $i$ in the range with the $\left(i+1\right)$-th row of $B_n$.

Consider the the binary representation of the integers in the range $\left[0,2^{n}-1\right]$. Choose $\mu_1$ of them and do a logic shift right by $1$ on each, then choose $\mu_2$ of the remaining and do a logic shift right by $2$ on each,..., then finally do a logic shift right by $n$ on each of the last remaining $\mu_n$. Now look at the LSB of all the shifted integers, then count how many $1$'s there are. The parity of the count is the parity of the corresponding $B_n$-path with weight $w$, where we identify each integer $i$ in the range with the $i+1$-th row of $B_n$.

Consider the the binary representation of the integers in the range $\left[0,2^{n}-1\right]$. Choose $\mu_1$ of them and do a logic shift right by $n-1$ on each, then choose $\mu_2$ of the remaining and do a logic shift right by $n-2$ on each,..., then finally do a logic shift right by $n-n=0$ on each of the last remaining $\mu_n$. Now look at the LSB of all the shifted integers, then count how many $1$'s there are. The parity of the count is the parity of the corresponding $B_n$-path with weight $w$, where we identify each integer $i$ in the range with the $\left(i+1\right)$-th row of $B_n$.

Parity of a weighted path

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

The parity of a $B_n$-path with weight $w$ can be computed by doing the following:

Consider the the binary representation of the integers in the range $\left[0,2^{n}-1\right]$. Choose $\mu_1$ of them and do a logic shift right by $1$ on each, then choose $\mu_2$ of the remaining and do a logic shift right by $2$ on each,..., then finally do a logic shift right by $n$ on each of the last remaining $\mu_n$. Now look at the LSB of all the shifted integers, then count how many $1$'s there are. The parity of the count is the parity of the corresponding $B_n$-path with weight $w$, where we identify each integer $i$ in the range with the $i+1$-th row of $B_n$.