login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A133686 Number of labeled n-node graphs with at most one cycle in each connected component. 4
1, 1, 2, 8, 57, 608, 8524, 145800, 2918123, 66617234, 1704913434, 48300128696, 1499864341015, 50648006463048, 1847622972848648, 72406232075624192, 3033607843748296089, 135313823447621913500, 6402077421524339766058, 320237988317922139148736 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

The total number of those graphs of order 5 is 608. The number of forests of trees on n labeled nodes of order 5 is 291, so the majority of the graphs of that kind have one or more unicycles.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..140

Wikipedia, Pseudoforest

FORMULA

a(0) = 1; for n >=1, a(n) = Sum of n!prod_{j=1}^n\{ frac{ A129271(j)^{c_j} } { j!^{c_j}c_j! } } over all the partitions of n, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0.

a(n) = Sum_{k=0..n} A144228(n,k). - Alois P. Heinz, Sep 15 2008

E.g.f.: sqrt(-LambertW(-x)/(x*(1+LambertW(-x))))*exp(-3/4 * LambertW(-x)^2). - Vladeta Jovovic, Sep 16 2008

E.g.f.: A(x)*B(x) where A(x) is the e.g.f. for A137916 and B(x) is the e.g.f. for A001858. - Geoffrey Critzer, Mar 23 2013

a(n) ~ 2^(-1/4) * Gamma(3/4) * exp(-1/4) * n^(n-1/4) / sqrt(Pi) * (1-7*Pi/(12*Gamma(3/4)^2*sqrt(n))). - Vaclav Kotesovec, Oct 08 2013

EXAMPLE

Below we see the 7 partitions of n=5 in the form c_1 + 2c_2 + ... + nc_n followed by the corresponding number of graphs. We consider the values of A129271(j) given by the table

   j|1|2|3| 4|  5|

----+-+-+-+--+---+

a(j)|1|1|4|31|347|

1*5 -> 5!1^5 / (1!^5 * 5!) = 1

2*1 + 1*3 -> 5!1^1 * 1^3 / (2!^1 * 1! * 1!^3 * 3!) = 10

2*2 + 1*1 -> 5!1^2 * 1^1 / (2!^2 * 2! * 1!^1 * 1!) = 15

3*1 + 1*2 -> 5!4^1 * 1^2 / (3!^1 * 1! * 1!^2 * 2!) = 40

3*1 + 2*1 -> 5!4^1 * 1^1 / (3!^1 * 1! * 2!^1 * 1!) = 40

4*1 + 1*1 -> 5!31^1 * 1^1 / (4!^1 * 1! * 1!^1 * 1!) = 155

5*1 -> 5!347^1 / (5!^1 * 1!) = 347

Total 608

MAPLE

cy:= proc(n) option remember; binomial(n-1, 2)*

        add((n-3)!/(n-2-t)! *n^(n-2-t), t=1..n-2)

     end:

T:= proc(n, k) option remember;

      if k=0 then 1

    elif k<0 or n<k then 0

    else add(binomial(n-1, j)*((j+1)^(j-1)*T(n-j-1, k-j)

             +cy(j+1)*T(n-j-1, k-j-1)), j=0..k)

      fi

    end:

a:= n-> add(T(n, k), k=0..n):

seq(a(n), n=0..20); # Alois P. Heinz, Sep 15 2008

MATHEMATICA

nn=20; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; Range[0, nn]!CoefficientList[ Series[ Exp[t/2-3t^2/4]/(1-t)^(1/2), {x, 0, nn}], x] (* Geoffrey Critzer, Sep 05 2012 *)

PROG

(PARI) x='x+O('x^50); Vec(serlaplace(sqrt(-lambertw(-x)/(x*(1+ lambertw(-x))))*exp(-(3/4)*lambertw(-x)^2))) \\ G. C. Greubel, Nov 16 2017

CROSSREFS

Cf. A129137, A005703, A000272, A057500, A129271, A134964, A137916, A001858.

Row sums of triangle A144228. - Alois P. Heinz, Sep 15 2008

Cf. A137352. - Vladeta Jovovic, Sep 16 2008

Sequence in context: A153529 A153558 A027335 * A153525 A153553 A191481

Adjacent sequences:  A133683 A133684 A133685 * A133687 A133688 A133689

KEYWORD

easy,nonn

AUTHOR

Washington Bomfim, May 12 2008

EXTENSIONS

Corrected and extended by Alois P. Heinz and Vladeta Jovovic, Sep 15 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 15 22:48 EDT 2019. Contains 325061 sequences. (Running on oeis4.)