cp's OEIS Frontend

A058879 Triangle read by rows: T(n,k) = number of connected graphs with one cycle of length m = n - k + 1 and n nodes (n >= 3 and 1 <= k <= n - 2).

%I A058879 #27 Sep 04 2022 12:28:50
%S A058879 1,1,1,1,1,3,1,1,4,7,1,1,4,9,18,1,1,5,10,28,44,1,1,5,13,32,71,117,1,1,
%T A058879 6,14,45,89,202,299,1,1,6,17,52,130,264,542,793,1,1,7,19,69,163,413,
%U A058879 751,1507,2095,1,1,7,22,79,224,544,1221,2179,4114,5607
%N A058879 Triangle read by rows: T(n,k) = number of connected graphs with one cycle of length m = n - k + 1 and n nodes (n >= 3 and 1 <= k <= n - 2).
%C A058879 Diagonals give A000226, A000368. Row sums give A001429.
%C A058879 From _Washington Bomfim_, Jul 06 2008: (Start)
%C A058879 T(n,3) = 2 + floor(m/2). When k = 3, n = m + 2, so we have unicyclic graphs of order m+2 with a cycle of length m. Only two nodes of those graphs belong to the rooted trees attached to the cycle, so the orders of those trees can be only 1, 2, or 3.
%C A058879 We can have only one tree of order 3 in those graphs. So the two different rooted trees of order 3 correspond to two unicycles.
%C A058879 We can have two trees of order 2 in those graphs. Those trees can be rooted at two points r_1, r_2 of the cycle in h = floor(m/2) ways. They can be neighbors, i.e., we have an edge of the cycle (r_1, r_2). They can be 2, 3, ..., h edges apart, but they cannot be h+1 edges away from each other. This is true because we obtain an isomorphic graph if r_1 and r_2 are h+1 (or more) edges apart, since there are also n - (h+1) edges between r_1 and r_2 and n-h-1 <= h. Note that there is only one rooted tree of order two.
%C A058879 The five unicyclic graphs of order 9 with a cycle of length 7 are depicted in the picture corresponding to the link.
%C A058879 T(n,4) = 4 + 2floor(m/2) + nearest integer to m^2/12.
%C A058879 We have unicyclic graphs of order m+3 with a cycle of length m. Only three nodes of those graphs belong to the rooted trees attached to the cycle, so the orders of those trees can be only 1, 2, 3, or 4. The set of unicycles can be divided in graphs with trees of orders
%C A058879 4,1,1,...,1
%C A058879 3,2,1,...,1
%C A058879 2,2,2,1,...,1.
%C A058879 Since there are 4 rooted trees of order 4, the orders 4,1,1,...,1 correspond to 4 unicycles.
%C A058879 The orders 3,2,1,...,1 correspond to 2floor(m/2) unicycles. For each one of the two rooted trees of order 3, we see above that there are floor(m/2) possibilities to choose a root for the tree of order 2.
%C A058879 The orders 2,2,2,1,...,1 correspond to i unicycles, i = nearest integer to m^2/12. This follows from the number of necklaces with n+3 beads 3 of which are red, that is equal to the nearest integer to (n+3)^2/12. See A001399. In our case we have necklaces with m beads. The 3 red beads are the roots of the trees of order 2. (End)
%D A058879 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 69, (3.4.1).
%D A058879 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150, Table 9.
%H A058879 Washington Bomfim, <a href="http://upload.wikimedia.org/wikipedia/commons/4/43/Uniciclos7_9.gif">The five unicyclic graphs of order 9 with a cycle of length 7: T(9,3)=5.</a>
%F A058879 T(n, k) = [x^n] Z(D_{n+1-k}; t(x)) where t(x) is the g.f. of A000081 and Z(D_m) is the cycle index of the dihedral group of order m. - _Sean A. Irvine_, Sep 03 2022
%e A058879 Triangle begins:
%e A058879   1;
%e A058879   1,  1;
%e A058879   1,  1,  3;
%e A058879   1,  1,  4,  7;
%e A058879   1,  1,  4,  9, 18;
%t A058879 Needs["NumericalDifferentialEquationAnalysis`"];
%t A058879 t[n_, k_] := Block[{x}, Coefficient[CycleIndexPolynomial[DihedralGroup[n + 1 - k], Table[ButcherTreeCount[n].x^(p Range[n]), {p, n + 1 - k}]], x, n]];
%t A058879 Table[t[n, k], {n, 13}, {k, 1, n - 2}] // Flatten
%t A058879 (* requires Mathematica 9+; _Andrey Zabolotskiy_, May 12 2017 *)
%Y A058879 Cf. A000081, A217781.
%K A058879 nonn,easy,tabl,nice
%O A058879 3,6
%A A058879 _N. J. A. Sloane_, Jan 07 2001
%E A058879 More terms from _Washington Bomfim_, May 12 2008
%E A058879 More terms from _Washington Bomfim_, Jul 06 2008
%E A058879 Rows n = 11 to 13 added, name and offset corrected by _Andrey Zabolotskiy_, May 12 2017