login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A119627 Number of labeled graphs with no isolated nodes of size up to n+1 nodes, using 2*n+2 unique labels (no two nodes can have the same label). 0
6, 95, 3122, 202671, 25992373, 6561168159, 3271778102626, 3238332198581151, 6386927543425690577, 25167828012974622494207, 198457647877828107872246829, 3134149754118486012018252515615 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Replacing 2*n+2 in the formula with m gives the formula to calculate the number of labeled graphs with no isolated nodes of size up to n+1 nodes, using m unique labels (with m > n). An alternative (and much more complicated!) way to find the sequence is with the following recurrence (n>1, m>n): a(n,m)=a(n-1,m)+binomial(m,n)*(-a(n-1,n+1)+sum_{k=1..n*(n+1)/2}binomial(n*(n+1)/2,k)), a(2,m)=binomial(m,2)+binomial(m,3)+binomial(3,2)*binomial(m,3).

LINKS

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

FORMULA

a(n)=sum_{k=1..n+1}binomial(2*n+2,k)*A006129(k)

EXAMPLE

a(1)=6 because with 1+1 nodes and 2*1+2 labels, you can construct the following graphs: 1-2, 1-3, 1-4, 2-3, 2-4, 3-4. We have 6 different graphs.

MAPLE

A006125:=(n)->2^(n*(n-1)/2); A006129:=(n)->sum('binomial(n, i)*(-1)^i*A006125(n-i)', i=0..n); A:=(n)->sum('binomial(2*n+2, i)*A006129(i)', i=1..n+1);

CROSSREFS

Cf. A006125, A006129.

Sequence in context: A290984 A326436 A243802 * A336825 A116158 A275561

Adjacent sequences:  A119624 A119625 A119626 * A119628 A119629 A119630

KEYWORD

easy,nonn

AUTHOR

Delorme C. (delorme(AT)lri.fr), Lopez R. (lopez(AT)lri.fr), Soguet D. (soguet(AT)lri.fr) Jun 08 2006

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 September 28 13:24 EDT 2020. Contains 337393 sequences. (Running on oeis4.)