A380631 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with k cycles and each node a member of exactly one cycle, 0 <= k <= floor(n/3).
1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 2, 0, 1, 2, 2, 0, 1, 3, 5, 0, 1, 3, 10, 0, 1, 4, 17, 6, 0, 1, 4, 26, 18, 0, 1, 5, 38, 51, 0, 1, 5, 52, 106, 18, 0, 1, 6, 70, 205, 87, 0, 1, 6, 90, 350, 286, 0, 1, 7, 115, 579, 741, 66, 0, 1, 7, 142, 887, 1660, 406
Offset: 0
Examples
Triangle begins: 1; 0; 0; 0, 1; 0, 1; 0, 1; 0, 1, 1; 0, 1, 1; 0, 1, 2; 0, 1, 2, 2; 0, 1, 3, 5; 0, 1, 3, 10; 0, 1, 4, 17, 6; 0, 1, 4, 26, 18; 0, 1, 5, 38, 51; 0, 1, 5, 52, 106, 18; ...
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..1750 (rows 0..100)
- Wikipedia, Cactus graph.
- Index entries for sequences related to cacti.
Crossrefs
Programs
-
PARI
EulerMTS(p)={my(n=serprec(p,x)-1,vars=variables(p)); exp(sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i))} raise(p,d) = {my(n=serprec(p,x)-1); substvec(p + O(x^(n\d+1)), [x,y], [x^d,y^d])} R(n,y)={my(g = O(x^3)); for(n=1, (n-1)\2, my(p=x*EulerMTS(g), p2=raise(p,2)); g=p*y*(p^2/(1 - p) + (1 + p)*p2/(1 - p2))/2); g} G(n,y=1)={my(g=R(n,y), p = x*EulerMTS(g) + O(x*x^n)); my( r=((1 + p)^2/(1 - raise(p,2)) - 1)/2 ); my( c=-sum(d=1, n, eulerphi(d)/d*log(raise(1-p,d))) ); 1 + (raise(g,2) - g^2 + y*(r + c - 2*p - p^2 - raise(p,2)))/2 } T(n)={[Vecrev(p) | p<-Vec(G(n,y))]} { my(A=T(15)); for(i=1, #A, print(A[i])) }
Formula
T(3*n, n) = A380634(n).
Comments