***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew <info@findstat.org> * * * * This information is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * ***************************************************************************** ----------------------------------------------------------------------------- Statistic identifier: St001827 ----------------------------------------------------------------------------- Collection: Graphs ----------------------------------------------------------------------------- Description: The number of two-component spanning forests of a graph. A '''spanning subgraph''' is a subgraph which contains all vertices of the ambient graph. A '''forest''' is a graph which contains no cycles, and has any number of connected components. A '''two-component spanning forest''' is a spanning subgraph which contains no cycles and has two connected components. ----------------------------------------------------------------------------- References: [1] Kassel, A., Kenyon, R., Wu, W. Random two-component spanning forests [[MathSciNet:3414453]] [[zbMATH:1334.82011]] [[DOI:10.1214/14-AIHP625]] [[arXiv:1203.4858]] [2] Number of forests with two connected components in the complete graph K_n. [[OEIS:A083483]] [3] Number a(n) of forests with two components in the complete bipartite graph K_n,n. [[OEIS:A100070]] ----------------------------------------------------------------------------- Code: ----------------------------------------------------------------------------- Statistic values: ([],1) => 0 ([],2) => 1 ([(0,1)],2) => 1 ([],3) => 0 ([(1,2)],3) => 1 ([(0,2),(1,2)],3) => 2 ([(0,1),(0,2),(1,2)],3) => 3 ([],4) => 0 ([(2,3)],4) => 0 ([(1,3),(2,3)],4) => 1 ([(0,3),(1,3),(2,3)],4) => 3 ([(0,3),(1,2)],4) => 1 ([(0,3),(1,2),(2,3)],4) => 3 ([(1,2),(1,3),(2,3)],4) => 3 ([(0,3),(1,2),(1,3),(2,3)],4) => 6 ([(0,2),(0,3),(1,2),(1,3)],4) => 6 ([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 10 ([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 15 ([],5) => 0 ([(3,4)],5) => 0 ([(2,4),(3,4)],5) => 0 ([(1,4),(2,4),(3,4)],5) => 1 ([(0,4),(1,4),(2,4),(3,4)],5) => 4 ([(1,4),(2,3)],5) => 0 ([(1,4),(2,3),(3,4)],5) => 1 ([(0,1),(2,4),(3,4)],5) => 1 ([(2,3),(2,4),(3,4)],5) => 0 ([(0,4),(1,4),(2,3),(3,4)],5) => 4 ([(1,4),(2,3),(2,4),(3,4)],5) => 3 ([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 9 ([(1,3),(1,4),(2,3),(2,4)],5) => 4 ([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 10 ([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 8 ([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 9 ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 18 ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 20 ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 32 ([(0,4),(1,3),(2,3),(2,4)],5) => 4 ([(0,1),(2,3),(2,4),(3,4)],5) => 3 ([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 9 ([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => 18 ([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => 10 ([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 19 ([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => 32 ([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 18 ([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 16 ([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 31 ([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 51 ([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => 33 ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 52 ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 77 ([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 110 ([],6) => 0 ([(4,5)],6) => 0 ([(3,5),(4,5)],6) => 0 ([(2,5),(3,5),(4,5)],6) => 0 ([(1,5),(2,5),(3,5),(4,5)],6) => 1 ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 5 ([(2,5),(3,4)],6) => 0 ([(2,5),(3,4),(4,5)],6) => 0 ([(1,2),(3,5),(4,5)],6) => 0 ([(3,4),(3,5),(4,5)],6) => 0 ([(1,5),(2,5),(3,4),(4,5)],6) => 1 ([(0,1),(2,5),(3,5),(4,5)],6) => 1 ([(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => 5 ([(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 12 ([(2,4),(2,5),(3,4),(3,5)],6) => 0 ([(0,5),(1,5),(2,4),(3,4)],6) => 1 ([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => 5 ([(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => 5 ([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 14 ([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 8 ([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 12 ([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 26 ([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 12 ([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 14 ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 32 ([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 20 ([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 26 ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 52 ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 64 ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 96 ([(0,5),(1,4),(2,3)],6) => 0 ([(1,5),(2,4),(3,4),(3,5)],6) => 1 ([(0,1),(2,5),(3,4),(4,5)],6) => 1 ([(1,2),(3,4),(3,5),(4,5)],6) => 0 ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => 5 ([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 3 ([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 12 ([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 9 ([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 27 ([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 5 ([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 14 ([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 11 ([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => 15 ([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 8 ([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 12 ([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 30 ([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 26 ([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 21 ([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 53 ([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => 5 ([(0,1),(2,4),(2,5),(3,4),(3,5)],6) => 4 ([(0,5),(1,5),(2,3),(2,4),(3,4)],6) => 3 ([(0,4),(1,2),(1,3),(2,5),(3,5),(4,5)],6) => 14 ([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6) => 12 ([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6) => 12 ([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 8 ([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 12 ([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6) => 30 ([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6) => 26 ([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 27 ([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 54 ([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0 ([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 26 ([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 16 ([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 47 ([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 34 ([(0,3),(0,5),(1,3),(1,5),(2,4),(2,5),(3,4),(4,5)],6) => 62 ([(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 52 ([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 53 ([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 58 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 98 ([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 57 ([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 40 ([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 47 ([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 91 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 108 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 160 ([(0,5),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 32 ([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 24 ([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 57 ([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 45 ([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 97 ([(0,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6) => 15 ([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6) => 33 ([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 30 ([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 31 ([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 26 ([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 30 ([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 58 ([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 53 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 59 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 99 ([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)],6) => 65 ([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 57 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 109 ([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 103 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 168 ([(0,5),(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 97 ([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 75 ([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 91 ([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 152 ([(0,4),(0,5),(1,2),(1,4),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 104 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 99 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 161 ([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 254 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)],6) => 117 ([(0,1),(0,2),(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 180 ([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 174 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 270 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 387 ([(0,4),(0,5),(1,2),(1,3),(2,3),(4,5)],6) => 9 ([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6) => 26 ([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6) => 27 ([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 16 ([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 54 ([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 47 ([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 93 ([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6) => 59 ([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 105 ([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 91 ([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 99 ([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 98 ([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 162 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 176 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 256 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6) => 63 ([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 59 ([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 105 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 170 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 111 ([(0,1),(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 176 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 169 ([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 264 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 389 ([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 168 ([(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 161 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 255 ([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 152 ([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 125 ([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 235 ([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 378 ([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 561 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 272 ([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 262 ([(0,1),(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 271 ([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 398 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 408 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 572 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 792 ([(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1080 ----------------------------------------------------------------------------- Created: Jul 26, 2022 at 11:37 by Harry Richman ----------------------------------------------------------------------------- Last Updated: Jul 26, 2022 at 11:37 by Harry Richman