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


Let $\operatorname{wt}(n)$ is [A000120](https://oeis.org/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](https://oeis.org/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](https://oeis.org/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](http://oeis.org/A295989), irregular triangle $T(n, k)$, read by rows, $n \geqslant 0$ and $0 \leqslant k <$ [A001316](http://oeis.org/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?



Sum with products turned into subsequences
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.)


