Return to Answer

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 binary digits in $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\}. $$

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

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 binary digits in $n$, and $n\preceq m$ if all binary digits in $n$ are smaller than 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\}. $$

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 binary digits in $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\}. $$

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 binary digits in $n$, and $n\preceq m$ if all binary digits in $n$ are smaller than 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$ of the $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\}. $$

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 binary digits in $n$, and $n\preceq m$ if all binary digits in $n$ are smaller than 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\}. $$