重庆师范大学数学与科学学院，重庆

收稿日期：2022年11月27日；录用日期：2022年12月23日；发布日期：2022年12月30日

摘要

Faà di Bruno’ formular的相关研究一直处于停滞状态，之后，由于Faà di Bruno在其它方面的应用，Lukacs开始将Faà di Bruno用于数学统计学；罗曼用umbral calculus的定理对Faà di Bruno方程进行了再论证，Constantine利用Faà di Bruno扩展了关于集合划分的恒等式，并给出了它的概率说明，Chu利用Faà di Bruno获得了一系列的行列式，Chou，Hsu和Shiue利用Faà di Bruno构造了一种具有互逆性的函数，由此推导了一组恒等方程，然而并没有有关用Fáa di Bruno’s公式求组合恒等式以及进行对称群及集合分割上的组合数的研究存在。本文使用Fáa di Bruno’s公式求组合恒等式以及进行对称群及集合分割上的组合数的研究，通过Faà di Bruno得到了各种著名组合数的恒等式，含括Catalan数，第一类及第二类Stirling数，q-二项式系数···等，及Faà di Bruno在计数上的应用；在第二节中，我们利用Faà di Bruno得到了多种组合数的恒等式；在第三节中，我们由第一类及第二类Stirling数、错排数、Bell数的指数生成函数用Faà di Bruno导出的恒等式获得这些数的组合意义，得到一些限制置换中圈结构和限制集合分割的子集大小的结果。

关键词

恒等式，Fáa di Bruno’s公式，高阶微分

Application of Faà di Bruno’s Formula in Identity and Counting

Ping Shen

School of Mathematics and Science, Chongqing Normal University, Chongqing

Received: Nov. 27^th, 2022; accepted: Dec. 23^rd, 2022; published: Dec. 30^th, 2022

ABSTRACT

The research on Faà di Bruno has been in a stagnant state. Later, because of the application of Faà di Bruno in other aspects, Lukacs began to use Faà di Bruno in mathematical statistics; Roman demonstrated the Faà di Bruno equation again by using the theorem of umbral calculus. Constantine extended the identity of set partition by using Faà di Bruno and gave its probability explanation. Chu obtained a series of determinants by using Faà di Bruno, Chou; Hsu and Shiue used Faà di Bruno to construct a kind of reciprocal function, and derived a set of identity equations from it. However, there is no research on finding combinatorial identities by using Fáa di Bruno’s formula and on the number of combinations on symmetric groups and set partitions. Faà di Bruno's formula was used to find the combinatorial identity, and the combinatorial numbers on symmetric groups and set partitions were studied. In this paper, the identities of various famous combinatorial numbers, including Catalan numbers, the first and second Stirling numbers, q binomial coefficients, etc., and the application of Faà di Bruno in counting were obtained through Faà di Bruno; In the second section, we use Faà di Bruno to obtain the identities of multiple combinatorial numbers; in the third section, we obtain the combined meanings of Stirling numbers, staggered numbers and Bell numbers from the exponential generating functions of the first and second types of Stirling numbers with the identities derived from Faà di Bruno, and the subset size of set partitions can be obtained.

Keywords:Identical Equation, Faà di Bruno’s Formula, Higher Order Differential

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等；另一类就是研究离散对象的组合数学。微积分以及现代数学的发展，为现代工业的发展打下了坚实的基石 [1]。而组合数学的发展，为本世纪电脑的变革打下了坚实的基石。从十七世纪到十八世纪，组合数学和随机运算的发展，到了十九世纪，它已经彻底地颠覆了传统的概念，产生了一种全新的、充满活力的新的数学派别 [2]。因此，组合数学的发展，使传统的数理学科成为了以解析与代数为主导的学科。尤其是随着计算机越来越多地渗透到各行各业，除了数字运算之外，也出现了许多快速发展的非数字运算方法，这些方法大多采用了合成方法 [3]。

