2
$\begingroup$

Let $m \geqslant 1$ be a fixed integer.

Let $f(n)$ be A007814, exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.

Then we have an integer sequence given by \begin{align} a_1(0)& = 1\\ a_1(2n+1)& = a_1(n)\\ a_1(2n)& = a_1(n-2^{f(n)})+a_1(2n-2^{f(n)}) \end{align} Here $a_1(n)$ is A243499, product of parts of integer partitions as enumerated in the table A125106.

Let $$a_m(n) = \sum\limits_{k=0}^{n}(\binom{n}{k}\operatorname{mod} 2)a_{m-1}(k)$$ Also $$s_m(n)=\sum\limits_{k=0}^{2^n-1}a_m(k)$$ I conjecture that $s_m(n)$ is Stirling transform of $$1, m, m^2, m^3, \cdots$$ In other words $$s_m(n)=\exp(-m)\sum\limits_{k=0}^{\infty}(k + 1)^n\frac{m^k}{k!}=\sum\limits_{k=0}^{n}{n+1\brace k+1}m^k$$ Is there a way to prove it?

$\endgroup$

1 Answer 1

2
$\begingroup$

The definition of $a_1$ given in OEIS is based on a bijection between integer partitions and natural numbers. A partition $\lambda_1\geq\lambda_2\geq\dots\geq\lambda_m>0$ with exactly $m$ parts corresponds to the number $$2^{\lambda_1+m-2}+2^{\lambda_2+m-1}+\dots+2^{\lambda_m-1}.$$ The definition of $a_1$ can then be written as \begin{equation}\label{a1d}(1)\qquad a_1\left(2^{\lambda_1+m-2}+2^{\lambda_2+m-1}+\dots+2^{\lambda_m-1}\right)=\lambda_1\dotsm\lambda_m.\end{equation}

When $n$ is a natural number, I will write $\|n\|$ for the number of ones in the binary expansion of $n$, and $n\preceq m$ if all binary digits in $n$ are smaller than or equal to those in $m$. It is well-known that $\binom nk\,\operatorname{mod}\,2=1$ if and only if $k\preceq n$. It is easy to see from this that $$a_m(n)=\sum_{k\preceq n}(m-1)^{\|n-k\|}a_1(k).$$ Roughly speaking, we go from $k$ to $n$ by changing zeroes to ones, and for each of the $\|n-k\|$ zeroes we can choose to change it in any one of $m-1$ binomial transforms.

The final ingredient is the identity $$\left\{\array{k+l\\l}\right\}=\sum_{l\geq \lambda_1\geq\lambda_2\geq\dots\geq\lambda_k> 0}\lambda_1\lambda_2\dotsm\lambda_k.$$ Probably this is well-known. I verified it using induction; just let me know if you need more explanation. By (1), this can be written \begin{equation}\label{sa}(2)\qquad\left\{\array{k+l\\l}\right\}=\sum_{0\leq j<2^{l+k-1},\,\|j\|=k}a_1(j).\end{equation}

We now have all ingredients we need. We have $$s_m(n)=\sum_{0\leq k<2^n}a_m(k)=\sum_{0\leq k<2^n}\sum_{l\preceq k}(m-1)^{\|k-l\|}a_1(l).$$ For fixed $l$ and $j=\|k-l\|$, we obtain $k$ by choosing $j$ from $n-\|l\|$ zeroes in $l$ and changing them to ones. Thus, we can write $$s_m(n)=\sum_{0\leq l<2^n}a_1(l)\sum_{j}\binom{n-\|l\|}{j}(m-1)^{j} =\sum_{0\leq l<2^n}a_1(l)m^{n-\|l\|}.$$ Writing this as a sum over $k=n-\|l\|$ and using (2) gives indeed $$s_m(n)=\sum_{k=0}^n m^k\left\{\array{n+1\\k+1}\right\}. $$

$\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.