3
$\begingroup$

Let $p, q \in \mathbb{Z}$.

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

$$n=2^{t_1}(1+2^{t_2+1}(1+\dots(1+2^{t_{wt(n)}+1}))\dots)$$

Then we have an integer sequence given by \begin{align} a(0, m)& = 1\\ a(n, m)& = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}m^{\operatorname{wt}(n)-\operatorname{wt}(j)}\prod\limits_{k=0}^{\operatorname{wt}(n)-1}(1+\operatorname{wt}(\left\lfloor\frac{j}{2^k}\right\rfloor))^{t_{k+1}+1} \end{align} I conjecture that $$a(n, -1) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(f(n,j),0)$$ and $$a(n, 0) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}a(f(n,j),-1)$$ where $a(n,-1)$ is A329369, number of permutations of ${1,2,...,m}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)...b(1)b(0)$ ($0 \leqslant k < m-1$) is the binary expansion of $n$. The excedance set of a permutation $p$ of ${1,2,...,m}$ is the set of indices $i$ such that $p(i) > i$; it is a subset of ${1,2,...,m-1}$.

and $a(n,0)$ is A284005, \begin{align} a(0, 0)& = 1\\ a(n,0)& = (1+\operatorname{wt}(n))a(\left\lfloor\frac{n}{2}\right\rfloor,0) \end{align}

and finally $f(n,k)$ is 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}

In other words

$$a(n, -1) = \sum\limits_{j=0}^{n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}(\binom{n}{j}\operatorname{mod} 2)a(j,0)$$ and $$a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)$$

Is there a way to prove it?

$\endgroup$

1 Answer 1

3
$\begingroup$

Actually, these two conjectures are actually equivalent.

We need a lemma: Lucas' Theorem: $\binom{a}{b}$ is odd if and only if $a\&b=b$ where $\&$ is bitwise AND operation. Let $S_j$ be the set of integers $i$ such that $i\&j=i$. Thus, if the first relation

$$a(n, -1) = \sum\limits_{j=0}^{n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}(\binom{n}{j}\operatorname{mod} 2)a(j,0)$$ holds, we have $$a(n, -1) = \sum\limits_{j\in S_n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(j,0)$$ And therefore, $$\sum_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)=\sum_{j\in S_n}\sum_{k\in S_j}(-1)^{\text{wt}(j)-\text{wt}(k)}a(k,-1)$$ Swapping the sums, we have the right hand side equals to $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ All the other $k\in S_n$ vanishs the sum $\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$ because for every bit that is $1$ in $n$ and $0$ in $k$, it contribute a factor $1$ if that bit in $j$ is $0$ and $-1$ if that bit in $j$ is $1$. Therefore, the sum $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ is actually $a(n,-1)$, which implies the conjecture $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)$. Similarly, we can derive the first conjecture using the second.

So, we only need to proof $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)$.

Notice that the sum $\sum_{j\in S_n}a(j,-1)$, if we take the combinatorial argument as granted, it counts the following permutations: for all the $k${th} bit of $n$ that is $0$, $\sigma(k)\le k$. This is because all the other bits when summed, cancelled out the restrictions. (If the $k$th bit of $n$ is $1$, that all the $S_k$ with $k$th bit $1$ with have $\sigma(k)> k$, and all the $S_k$ with $k$th bit $0$ with have $\sigma(k)\le k$. So These two cancelled out if we sum the elements in $S_n$.) So we claim the number of such permutations is $a(n,0)$.

Actually, we can count the permutations as follows: for the $0$ bits of $n$ (call it $i_1,i_2,\dots,i_k$), we select the permutation one by one. We select $\sigma(i_l)$ to be one of $1,2,\dots,i_l$ except $\sigma(i_1),\dots,\sigma(i_{l-1})$. So this is $i_l-(\text{number of zeroes before $i_l$})$, that is, the number of ones before $i_l$. The rest of them we choose it freely, so it is $(\text{number of ones})!$. That is, we can assign $t$ to the $t$th one in the binary representation of $n$, or, the number of $1$ not after that bit, and take the product. Let $n=b_rb_{r-1}\dots b_0$ be its binary representation. So, the overall number of permutation is $\prod_{u=1}^r (\text{the number of ones not later than digit }b_u)$, and thus equals $a(n,0)$ (because the combinatorial meaning of $a(n,0)$ is such.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.