在计算机科学、编码与密码学、物理等领域，都有着举足轻重的作用。化学、生物等学科都具有很大的实用价值，即计算科学 [4]。计算机的运算方法只是一个离散的物体，而不是一个数字，它的科学就在于它的结合，它给人一种感觉，就像它有思想一样，因此，它的计算方法就成为了计算机的中心 [5]。在商业经营、运输计划、作战指挥、财务分析等方面，美国有一间公司以组合数学为名；他们运用了综合数学的理论，以增加公司经营的收益，这个公司做的很好，另外，实验设计也是一个很实用的课题，其主要的数学理论是结合的。美国已经有一些专业公司，在此基础上，对其进行了研究 [6] [7]。近年来，一名德国知名的复合数学家运用复合数论对药品结进行了深入的探讨，为医药企业节约了成本。简而言之，组合数学的基础理论与实践，涉及计算机科学，生物学，化学；心理学，金融和基因工程学的最新的运用，其范围十分广阔。

本文首先研究使用Faà di Bruno公式求组合恒等式，然后进行对称群及集合分割上的组合数的研究，最后对论文进行总结，发觉Faà di Bruno公式的应用前景。由于本文研究偏理论研究，因此将不使用仿真例子进行研究，后续可在此基础上进行相关深入的研究。

2. 用Faà di Bruno求组合恒等式

对任意给定幂级数 $\varphi \left(t\right)={\displaystyle {\sum }_{n=0}^{\infty }{a}_n{t}^n}$，以 $\left[\begin{array}{c}\varphi \\ n\end{array}\right]$ 表示 $t^n$ 的系数，即 $\varphi \left(t\right)={\displaystyle \underset{n\ge 0}{\sum }\left[\begin{array}{c}\varphi \\ n\end{array}\right]t^n}$。

假设f有反函数，考虑复合函数 $\left(f\circ \varphi \right)\left(t\right)$ 和 $\left(f^{-1}\circ \left(f\circ \varphi \right)\right)\left(t\right)$，Chou，Hsu与Shiue将Faà di Bruno改写，得到下列两个式：

$\left[\begin{array}{c}f\circ \varphi \\ n\end{array}\right]={\displaystyle \underset{\sigma \left(n\right)}{\sum }{\left(D^{k}f\right)}_{x=\varphi \left(0\right)}\frac{{\left[\begin{array}{c}\varphi \\ 1\end{array}\right]}^{k_1}{\left[\begin{array}{c}\varphi \\ 2\end{array}\right]}^{k_2}\cdots {\left[\begin{array}{c}\varphi \\ n\end{array}\right]}^{k_n}}{k_1!k_2!\cdots k_n!}}$ (1)

$\left[\begin{array}{c}\varphi \\ n\end{array}\right]={\displaystyle \underset{\sigma \left(n\right)}{\sum }{\left(D^k{f}^{-1}\right)}_{x=f\circ \varphi \left(0\right)}\frac{{\left[\begin{array}{c}f\circ \varphi \\ 1\end{array}\right]}^{k_1}{\left[\begin{array}{c}f\circ \varphi \\ 2\end{array}\right]}^{k_2}\cdots {\left[\begin{array}{c}f\circ \varphi \\ n\end{array}\right]}^{k_n}}{k_1!k_2!\cdots k_n!}}$ (2)

因为 $\left[\begin{array}{c}f\circ \varphi \\ n\end{array}\right]$ 和 $\left[\begin{array}{c}\varphi \\ n\end{array}\right]$ 在(1)和(2)中所处的地位恰好相反，称这两条恒等式为一组互逆关系式。特别地，考虑 $f\left(x\right)={\text{e}}^x$，$\varphi \left(t\right)={\displaystyle {\sum }_{n=0}^{\infty }{a}_n{t}^n}$，令 $b_n=\left[\begin{array}{c}f\circ \varphi \\ n\end{array}\right]$，若 $\varphi \left(0\right)=0$，则由(1)和(2)有以下互逆关系：

