拉格朗日反演公式(lagrange inversion)组合证明

发布时间 2023-05-07 22:14:45作者: pigpigger

There is a simple combinatorial proof.
The original form is

\[[t^n]w^k=\frac{k}{n}[t^{n-k}]\phi^k \]

where \(w=t\phi(w)\)

consider \(w\) as egf. of the ways of some trees.

\(\phi\) as a generating rule concerning degree.

\[n![x^n]\frac{w^k}{k!}=(n-k)![x^{n-k}]\phi^{n} \times\binom{n}{k} \times k \times\frac{1}{n} \]

prufer sequence give a bijection between k-component forest and a sequence of $[k] \times [n]^{n-k-1} $

the LHS means a forest of \(k\) trees.
the RHS means the forest of \(k\) trees has a prufer sequence of length \(n-k\) . from \([n]\) choose a vertex to

there are\(\binom{n}{k}\) ways to choose \(k\) vertexes as roots. but \([x^{n-k}]\phi^n\) only count the sequences with arbitrary first term of which \(\frac{k}{n}\) of them is actually true.

now let us deduce another useful formula used in combinatorial sums.

\[\mathcal{G}([t^n]F(t)\phi(t)^n)=\frac{F(w)}{1-t\phi'(w)}|w=t\phi(w) \]

which means

\[\sum_n([x^n]F(x)\phi(x)^n)t^n=\frac{F(w)}{1-t\phi'(w)}|w=t\phi(w) \]

\[LHS=\sum_kt^k\sum_jf_j[x^{k-j}]\phi(x)^k \]

\[=\sum_{k,j}t^k ~ f_j ~ \frac{k}{j} ~ [x^k]w(x)^j\]

\[=\sum_jf_j~\frac{1}{j}~ (w(t)^j)'t \]

\(w=t\phi(w)\) derive both side

\[w'=\frac{\phi(w)}{1-t\phi'(w)}=\frac{w}{(1-t\phi'(w))t} \]

continue

\[=\sum_jf_j~ w'w^{j-1}t=\sum_jf_j~ w^{j}\frac{1}{1-t\phi'(w)} \]

\[=\frac{F(w)}{1-t\phi'(w)} \]