1
$\begingroup$

Related questions:

Let $a_{1}(n)$ (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_{2}(n)$ (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.

First I want to prove that \begin{align} a_{1}(0)& = 1\\ a_{1}(n)& = (1+\operatorname{wt}(n))a_{1}(\left\lfloor\frac{n}{2}\right\rfloor) \end{align}

Here $\operatorname{wt}(n)$ is A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).

Suppose we have a sequence of black cells

$$\underbrace{1\cdots1}_{k}$$

According to the conditions, biased rook on a black cell moves in any direction. Then it is obvious that we have $k$ ways to choose the $1$st cell, $k-1$ ways to choose the $2$nd cell, etc. As a result, we have $k!$ open tours by a biased rook of the first kind.

Next we have the following sequence of cells

$$\underbrace{1\cdots1}_{k_2}0\underbrace{1\cdots1}_{k_1}$$

Imagine that there is no white cell as in the previous case, then we start with $(k_1+k_2)!$. Then we ask ourselves the question: how many ways can we insert a white cell into the sequence of visiting black cells? Obviously, we can insert it in front of the leftmost black cells and also at the end. As a result, we have $(k_1+k_2)!(k_2+1)$ open tours by a biased rook of the first kind.

Next we have

$$\underbrace{1\cdots1}_{k_2}00\underbrace{1\cdots1}_{k_1}$$

Here it is obvious that we cannot put the $1$st cell on the right after of the $1$st cell on the left, since by the condition biased rook on a white cell moves only to the left. As a result, we have $(k_1+k_2)!(k_2+1)^2$ open tours by a biased rook of the first kind.

Next we have

$$\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}\underbrace{0\cdots0}_{j_1}$$

As a result, we have $(k_1+k_2)!(k_2+1)^{j_2}(k_1+k_2+1)^{j_1}$ open tours by a biased rook of the first kind.

Next we have

$$\underbrace{1\cdots1}_{k_m}\underbrace{0\cdots0}_{j_m}\cdots\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}\underbrace{0\cdots0}_{j_1}$$

As a result, we have

$$a_1(n)=(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_q}$$

Then if we add a white cell on the right, we have

$$a_1(2n)=(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_{p}+[p=1]}=(1+\sum\limits_{q=1}^{m}k_q)(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p}$$ Here $$\sum\limits_{q=1}^{m}k_q=\operatorname{wt}(n)$$ so $$a_1(2n)=(1+\operatorname{wt}(n))a(n)=(1+\operatorname{wt}(2n))a(n)$$ Don't forget that for $a(n)$ we are working with a binary representation of $2n$, then for $a(2n+1)$ we have 2 options: $$\underbrace{1\cdots1}_{k_m}\underbrace{0\cdots0}_{j_m}\cdots\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}1\underbrace{0}_{j_1}$$ $$\underbrace{1\cdots1}_{k_m}\underbrace{0\cdots0}_{j_m}\cdots\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}\underbrace{0\cdots0}_{j_{1}-1}\underbrace{1}_{k_{0}}\underbrace{0}_{j_{0}}$$ Then we have

$$a_1(2n+1)=(\sum\limits_{i=1}^{m}k_i+[i=1])!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q+[q=1])^{j_{p}}=(2+\sum\limits_{q=1}^{m}k_q)(1+\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=2}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p}=(2+\sum\limits_{q=1}^{m}k_q)(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p}=(2+\operatorname{wt}(n))a(n)=(1+\operatorname{wt}(2n+1))a(n)$$ and $$a_1(2n+1)=(1+\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=0}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_{p}-[p=1]}=(1+\sum\limits_{q=0}^{m}k_q)(1+\sum\limits_{i=1}^{m}k_i)(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p-[p=1]}=(2+\sum\limits_{q=1}^{m}k_q)(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p}=(2+\operatorname{wt}(n))a(n)=(1+\operatorname{wt}(2n+1))a(n)$$ QED

Second I want to prove that $$a_1(n) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a_2(j)$$ Since $a_2(n)$ is 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) then for example for $1100$ we can replace $k$ ones by $k$ zeros (we have 4 options):

  • $1100$ -> $1100$ (no change; here 0 ones replaced by 0 zeros)
  • $1100$ -> $0100$ (here 1 one replaced by 1 zero)
  • $1100$ -> $1000$ (another variant)
  • $1100$ -> $0000$ (here 2 ones replaced by 2 zeros)

Through this we add all possible ways to finish on any cell, which is what $a_1(n)$ counts. It remains only to add that operation above is the same as taking values of the $n$-th row of A295989, which is also the same as taking $j$ such that $$\binom{n}{j}\operatorname{mod} 2=1$$ QED

Are my proofs rigorous? What are they missing? Сan they be improved?

Improve this question
$\endgroup$

0

Reset to default

You must log in to answer this question.