Return to Question

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}{k}\operatorname{mod} 2)a(j,0)$$ and $$a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{k}\operatorname{mod} 2)a(j,-1)$$

Is there a way to prove it?

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?

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}

I also conjecture that

$$a(n, p) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(p-q)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(f(n,j),q)$$

Is there a way to prove it?

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}{k}\operatorname{mod} 2)a(j,0)$$ and $$a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{k}\operatorname{mod} 2)a(j,-1)$$

Is there a way to prove it?

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

$$a(n, p) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(p-q)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(f(n,j),q)$$

You can easily verify it using pari

v=[[0], [0, 1], [0, 2], [0, 1, 2, 3], [0, 4], [0, 1, 4, 5], [0, 2, 4, 6], [0, 1, 2, 3, 4, 5, 6, 7], [0, 8], [0, 1, 8, 9], [0, 2, 8, 10], [0, 1, 2, 3, 8, 9, 10, 11], [0, 4, 8, 12], [0, 1, 4, 5, 8, 9, 12, 13], [0, 2, 4, 6, 8, 10, 12, 14], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], [0, 16], [0, 1, 16, 17], [0, 2, 16, 18], [0, 1, 2, 3, 16, 17, 18, 19], [0, 4, 16, 20], [0, 1, 4, 5, 16, 17, 20, 21], [0, 2, 4, 6, 16, 18, 20, 22], [0, 1, 2, 3, 4, 5, 6, 7, 16, 17, 18, 19, 20, 21, 22, 23], [0, 8, 16, 24], [0, 1, 8, 9, 16, 17, 24, 25], [0, 2, 8, 10, 16, 18, 24, 26], [0, 1, 2, 3, 8, 9, 10, 11, 16, 17, 18, 19, 24, 25, 26, 27], [0, 4, 8, 12, 16, 20, 24, 28], [0, 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29], [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]]

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}

$$a(n, p) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(p-q)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(f(n,j),q)$$