拉格朗日反演公式(lagrange inversion)组合证明
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)}
\]