4
$\begingroup$

I am investigating the polynomial $$P_n(x)=\left(x\frac{d}{dx}\right)^n f(x)=xP_{n-1}'(x)$$ for some known function $f$. I defined $f_n(x)=\frac{d}{dx}f_{n-1}(x)$ with $P_0=f_0=f$. And I also defined $$P_n(x)=\sum_{k=1}^{n}C_n(k)x^kf_k(x)$$ And I am interested in finding an explicit form, or at least a recurrence relation for $C_n(k)$. With manual calculation, I was able to find up through $n=6$, but I failed to recognize any pattern, so I thought I'd ask for help. For those interested, a 'table' of values:

$n=1$: $$C_1(1)=1$$ $n=2$: $$C_2(1)=1,\quad C_2(2)=1$$ $n=3$: $$C_3(1)=1,\quad C_3(2)=3,\quad C_3(3)=1$$ $n=4$: $$C_4(1)=1,\quad C_4(2)=7,\quad C_4(3)=6,\quad C_4(4)=1$$ $n=5$: $$C_5(1)=1,\quad C_5(2)=15,\quad C_5(3)=25,\quad C_5(4)=10,\quad C_5(5)=1$$ $n=6$: $$C_6(1)=1,\quad C_6(2)=31,\quad C_6(3)=90,\quad C_6(4)=65,\quad C_6(5)=15,\quad C_6(6)=1$$ The only pattern I can see is $C_n(1)=C_n(n)=1$. Also, it is easily shown that, since $P_n=xP_{n-1}'$, $$\sum_{k=1}^{n}C_n(k)x^kf_k(x)=\sum_{k=1}^{n-1}C_{n-1}(k)x^k\left[f_k(x)+xf_{k+1}(x)\right]$$ Although I'm not sure that helps. I am very lost, please help. Thanks!

$\endgroup$
  • 5
    $\begingroup$ Look up Stirling numbers of the second kind: oeis.org/A008277 This $C_n(k)$ counts the number of ways to partition a set of $n$ distinct things into $k$ nonempty piles. $\endgroup$ – bonsoon Feb 8 at 0:36
  • 3
    $\begingroup$ @bonsoon That looks like an answer. Please make it into one? $\endgroup$ – Pedro Tamaroff Feb 8 at 0:44
3
$\begingroup$

For integers $n,k$ with $n\ge 0$, let ${n\brace k}$ denote the Stirling numbers of the second kind, which count the number of partitions of a set of size $n$ into $k$ nonempty, non-distinct parts. These satisfy the following recurrence, which can be taken as their definition: $$ {n\brace k}={n-1 \brace k-1}+k{n-1\brace k},\\ {0\brace 0}=1,{0\brace k}=0\text{ for }k\neq 0 $$

Now, let $D$ be the differential operator, and let $X$ be the operator which takes in a function $f$ and returns $xf$. As a special case of the product rule, we have the operator identity $$ DX=XD+1 $$ where $1$ is the identity, $1f=f$. Indeed, applying both sides to some function $f$, you get $D(xf)=x(Df)+f$. More generally, $$ DX^k=X^kD+kX^{k-1} $$ You can now prove by induction that $$ (XD)^n=\sum_k {n \brace k}X^kD^k $$ where the sum ranges over all integral $k$ (but is effectively finite since ${n \brace k}$ is zero for $k$ outside $[0,n]$) as follows:

\begin{align} (XD)^n &=(XD)(XD)^{n-1} \\&=(XD)\sum_k {n-1 \brace k}X^k D^k \\&=\sum_k {n-1\brace k}XDX^kD^k \\&=\sum_k {n-1\brace k}X(X^kD+kX^{k-1})D^k \\&=\sum_k {n-1 \brace k}(X^{k+1}D^{k+1}+kX^kD^k) \\&=\sum_k \Big(k{n-1\brace k}+{n-1\brace k-1}\Big)X^kD^k \\&=\sum_k {n\brace k}X^kD^k \end{align}

$\endgroup$
  • $\begingroup$ So, in other words, $C_n(k)={n\brace k}$? $\endgroup$ – clathratus Feb 8 at 1:13
  • $\begingroup$ @clathratus That's right. To relate this back to your question, take the operators on both sides of $(XD)^n=\sum_{k=0}^n {n \brace k}X^kD^k$, and apply them to $f$. Since $D^kf=f_k$, you get that $P_n(x)=\sum_{k=1}^{n}{n \brace k}x^kf_k(x)$, so that the $C_n(k)$ you want are precisely ${n \brace k}$. $\endgroup$ – Mike Earnest Feb 8 at 1:17
6
$\begingroup$

Here is a supplementary to user @bonsoon's comment as to why the Stirling numbers of the second kind pop up. This begins with the identity

$$ x^n = \sum_{k=0}^{n} \left\{ {n \atop k} \right\} (x)_k, $$

where

  • $\left\{{n \atop k}\right\}$ is the Stirling number of the second kind, which counts the number of ways of partitioning the set $\{1,\cdots,n\}$ into $k$ parts, and

  • $(x)_k = x(x-1)\cdots(x-k+1)$ is the falling factorial.

(See the Wikipedia article, for instance.) Now if we introduce two operators $D = \frac{d}{dx}$ and $L = x\frac{d}{dx}$, then they satisfy $ L^n(x^a) = a^n x^a $ and $ D^n(x^a) = (a)_n x^{a-n} $, and so,

$$ L^n(x^a) = a^n x^a = \sum_{k=0}^{n} \left\{ {n \atop k} \right\} (a)_k x^a = \sum_{k=0}^{n} \left\{ {n \atop k} \right\} x^k D^k (x^a). $$

Since both $L$ and $D$ are linear, the same identity holds for any polynomial $f(x)$ in place of $x^a$, yielding

$$ L^n f = \sum_{k=0}^{n} \left\{ {n \atop k} \right\} x^k D^k f. $$

Of course, this extends to any $C^n$-function $f$ by polynomial approximation.

$\endgroup$
  • 1
    $\begingroup$ This is really, really cool. Thank you $\endgroup$ – clathratus Feb 8 at 0:55
  • $\begingroup$ @clathratus, Glad it helped. This answer still leaves the question as to why the identity at the beginning holds, but the proof should be available from any reasonably well-versed textbook in combinatorics or from googling :) $\endgroup$ – Sangchul Lee Feb 8 at 0:58
  • 1
    $\begingroup$ Thanks for filling the details :) $\endgroup$ – bonsoon Feb 8 at 0:59
  • $\begingroup$ I'm sorry to do this, but I am un-accepting your answer for the time being, until someone shows me a proof for my identity. $\endgroup$ – clathratus Feb 8 at 1:10
  • $\begingroup$ @clathratus, User Mike Earnest gave a nice, self-contained answer for the identity $$\left(x\frac{d}{dx}\right)^n = \sum_{k=0}^{n} \left\{ {n \atop k} \right\} x^k \left(\frac{d}{dx}\right)^k$$ which also appears at the end of my answer. Now comparing what we get from this with your equality, it is evident that $C_n(k) = \left\{{n \atop k}\right\}$, so $C_n(k)$ is exactly the Stirling numbers of the second kind. $\endgroup$ – Sangchul Lee Feb 8 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.