第28行: |
第28行: |
| |last1 = Harary | first1 = Frank | author1-link = Frank Harary | first2 = Edgar M. | last2 = Palmer | year = 1973| title = Graphical Enumeration | publisher = [[Academic Press]] | isbn = 978-0-12-324245-7 | page=19}}.</ref> | | |last1 = Harary | first1 = Frank | author1-link = Frank Harary | first2 = Edgar M. | last2 = Palmer | year = 1973| title = Graphical Enumeration | publisher = [[Academic Press]] | isbn = 978-0-12-324245-7 | page=19}}.</ref> |
| 如标号顶点在拓扑排序中出现的顺序不受限制,有{{mvar|n}}个顶点的标号有向无环图的数量为 | | 如标号顶点在拓扑排序中出现的顺序不受限制,有{{mvar|n}}个顶点的标号有向无环图的数量为 |
− | :1, 1, 3, 25, 543, 29281, 3781503, … {{OEIS|id=A003024}}。 | + | :1, 1, 3, 25, 543, 29281, 3781503, … (OEIS中的数列A003024)。 |
− | 其中{{math|1=''n'' = 0, 1, 2, 3,……}}。这个数列的[[递推关系式]]是 | + | 其中{{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" /> |
| [[埃里克·韦斯坦因]]推测<ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture}}</ref>,{{mvar|n}}个顶点的标号有向无环图的数量与其中所有[[特征值和特征向量|特征值]]都为正实数的{{math|n*n}}[[逻辑矩阵]]的数量相同。这一点随后被证实,证明采用了[[双射法]]:一个矩阵{{mvar|A}}是有向无环图的一个[[邻接矩阵]],当且仅当{{math|''A'' + ''I''}}是一个所有特征值都为正数的逻辑矩阵,其中{{mvar|I}}为[[单位矩阵]]。因为一个有向无环图不允许[[自环]],它的邻接矩阵的对角线必定全为0。因此,加上{{mvar|I}}保持了所有矩阵因子都是0或1的特性。<ref>{{citation|last1=McKay|first1=B. D.|author1-link=Brendan McKay|last2=Royle|first2=G. F.|author2-link=Gordon Royle|last3=Wanless|first3=I. M.|last4=Oggier|first4=F. E.|author4-link= Frédérique Oggier |last5=Sloane|first5=N. J. A.|author5-link= Neil Sloane|last6=Wilf|first6=H.|author6-link=Herbert Wilf|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> | | [[埃里克·韦斯坦因]]推测<ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture}}</ref>,{{mvar|n}}个顶点的标号有向无环图的数量与其中所有[[特征值和特征向量|特征值]]都为正实数的{{math|n*n}}[[逻辑矩阵]]的数量相同。这一点随后被证实,证明采用了[[双射法]]:一个矩阵{{mvar|A}}是有向无环图的一个[[邻接矩阵]],当且仅当{{math|''A'' + ''I''}}是一个所有特征值都为正数的逻辑矩阵,其中{{mvar|I}}为[[单位矩阵]]。因为一个有向无环图不允许[[自环]],它的邻接矩阵的对角线必定全为0。因此,加上{{mvar|I}}保持了所有矩阵因子都是0或1的特性。<ref>{{citation|last1=McKay|first1=B. D.|author1-link=Brendan McKay|last2=Royle|first2=G. F.|author2-link=Gordon Royle|last3=Wanless|first3=I. M.|last4=Oggier|first4=F. E.|author4-link= Frédérique Oggier |last5=Sloane|first5=N. J. A.|author5-link= Neil Sloane|last6=Wilf|first6=H.|author6-link=Herbert Wilf|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> |