My question is related to the following:
We have an identity
$$a(n, -1) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(f(n,j),0)$$
or
$$a(n, -1) = \sum\limits_{j=0}^{n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}(\binom{n}{j}\operatorname{mod} 2)a(j,0)$$
Here $\operatorname{wt}(n)$ is the number of $1$'s in the binary expansion of $n,$ or its binary weight.
Here is the combinatorial interpretation:
Let $a(n,0)$ (A284005) be the number of open tours by a biased rook of the first kind which make its tours on a specific $f(n)\times 1$ board (which ends on any cell) where $f(n) = \left\lfloor\log_2{2n}\right\rfloor + 1$ and cells are colored white or black according to the binary representation of $2n$. A cell is colored white if the binary digit is $0$ and a cell is colored black if the binary digit is $1$. A biased rook on a white cell moves only to the left and otherwise moves in any direction.
Let $a(n,-1)$ (A329369) be the number of open tours by a biased rook of the second kind which make its tours on a specific $f(n)\times 1$ board (which ends on a white cell) where $f(n) = \left\lfloor\log_2{2n}\right\rfloor + 1$ and cells are colored white or black according to the binary representation of $2n$. A cell is colored white if the binary digit is $0$ and a cell is colored black if the binary digit is $1$. A biased rook on a white cell moves only to the left and otherwise moves only to the right.
Here is a table:
In this table we have solutions (in lexicographic order) for $a(6,-1)$ (because $1100$ in binary is $12$ and by the condition we work with $2n$), described as permutations which reading as follows: $3421$ means that we start with $4$-th cell, then go to $3$-rd, then to $1$-st, and finally to $2$-nd. In other words, inverse permutation $4312$ gives the sequence of visiting the cells.
We also have solutions for $a(0,0)$, $a(2,0)$, $a(4,0)$ and $a(6,0)$. Why are we taking those numbers? We start from $6$ and then replace each $k$ ones with $k$ zeros, exactly:
- $110$ -> $110$ (no change; here 0 ones replaced by 0 zeros)
- $110$ -> $010$ (here 1 one replaced by 1 zero)
- $110$ -> $100$ (another variant)
- $110$ -> $000$ (here 2 ones replaced by 2 zeros)
In other words, we take values from the row $n$ (here $n=6$) of A295989, irregular triangle $T(n, k)$, read by rows, $n \geqslant 0$ and $0 \leqslant k <$ A001316$(n)$: $T(n, k)$ is the $(k+1)$-th nonnegative number $m$ such that $n \operatorname{AND} m = m$ (where $\operatorname{AND}$ denotes the bitwise $\operatorname{AND}$ operator).
\begin{align} T(n, 0)& = 0\\ T(2n, k)& = 2T(n,k)\\ T(2n+1, 2k)& = 2T(n,k)\\ T(2n+1, 2k+1)& = 2T(n,k) + 1 \end{align}
I conjecture that if we delete duplicates in the solutions for $a(0,0)$, $a(2,0)$, $a(4,0)$ and $a(6,0)$ we get solutions for $a(6,-1)$ (which is also must work for any $n$).
Is there a way to prove it?
