login
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
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
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 A362267 A271339
KEYWORD
nonn,tabl
AUTHOR
Washington Bomfim, May 03 2005
STATUS
approved