Is there something called the pochhammer expansion?

Question

I'm just playing around with the Pochhammer notation where $$n^{\underline{k}} \equiv n(n-1)\ldots(n-k+1).$$ I've established the formulas $$\begin{split} n &= n^{\underline{1}}\\ n^2 &= n^{\underline{2}} + n^{\underline{1}}\\ n^3 &= n^{\underline{3}} + 3n^{\underline{2}} + n^{\underline{1}}\\ n^4 &= n^{\underline{4}} + 6n^{\underline{3}} + 7n^{\underline{2}} + n^{\underline{1}}\\ n^5 &= n^{\underline{5}} + 10n^{\underline{4}} + 25n^{\underline{3}} + 15n^{\underline{2}} + n^{\underline{1}}. \end{split} $$ Does it exist a general formula of the form $$ n^k = \sum_{i=k}^1 c(i,k)n^{\underline{i}}, $$ for such expansions? What are in that case the closed form of the coefficients $c(i,k)$? Does this expansion have a name?

Answer 1

The general expression for $n\ge 0$ is

$$x^n=\sum_{k=0}^n{n\brace k}x^{\underline k}\,,$$

where $n\brace k$ is the Stirling number of the second kind that counts the partitions of $[n]$ into $k$ non-empty subsets. This is easily proved by induction on $n$ once you have the identity

$$x\cdot x^{\underline k}=x^{\underline{k+1}}+kx^{\underline k}$$

and the recurrence

$${n\brace k}=k{{n-1}\brace k}+{{n-1}\brace{k-1}}\,.$$

The induction step is:

$$\begin{align*} x^n&=x\sum_k{{n-1}\brace k}x^{\underline k}\\ &=\sum_k{{n-1}\brace k}x^{\underline{k+1}}+\sum_k{{n-1}\brace k}kx^{\underline k}\\ &=\sum_k{{n-1}\brace{k-1}}x^{\underline k}+\sum_k{{n-1}\brace k}kx^{\underline k}\\ &=\sum_k\left(k{{n-1}\brace k}+{{n-1}\brace{k-1}}\right)x^{\underline k}\\ &=\sum_k{n\brace k}x^{\underline k} \end{align*}$$

Answer 2

We have that

$$n^k = \sum_{q=0}^k {k\brace q} n^\underline{q}.$$

This is because we have for the RHS

$$\sum_{q=0}^k {k\brace q} q! {n\choose q} = k! [z^k] \sum_{q=0}^k (\exp(z)-1)^q {n\choose q}.$$

Now $\exp(z)-1= z+\cdots$ so that $(\exp(z)-1)^q = z^q+\cdots$ and the coefficient extractor enforces the upper limit of the sum and we find

$$k! [z^k] \sum_{q\ge 0} (\exp(z)-1)^q {n\choose q} = k! [z^k] \exp(nz) = n^k.$$

We can also prove this combinatorially. The left side counts all $k$-tuples with component values ranging from $1$ to $n.$ The right is a classification by the number $q$ of different values that appear. We choose these in ${n\choose q}$ ways, then we partition the slots of the tuple into $q$ non-empty sets in ${k\brace q}$ ways. To conclude note that we can assign the $q$ chosen values to the sets of slots in $q!$ ways. This is essentially the comment by @QuiaochuYuan.