7,129
个编辑
更改
跳到导航
跳到搜索
第46行：
第46行： − + +
→组合计数
其中{{math|1=''n'' = 0, 1, 2, 3,……}}。这个数列的<font color="#ff8000"> '''递推关系式 Recurrence relation''' </font>是
其中{{math|1=''n'' = 0, 1, 2, 3,……}}。这个数列的<font color="#ff8000"> '''递推关系式 Recurrence relation''' </font>是
:<math>a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.</math><ref name="enum" />
:<math>a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.</math><ref name="enum" />
埃里克·韦斯坦因 Eric W. Weisstein <ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture}}</ref>，{{mvar|n}}个顶点的标号有向无环图的数量与其中所有<font color="#ff8000"> '''特征值 Eigenvalues''' </font>都为正实数的{{math|n*n}}<font color="#ff8000"> '''逻辑矩阵''' </font>的数量相同。这一点随后被 McKay 证实，证明采用了<font color="#ff8000"> '''双射法 Bijective'''</font>：一个矩阵{{mvar|A}}是有向无环图的一个<font color="#ff8000"> '''邻接矩阵 Adjacency matrix''' </font>，当且仅当{{math|''A'' + ''I''}}是一个所有特征值都为正数的逻辑矩阵，其中{{mvar|I}}为<font color="#ff8000"> '''单位矩阵 Identity matrix''' </font>。因为一个有向无环图不允许<font color="#ff8000"> '''自环 Self-loops''' </font>，它的邻接矩阵的对角线必定全为0。因此，加上{{mvar|I}}保持了所有矩阵因子都是0或1的特性。<ref>{{citation|last1=McKay|first1=B. D.|last2=Royle|first2=G. F.last3=Wanless|first3=I. M.|last4=Oggier|first4=F. E. |last5=Sloane|first5=N. J. A.|last6=Wilf|first6=H.|title=Acyclic digraphs and eigenvalues of (0,1)-matrices|journal=[[Journal of Integer Sequences]]|volume=7|year=2004|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html}}, Article 04.3.3.</ref>
埃里克·韦斯坦因 Eric W. Weisstein <ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture}}</ref>，{{mvar|n}}个顶点的标号有向无环图的数量与其中所有<font color="#ff8000"> '''特征值 Eigenvalues''' </font>都为正实数的{{math|n*n}}<font color="#ff8000"> '''逻辑矩阵''' </font>的数量相同。这一点随后被 McKay 证实，证明采用了<font color="#ff8000"> '''双射法 Bijective'''</font>：一个矩阵{{mvar|A}}是有向无环图的一个<font color="#ff8000"> '''邻接矩阵 Adjacency matrix''' </font>，当且仅当{{math|''A'' + ''I''}}是一个所有特征值都为正数的逻辑矩阵，其中{{mvar|I}}为<font color="#ff8000"> '''单位矩阵 Identity matrix''' </font>。因为一个有向无环图不允许<font color="#ff8000"> '''自环 Self-loops''' </font>，它的邻接矩阵的对角线必定全为0。因此，加上{{mvar|I}}保持了所有矩阵因子都是0或1的特性。<ref>{{citation|last1=McKay|first1=B. D.|last2=Royle|first2=G. F.last3=Wanless|first3=I. M.|last4=Oggier|first4=F. E. |last5=Sloane|first5=N. J. A.|last6=Wilf|first6=H.|title=Acyclic digraphs and eigenvalues of (0,1)-matrices|journal=Journal of Integer Sequences|volume=7|year=2004|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html}}, Article 04.3.3.</ref>
<br>
===相关概念===
===相关概念===