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, 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

Table of n, a(n) for n=1..30.

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

Adjacent sequences: A291645 A291646 A291647 * A291649 A291650 A291651

Keyword

nonn

Author

Louis V QUINTAS, Aug 28 2017

Status

approved