$b_n={\displaystyle \underset{\sigma \left(n\right)}{\sum }\frac{a_1^{k_1}{a}_2^{k_2}\cdots a_n^{k_n}}{k_1!k_2!\cdots k_n!}}$ (3)

$a_n={\displaystyle \underset{\sigma \left(n\right)}{\sum }{\left(-1\right)}^{k-1}\left(k-1\right)!\frac{b_1^{k_1}{b}_2^{k_2}\cdots b_n^{k_n}}{k_1!k_2!\cdots k_n!}}$ (4)

定理1 对任意正整数n，有互逆关系

$C_n=\frac{1}{n+1}\left(\begin{array}{c}2n\\ n\end{array}\right)=\frac{1}{n+1}{\displaystyle \underset{\sigma \left(n\right)}{\sum }\frac{2^{2n-k}}{1^{k_1}{k}_1!2^{k_2}{k}_2!\cdots n^{k_n}{k}_n!}}$

及 $4^n=2n{\displaystyle \underset{\sigma \left(n\right)}{\sum }{\left(-1\right)}^{k-1}\left(k-1\right)!{\displaystyle \underset{i=1}{\overset{n}{\prod }}\frac{{\left(\begin{array}{c}2i\\ i\end{array}\right)}^{k_i}}{k_i!}}}$。

定理2. 对任意正整数n，r，有互逆关系

$1^n+2^n+\cdots +r^n=n{\displaystyle \underset{\sigma \left(n\right)}{\sum }{\left(-1\right)}^{k-1}\left(k-1\right)!{\displaystyle \underset{i=1}{\overset{n}{\prod }}\frac{S{\left(r+i,r\right)}^{k_i}}{k_i!}}}$

及 $S\left(n+r,r\right)={\displaystyle \underset{\sigma \left(n\right)}{\sum }{\displaystyle \underset{i=1}{\overset{n}{\prod }}\frac{S{\left(1^i+2^i+\cdots +r^i\right)}^{k_i}}{i^{k_i}{k}_i!}}}$ 或 $S\left(n,r\right)={\displaystyle \underset{\sigma \left(n-r\right)}{\sum }{\displaystyle \underset{i=1}{\overset{n-r}{\prod }}\frac{{\left(1^i+2^i+\cdots +r^i\right)}^{k_i}}{i^{k_i}{k}_i!}}}$。

证明：令 $f\left(x\right)={\text{e}}^x$，$\varphi \left(t\right)=\ln \frac{1}{\left(1-t\right)\left(1-2t\right)\cdots \left(1-rt\right)}$，显然 $\varphi \left(0\right)=0$，

$\left(f\circ \varphi \left(t\right)\right)=\frac{1}{\left(1-t\right)\left(1-2t\right)\cdots \left(1-rt\right)}={\displaystyle \underset{i\ge r}{\sum }S\left(i,r\right)t^{i-r}}$

故而 $b_i=\left[\begin{array}{c}f\circ \varphi \\ i\end{array}\right]=S\left(r+i,r\right)$。

另一方面因为

$\varphi \left(t\right)=\ln \frac{1}{\left(1-t\right)\left(1-2t\right)\cdots \left(1-rt\right)}={\displaystyle \underset{i=1}{\overset{r}{\sum }}\left(-\ln \left(1-it\right)\right)}={\displaystyle \underset{i=1}{\overset{r}{\sum }}{\displaystyle \underset{j\ge 1}{\sum }\frac{i^j}{j}{t}^j}}={\displaystyle \underset{j\ge 1}{\sum }{\displaystyle \underset{i=1}{\overset{r}{\sum }}\frac{i^j}{j}{t}^j}}$

观察 $t^n$ 的系数可得

$a_i=\left[\begin{array}{c}\varphi \\ n\end{array}\right]={\displaystyle \underset{i=1}{\overset{r}{\sum }}\frac{i^n}{n}}=\frac{1^n+2^n+\cdots +r^n}{n}$

