Combinatorial Proof of an Abel-type Identity ∗
Combinatorial Proof of an Abel-type Identity ∗
复制标题
Abel 型恒等式的组合证明 *
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Dave Perkins
中科院分区：
文献类型：
--
作者：
P. M. Kayll;Dave Perkins
下面的恒等式（1）是我们在[21]中对完全图K n（n ≥ 1）上的筹码射击游戏的研究得出的;参见，例如，[2]关于前因左侧表示游戏经历每个可能长度为0，1，...的射击序列的概率之和。..，n.本文给出了一个组合证明，证明这些概率和为1。我们首先将n − 1 n + 1 + n − 1 =1 n − 1 − n −1（n + 1 − n）n−1− n（n + 1）n−1 = 1（1）转化为一种适合于组合证明的形式。乘以n（n + 1）n并使用关系n = n+1（n + 1 −）/（n + 1），我们将（1）变换为等价形式n =1 n + 1 −2（n + 1 −）n−1 −（n +1 −）= 2n（n + 1）n−1。(2)为了证明（2）成立，首先观察右侧枚举了对（T，e），其中T是Kn +1的生成树，其中一条边e（的
Identity (1) below resulted from our investigation in [21] of chip-firing games on complete graphs K n , for n ≥ 1; see, e.g., [2] for antecedents. The left side expresses the sum of the probabilities of a game experiencing firing sequences of each possible length ℓ = 0, 1,. .. , n. This note gives a combinatorial proof that these probabilities sum to unity. We first manipulate n − 1 n + 1 + n ℓ=1 n ℓ ℓ ℓ−1 (n + 1 − ℓ) n−1−ℓ n(n + 1) n−1 = 1 (1) into a form amenable to combinatorial proof. Multiplying by n(n + 1) n and using the relation n ℓ = n+1 ℓ (n + 1 − ℓ)/(n + 1), we transform (1) to the equivalent form n ℓ=1 n + 1 ℓ ℓ ℓ−2 (n + 1 − ℓ) n−1−ℓ ℓ(n + 1 − ℓ) = 2n(n + 1) n−1. (2) To see that (2) holds, first observe that the right side enumerates the pairs (T, e), where T is a spanning tree of K n+1 for which one edge e (of