百科问答小站 logo
百科问答小站 font logo



如何证明以下的这个组合恒等式? 第1页

  

user avatar   yu-yiren-62 网友的相关建议: 
      

这是Abel组合恒等式(二项式定理的一种推广)

的一个特例。


user avatar   _elaina 网友的相关建议: 
      

只需证

对于

利用 ,比较系数即可

而上述级数用拉格朗日反演不难得到。


user avatar   fan-she-xu-shu 网友的相关建议: 
      

引理:以1,2,...,n为顶点的树有n^(n-2)个。

引理证明见proofs from the book。

考虑这样的组合对象的数量m:以1,2,...,n为顶点的树,其中特别标出一条边。

显然等式左边为m,下面考察等式右边。

任意把1,2,...,n划分成非空的两部分。设含有1的那部分有k个顶点。

在这两部分上分别任取一颗树,然后分别任取一个顶点,然后把这两个顶点连起来(并标出这条边),得到一颗完整的树。

易知这样的操作方案一一对应于一个标出一条边的树。而操作方案数恰好等于等式右边。

因此等式两边相等。




  

相关话题

  如何证明以下的这个组合恒等式? 
  如何估计Ramsey数的上界? 
  如何求解这个偏序集的问题? 
  n 座桥,连通 n+1 个岛,有多少种连法? 
  包含所有各项不大于n的n元正整数列且长度最小的序列有多少个? 
  对 n × n 网格图,从左下角走到右上角的边不重复路径(即左下角到右上角的迹)有多少种? 
  已知映射f:N→N(其中N是正整数集),问以下三条是否可以相容? 
  任给N个连续的整数,是否能从中找到一些数(至少一个),使得它们加起来是N(N+1)/2的倍数? 
  不用计算机程序,如何求1,2,…,n中所有与n互素的数的平方和? 
  下面这个组合恒等式如何证明? 

前一个讨论
如何证明满射有界线性算子的如下性质?
下一个讨论
如何证明这个与树有关的递推式?





© 2025-03-31 - tinynew.org. All Rights Reserved.
© 2025-03-31 - tinynew.org. 保留所有权利