根据Faà di Bruno (4)可以得到

$\frac{1^n+2^n+\cdots +r^n}{n}={\displaystyle \underset{\sigma \left(n\right)}{\sum }{\left(-1\right)}^{k-1}\left(k-1\right)!}\frac{S{\left(r+1,r\right)}^{k_1}S{\left(r+2,r\right)}^{k_2}\cdots S{\left(r+n,r\right)}^{k_n}}{k_1!k_2!\cdots k_n!}$

等号两边同乘n即得第一条恒等式；由Faà di Bruno的(3)可得第二条恒等式

$S\left(n,r\right)={\displaystyle \underset{\sigma \left(n-r\right)}{\sum }{\displaystyle \underset{i=1}{\overset{n-r}{\prod }}\frac{{\left(1^i+2^i+\cdots +r^i\right)}^{k_i}}{i^{k_i}{k}_i!}}}$

注1. 除了上述定理外，连续整数的幂次和与 $S\left(n,k\right)$ 还有以下关系

$1^n+2^n+\cdots +r^n={\displaystyle \underset{k=1}{\overset{n}{\sum }}k!S\left(n,k\right)\left(\begin{array}{c}r+1\\ k+1\end{array}\right)}$

定理3. 对任意整数n，r，有互逆关系。

由Faà di Bruno的(4)可得第二个恒等式。

3. 对称群及集合分割上的组合数

这一节，将由已知的第一类及第二类Stirling数、Bell数、错排数的指数生成函数出发，利用Faà di Bruno推导出这些数的组合意义，从而可用Faà di Bruno求出错排数及Bell数加上更多限制的生成函数。首先，先考虑第一类Stirling数 $S\left(n,k\right)$ 及错排数D_n。

对称群S_n中的每一个置换皆可唯一分解成互斥圈的乘积。若一个置换分解成互斥圈后，长度为i的圈有k_i个 $\left(i=1,2,\cdots ,n\right)$，则称这个置换是属于 $1^{k_1}{2}^{k_2}\cdots n^{k_n}$ 型的置换。

下面是已知的事实：

给定非负整数 $k_1,k_2,\cdots ,k_n$，则S_n中 $1^{k_1}{2}^{k_2}\cdots n^{k_n}$ 型置换的个数为

$\frac{n!}{1^{k_1}{k}_1!2^{k_2}{k}_2!\cdots n^{k_n}{k}_n!}$ (5)

第一类Stirling数的指数生成函数为 ${\displaystyle \underset{n\ge r}{\sum }s\left(n,r\right)\frac{t^n}{n!}}=\frac{1}{r!}{\left(\ln \left(1+t\right)\right)}^r$。

错排数D_n的指数生成函数为 ${\displaystyle \underset{n\ge 0}{\sum }{D}_n\frac{t^n}{n!}}=\frac{1}{{\text{e}}^t\left(1-t\right)}$。

定理4. 对任意正整数n， $D_n={\displaystyle \underset{\begin{array}{l}{k}_2+k_3+\cdots +k_n=k\\ 2k_2+3k_3+\cdots +n{k}_n=n\end{array}}{\sum }\frac{n!}{2^{k_2}{k}_2!\cdots n^{k_n}{k}_n!}}$。

证明：取 $f\left(x\right)=\ln \left(x\right)$ 、 $\varphi \left(t\right)=\frac{1}{{\text{e}}^t\left(1-t\right)}$，显然 $f\circ \varphi \left(0\right)=0$。由于 $\varphi \left(t\right)$ 的 $t^n$ 项系数为 $\left[\begin{array}{c}\varphi \\ n\end{array}\right]=\frac{D_n}{n!}$。

因为 $f\circ \varphi \left(t\right)=-\ln \left(1-t\right)-t=\frac{t^2}{2}+\frac{t^3}{3}+\cdots$，对任意正整数i

