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.
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
Examples
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;
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
Programs
-
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 *) -
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
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
Comments