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!)
A106239 Triangle read by rows: T(n,m) = number of graphs on n labeled nodes, with m components of size = order. Also number of graphs on n labeled nodes with m unicyclic components. 4
0, 0, 0, 1, 0, 0, 15, 0, 0, 0, 222, 0, 0, 0, 0, 3660, 10, 0, 0, 0, 0, 68295, 525, 0, 0, 0, 0, 0, 1436568, 20307, 0, 0, 0, 0, 0, 0, 33779340, 727020, 280, 0, 0, 0, 0, 0, 0, 880107840, 25934184, 31500, 0, 0, 0, 0, 0, 0, 0, 25201854045, 950478210, 2325015, 0, 0, 0, 0, 0, 0, 0, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,7

COMMENTS

Also the Bell transform of A057500(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

REFERENCES

D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions, Addison-Wesley, 2005, pp. 39, 47.

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

FORMULA

E.g.f.: exp((-y/2)*log(1+LambertW(-x)) + (y/2)*LambertW(-x) - (y/4)*LambertW(-x)^2). - Vladeta Jovovic, May 04 2005

T(n,m) = n! * Sum_{P(n,m)} Product_{p=1..n} f(p)^c_p / (c_p! * p!^c_p), where f(n) = A057500(n) =(n^(n-2)*(1-3*n)+exp(n)*Gamma(n+1,n)/n)/2, and P(n,m) are the partitions of n with m parts p, all p>=3: c_1 + 2*c_2 + ... + n*c_n = n; c_1,c_2, ..., c_n>= 0. - Washington Bomfim, May 03 2005, updated Apr 08 2020

T(n,1) = A057500(n), T(n,m) = Sum_{j=2..n-1} C(n-1,j) * A057500(j+1) * T(n-1-j,m-1) if m>1. - Alois P. Heinz, Sep 15 2008

EXAMPLE

a(30) = T[8,2] = 20307. The partitions of 8 with two parts p, p>=3 are [5*1 + 3*1], and [4*2].

Partition [5*1 + 3*1] corresponds to f(5)^1 * f(3)^1 / ( (1! * 5!^1) * (1! * 3!^1) ) = 222 /(5! * 3!) = 37/120; Partition [4*2] corresponds to f(4)^2 / ( 2! * 4!^2) = 225 / (2*4!^2) = 25/128. Finally 8! * (37/120 + 25/128) = 20307. (See formula).

Triangle T(n,m) begins:

          0;

          0,        0;

          1,        0,     0;

         15,        0,     0, 0;

        222,        0,     0, 0, 0;

       3660,       10,     0, 0, 0, 0;

      68295,      525,     0, 0, 0, 0, 0;

    1436568,    20307,     0, 0, 0, 0, 0, 0;

   33779340,   727020,   280, 0, 0, 0, 0, 0, 0;

  880107840, 25934184, 31500, 0, 0, 0, 0, 0, 0, 0;

MAPLE

cy:= proc(n) option remember; local t; binomial(n-1, 2) *add ((n-3)! /(n-2-t)! *n^(n-2-t), t=1..n-2) end: T:= proc(n, m) if m=1 then cy(n) else add (binomial(n-1, j) *cy(j+1) * T(n-1-j, m-1), j=2..n-1) fi end: seq (seq (T(n, m), m=1..n), n=1..11); # Alois P. Heinz, Sep 15 2008

# The function BellMatrix is defined in A264428.

# Adds (1, 0, 0, 0, ..) as column 0.

a := n -> n!*n^(n-1)/2*add(1/(n^k*(n-k)!), k=3..n);

BellMatrix(n -> a(n+1), 9); # Peter Luschny, Jan 27 2016

MATHEMATICA

nn=12; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; Range[0, nn]!CoefficientList[ Series[Exp[y(Log[1/(1-t)]/2-t/2-t^2/4)], {x, 0, nn}], {x, y}] //Grid  (* Geoffrey Critzer, Nov 04 2012 *)

BellMatrix[f_Function, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];

rows = 12;

M = BellMatrix[(#+1)! (#+1)^#/2 Sum[1/((#+1)^k (#-k+1)!), {k, 3, #+1}]&, rows];

Table[M[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-Fran├žois Alcover, Jun 24 2018, after Peter Luschny *)

PROG

(PARI) Row(n)={my(w=lambertw(-x+O(x*x^n))); Vecrev(n!*if(n>=3, polcoef(exp(-y*log(1+w)/2 + y*w/2 - y*w^2/4), n)/y), n)}

{for(n=1, 10, print(Row(n)))} \\ Andrew Howroyd, Apr 06 2020

(PARI) x = 90; D = Set(x); A = t = vector(x);

\p 500        \\ See Peter Luschny formula in A057500.

f = vector(x, n, round( (n^(n-2)*(1-3*n) + exp(n) * incgam(n+1, n) /n)/2) );

T(n, m)={my(p, c, S=0, Pr, cD, j); if(m>floor(n/3), return(0)); if(n>x, return(-1));

forpart(a = n, A = Vec(a); Pr = 1; D = Set(a); cD = #D;

for(j=1, cD, p= D[j]; t= select(x-> x==p, A); c=#t; Pr *= f[p]^c / (c!*p!^c));

S += Pr, [3, n], [m, m]); n! * S }; \\ - Washington Bomfim, Apr 07 2020

CROSSREFS

Cf. A057500, A106238 (similar formulas that can be used in the unlabeled case).

Sequence in context: A287285 A324677 A324675 * A271763 A271339 A202857

Adjacent sequences:  A106236 A106237 A106238 * A106240 A106241 A106242

KEYWORD

nonn,tabl

AUTHOR

Washington Bomfim, May 03 2005

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 August 8 14:02 EDT 2020. Contains 336298 sequences. (Running on oeis4.)