$\left[\begin{array}{c}f\circ \varphi \\ n\end{array}\right]=\{\begin{array}{l}0,当i=1\\ \frac{1}{i},当i\ne 1\end{array}$

因为 $\left[\begin{array}{c}f\circ \varphi \\ 1\end{array}\right]=0$，只有 $k_1=0$ 时 $\frac{{\left[\begin{array}{c}f\circ \varphi \\ 1\end{array}\right]}^{k_1}{\left[\begin{array}{c}f\circ \varphi \\ 2\end{array}\right]}^{k_2}\cdots {\left[\begin{array}{c}f\circ \varphi \\ n\end{array}\right]}^{k_n}}{k_1!k_2!\cdots k_n!}\ne 0$，故而，由Faà di Bruno(4)可知

$\frac{D_n}{n!}={\displaystyle \underset{\sigma \left(n\right)}{\sum }\frac{{\left[\begin{array}{c}f\circ \varphi \\ 1\end{array}\right]}^{k_1}{\left[\begin{array}{c}f\circ \varphi \\ 2\end{array}\right]}^{k_2}\cdots {\left[\begin{array}{c}f\circ \varphi \\ n\end{array}\right]}^{k_n}}{k_1!k_2!\cdots k_n!}}={\displaystyle \underset{\begin{array}{l}{k}_2+k_3+\cdots +k_n=k\\ 2k_2+3k_3+\cdots +n{k}_n=n\end{array}}{\sum }\frac{1}{2^{k_2}{k}_2!\cdots n^{k_n}{k}_n!}}$

也即 $D_n={\displaystyle \underset{\begin{array}{l}{k}_2+k_3+\cdots +k_n=k\\ 2k_2+3k_3+\cdots +n{k}_n=n\end{array}}{\sum }\frac{n!}{2^{k_2}{k}_2!\cdots n^{k_n}{k}_n!}}$。

注4：定理4的恒等式可直接由错排数本身的定义得到，由(5)可知定理4中连加符号内的被加项分别为 $1^{k_1}{2}^{k_2}\cdots n^{k_n}$ 型置换及 $1^0{2}^{k_2}\cdots n^{k_n}$ 型置换的个数。

先观察定理中的置换，这些置换所对应的 $\left(k_1,k_2,\cdots ,k_n\right)$ 为 $\sigma \left(n,r\right)$ 内的元素，从而 $\left(k_1,k_2,\cdots ,k_n\right)$ 必须满足

$\{\begin{array}{l}{k}_1+k_2+\cdots +k_n=r\\ k_1+2k_2+\cdots +n{k}_n=n\end{array}$

另一方面，对所有 $1\le i\le n$，$k_i$ 代表长度为i的互斥圈的个数，所以 $k_1+k_2+\cdots +k_n=r$ 代表互斥圈的总数为r，而 $k_1+2k_2+\cdots +n{k}_n=n$ 则代表这个置换是 $S_n$ 中的元素，因此 ${\displaystyle {\sum }_{\sigma \left(n,r\right)}\frac{n!}{1^{k_1}{k}_1!2^{k_2}{k}_2!\cdots n^{k_n}{k}_n!}}$ 可以解释为 $S_n$ 中互斥圈总数为r的置换的个数，于是得到了组合学中广为人知的 $\left|S\left(n,r\right)\right|$ 的组合意义： $S_n$ 中互斥圈总数为r的置换的个数。

而定理4中的置换对应的 $\left(k_1,k_2,\cdots ,k_n\right)$ 需满足

$\{\begin{array}{l}{k}_1=0\\ k_1+k_2+\cdots +k_n=k\left(1\le k\le n\right)\\ k_1+2k_2+\cdots +n{k}_n=n\end{array}$

其中因为 $k_1=0$，这些置换分解成相斥圈后，都不具有长度为1的圈，换句话说就是没有固定点，因此 ${\displaystyle \underset{\begin{array}{l}{k}_2+k_3+\cdots +k_n=k\\ 2k_2+3k_3+\cdots +n{k}_n=n\end{array}}{\sum }\frac{n!}{2^{k_2}{k}_2!\cdots n^{k_n}{k}_n!}}$ 为S_n的所有置换中，不具有固定点的置换的个数，用比较贴近生活的言语表达即是：

有n个人参加宴会，每个人各戴一顶帽子，宴会进场时，n人皆将帽子交给服务生，宴会结束后n人拿回帽子，没有人拿到自己帽子的情况的个数。

这就是错排最初被提出时的问题。

取 $f\left(x\right)=\ln \left(x\right)$ 、 $\varphi \left(t\right)=\frac{1}{{\text{e}}^t\left(1-t\right)}$，显然 $f\circ \varphi \left(0\right)=0$。由于 $\varphi \left(t\right)$ 的 $t^n$ 项系数为 $\left[\begin{array}{c}\varphi \\ n\end{array}\right]=\frac{D_n}{n!}$。

因为 $f\circ \varphi \left(t\right)=-\ln \left(1-t\right)-t=\frac{t^2}{2}+\frac{t^3}{3}+\cdots$

由定理4证明的过程中，发现利用Faà di Bruno得到的等式可以更进一步的探讨错排的问题。

回顾当时的证明，取 $D_n$ 的指数生成函数 $\varphi \left(t\right)=\frac{1}{{\text{e}}^t\left(1-t\right)}$ 、 $f\left(x\right)=\ln \left(x\right)$，所以 $f\circ \varphi \left(t\right)=-\ln \left(1-t\right)-t=\frac{t^2}{2}+\frac{t^3}{3}+\cdots$，因为 $\ln \frac{1}{{\text{e}}^t\left(1-t\right)}$ 中的 $\ln \frac{1}{{\text{e}}^t}$ 消去了 $\ln \frac{1}{1-t}$ 的t系数， $\left[\begin{array}{c}f\circ \varphi \\ 1\end{array}\right]=0$ 迫使 $k_1=0$ 代表置换中长度为1的圈的个数为0，因为，可以得到此类置换的个数。

现在观察 $\varphi \left(t\right)$，首先注意到因为 $\frac{1}{1-t}=1+t+t^2+t^3+\cdots =1+t+2!\frac{t^2}{2!}+3!\frac{t^3}{3!}+\cdots$。

所以 $\frac{1}{1-t}$ 为对称群元素个数 $\left|S_n\right|$ 的指数生成函数，而由先前讨论可知， $\frac{1}{1-t}$ 乘上 ${\text{e}}^{-t}$ 后使得具有长度1的圈被排除而得到 $D_n$ 的指数生成函数，因此猜测经由乘上e的幂次也能排除具有其他长度圈的置换。

定理5. 对任意正整数n，

$B_n={\displaystyle \underset{\sigma \left(n\right)}{\sum }\frac{n!}{{\left(1!\right)}^{k_1}{k}_1!{\left(2!\right)}^{k_2}{k}_2!\cdots {\left(n!\right)}^{k_n}{k}_n!}}$

证明：取 $f\left(x\right)={\text{e}}^x$ 、 $\varphi \left(t\right)={\text{e}}^t-1$，显然 $\varphi \left(0\right)=0$。对所有正整数i

$\left[\begin{array}{c}\varphi \\ i\end{array}\right]=\frac{1}{i!}$，故而 $\left[\begin{array}{c}f\circ \varphi \\ 1\end{array}\right]={\text{e}}^{\left[\begin{array}{c}{\text{e}}^{t-1}\\ n\end{array}\right]}=\frac{B_n}{n!}$。

利用Faà di Bruno的(3)得 $\frac{B_n}{n!}={\displaystyle \underset{\sigma \left(n\right)}{\sum }\frac{1}{{\left(1!\right)}^{k_1}{k}_1!{\left(2!\right)}^{k_2}{k}_2!\cdots {\left(n!\right)}^{k_n}{k}_n!}}$。

等号两边同时乘以 $n!$ 得到 $B_n={\displaystyle \underset{\sigma \left(n\right)}{\sum }\frac{n!}{{\left(1!\right)}^{k_1}{k}_1!{\left(2!\right)}^{k_2}{k}_2!\cdots {\left(n!\right)}^{k_n}{k}_n!}}$。

注8. 定理也可以直接由Bell数的定义把定理从r = 1到r = n的情况加起来得到，但这里由其生成函数出发，利用Faà di Bruno也能导出相同的结论。

定理中连加符号内的被加项为 $\frac{n!}{{\left(1!\right)}^{k_1}{k}_1!{\left(2!\right)}^{k_2}{k}_2!\cdots {\left(n!\right)}^{k_n}{k}_n!}$。

可知其恰为将n元集合分割成k_i个i元子集(1 ≤ I ≤ n)的方法数，定理中每一个被加项对应到的 $\left(k_1,k_2,\cdots ,k_n\right)$ 都是 $\sigma \left(r\right)$ 里的元素，即必须满足

$\{\begin{array}{l}{k}_1+k_2+\cdots +k_n=r\\ k_1+2k_2+\cdots +n{k}_n=n\end{array}$

所以可以将每一个被加项都视为一个分割， $k_1+k_2+\cdots +k_n=r$ 表示这个分割的子集合总数， $k_1+2k_2+\cdots +n{k}_n=n$ 则代表被分割的集合里有n个元素，因此可以解释成将n元相异集合分割成r个子集的方法数，于是得到一般熟知的 $S\left(n,r\right)$ 的组合意义—将n元相异集合分割成r个子集合的方法数。又因为 $\sigma \left(n\right)={\displaystyle {\cup }_{k=0}^n\sigma \left(n,k\right)}$，立即可以得到B_n的组合意义—分割n元相异集合的方法数。

因为定理的启发，利用类似于定理中排除有某些特定长度圈的置换的方法，也可以用来限制分割集合时产生的子集大小，结果如下：

给定一集合 $P\subset N$。一个n元集合若分割成子集后不具有元素个数为 $j\in P$ 的子集时，称此种分割为“P免除分割”。

4. 总结

代数组合学是组合数学中最重要的分支之一，它有着丰富的内容和广泛的应用，著名的Faà di Bruno公式，Bell多项式以及对称群循环指标是代数组合学中重要的组成部分，三者息息相关，密不可分 [8]。Faà di Bruno公式起源可以追溯到十九世纪，其主要是解决复合函数的高阶求导问题，很多数学家曾对此作出过贡献：Scott，Meyer，Hoppe，Faà di Bruno等等。Faà di Bruno公式有很多种表达形式，最常见的是用Bell多项式来表示，然而，事实上，Bell多项式本来是集合分拆的数学工具，与Faà di Bruno公式并无直接联系，后来，Riordan发现Bell多项式非常适合对Faà di Bruno的表达。

同样运用Faà di Bruno公式，王兴华证明了对于复多项式，Halley族迭代的所有额外不动点都是斥性的。该结果比之前的发现要早六年解决其中的问题。Faà di Bruno公式也被应用到曲线插值的误差估计上，Floater和他的合作者研究了参数选择在插值逼近阶上的影响，证明了弦长参数值的三次及三次以上多项式能够饱和逼近曲线，井且给出了相应的算法．该算法也能够被用来估计曲线的长度 [9]。另外，王兴华通过利用Bell多项式和对称群的循环指标，建立了同时获得多项式所有根的并行和区间迭代．该结果成为文献的主要部分，另外，UlrichAbel和Mircea Ivan把Bell多项式运用到了区间趋向于零时差商的澈分中值定理的渐进展开上面。

一个复合函数的高阶导数是什么？至今最好的答案就是Faà di Bruno公式，从Gousat和ValleePoussin的著作中可以看到，曾经Faà di Bruno公式被认为是实分析中的一个结果。而Riordan和Comtet把它看作是代数组合学的一部分，Faà di Bruno公式广泛地出现在整数拆分、数学统计、矩阵理论、有限差分的微积分学、科学计算、对称函数等各个领域中。

Faà di Bruno公式有着悠久的历史。Faà di Bruno曾经把他的公式发表在期刊上，两者都是在1855年的12月份，文章较短，本质上基本相同。现在常见的Faà di Bruno公式有三种形式分别是集合分拆形式，Bell多项式形式和行列式形式。事实上，根据Lukacs关于函数高阶导数的显式表达问题，最早在1810年Lacriox的关于微积分的论文中已经提到 [10]。除了Faà di Bruno公式，曾经已有不少数学工作者给出了各种类型的表示，Johnson在他的文章中列出了四种有关复合函数高阶导数的表达式，即分别是T.A.，Scott，Meyer和Hoppe公式。自从Faà di Bruno公式第一次出现以后，对它的各种证明不断涌现，而且，Faà di Bruno公式被广泛地应用到数学的各个领域。同时也出现了与其相关的一系列恒等式，随着问题的深化Faà di Bruno公式也进一步发展为多变量的情形和q的形式。

对称群的循环指标多项式是表现力极强的解析工具，有很大一类超越函数可以用对称群的循环指标多项式予以表示。王兴华利用对称群的循环指标多项式建立了一族求多项式所有零点的并行迭代。后来，王兴华给出了数值分析中经典的Hermite插值的对称群循环指标表示，可以看到Hermite插值可以被对称群循环指标表达得十分简单明了。人们对对称群的循环指标多项式重视程度还是不够，没有真正认识到它的重要性，比如拿十分优秀的数学手册来说，尽管其第24章组合分析中已经介绍了对称群的循环指标多项式，但是很少把它作为一种工具使用对于王兴华等人的结果完全可以列入第25章插值，数值微分和数值积分中。

差商是数值分析中很重要的一部分内容，特别是对样条理论的发展一直扮演著主要角色众所皆知，在B样条的递归关系中，它是一个基本工具。商有很多种定义方法，通常把它当作是牛顿插值的系数或者直接通过递归来定义。差商有多种表示方式，常见的有行列式比表示、Peano核表示方式、围道积分形式和Genocchi-Hermite表示形式。由于差商在数值分析中的重要性，所以一直以来许多作者对其性质和应用的研究从未间断过早期，对差商性质的应用多见于数值微分上，如上世纪九十年代，Powers等人研究了两种微分中值定理的渐进性质。第一种是与差商相关的形式，第二种是推广的Flett中值定理。2004年，UlrichAbel等人根据差商推广了该定理。同样利用差商的性质，Horwitz研究了另一种类型的中值的极限行为近来，杨专门对差商的性质进行了讨论，并把它们应用到基于第二类Chebyshev多项式零点的数值积分公式上。Floater在中给出了差商展开的误差，在此基础上，C.deBoor给出了差商的差商展开进一步，王兴华与其合作者得到了数值差商的一些结果，用一组节点的差商来表示同一个函数的给定节点的差商，当给定节点比较密集因而在其上的差商难以直接计算时，把它用另一组由自己选取的较为疏朗的节点上的差商表示出来，以便能顺利的进行数值计算。有趣的是，Adell等人应用上面的一系列结果于统计之中。

在参变量多项式插值的研究中，需要估计一个复合函数 $h=f\circ g$ 差商的界，王兴华和Floater分别用不同的方法独立的解决了该问题，并且，把该公式应用到行列式恒等式上，从而得到了一系列漂亮的组合恒等式。

文章引用

沈 萍. Faà di Bruno公式在恒等式及计数上的应用
Application of Faà di Bruno’s Formula in Identity and Counting[J]. 理论数学, 2022, 12(12): 2231-2238. https://doi.org/10.12677/PM.2022.1212240

参考文献