login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A291648
a(n) is the number of simple graphs of order n having at most one cycle (such graphs are called "at most unicyclic graphs").
1
1, 2, 4, 9, 19, 45, 105, 261, 657, 1708, 4498, 12081, 32752, 89792, 247893, 689004, 1924357, 5398587, 15197830, 42917215, 121507597, 344806293, 980423528, 2792741331, 7967842859, 22765631866, 65131178683, 186560990191, 53497417058, 1535637252938
OFFSET
1,2
COMMENTS
a(n) = A005195(n) + A236570(n). Proof: Since an at most unicyclic graph is either a forest or a unicyclic graph and since the latter two types of graphs have been enumerated (see A005195, A236570) the enumeration of the at most unicyclic graphs is the sum of the enumeration of the forests and unicyclic graphs, namely, the sum of the sequences A005195 and A236570, where these sequences start for n >= 1, respectively,
1, 2, 3, 6, 10, 20, 37, 76, ...
0, 0, 1, 3, 9, 25, 68 185, ... .
LINKS
E. G. DuCasse, L. V. Quintas, and J. M. Zorluoglu, The At Most Unicyclic Random Graph Process, Mathematics Department, Pace University, New York, No. 1 (2017).
EXAMPLE
For n = 4, a(4) = 6 + 3 = 9 and for n = 5, a(5) = 10 + 9 = 19
CROSSREFS
Cf. A005195 (number of forests with n unlabeled nodes), A236570 (number of n-node unicyclic graphs).
Sequence in context: A316473 A316501 A036612 * A036613 A036614 A036718
KEYWORD
nonn
AUTHOR
Louis V QUINTAS, Aug 28 2017
STATUS
approved

  NODES
orte 1
see 2
Story 1