A217756 Triangular array read by rows: T(n,k) is the number of simple labeled graphs on n nodes with exactly k components where each component has at most one cycle; n>=1, 1<=k<=n.

1, 1, 1, 4, 3, 1, 31, 19, 6, 1, 347, 195, 55, 10, 1, 4956, 2707, 720, 125, 15, 1, 85102, 46319, 12082, 2030, 245, 21, 1, 1698712, 930947, 242774, 40397, 4830, 434, 28, 1, 38562309, 21372678, 5620177, 938826, 112287, 10206, 714, 36, 1

Offset: 1

Author

Geoffrey Critzer, Mar 23 2013

Keywords

• nonn
• tabl

Comments

The Bell transform of A129271(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016

From Washington Bomfim, May 10 2020: (Start)

The second formula is based on Kolchin's formula (1.4.2) [see the Kolchin reference].

Some special cases of T(n,k) are

Column 2 = n! * Sum_{j=1..floor(n/2)} f(j)/j! * f(n-j)/(n-j)!, odd n.

n!/2 *( (f(n/2)/(n/2)!)^2 + 2 * Sum_{j=1..floor(n/2)-1} f(j)/j! * f(n-j)/(n-j)!), even n.

Diagonal T(n,n-3) = 1/48*n^6 +1/48*n^5 -13/48*n^4 -37/48*n^3 +13/4*n^2 -9/4*n,

Diagonal T(n,n-2) = 1/8*n^4 -1/12*n^3 -5/8*n^2 +7/12*n = A215862(n-2),

Diagonal T(n,n-1) = 1/2*n^2- 1/2*n = A000217(n-1),

and Diagonal T(n,n) = 1. (End)

Examples

			  ... o-o ........... o o ........... o o ..........
  ...     ........... |   ........... |\  ..........
  ... o-o ........... o-o ........... o-o ..........
T(4,2) = 19 because the above graphs on 4 nodes have 2 components with at most one cycle.  They have respectively 3 + 12 + 4 = 19 labelings.
1;
1,     1;
4,     3,     1;
31,    19,    6,     1;
347,   195,   55,    10,   1;
4956,  2707,  720,   125,  15,  1;
85102, 46319, 12082, 2030, 245, 21, 1;
		

References

• V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999, pp 30-31.

Crossrefs

Row sums = A133686.

Column 1 = A129271.

Cf. A144228, A000217, A215862.

Programs

Mathematica

nn=10;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];f[list_]:=Select[list,#>0&];Map[f,Drop[Range[0,nn]!CoefficientList[Series[Exp[y(t/2-3t^2/4)]/(1-t)^(y/2),{x,0,nn}],{x,y}],1]]//Grid

PARI

\p 1000  \\ See Peter Luschny formula in A129271.
f(p) = round(((p-1) * exp(p) * incgam(p-1,p) + p^(p-2) * (3-p)) /2);
T(n,k) = { my(S=0, D, p, c); forpart(a = n, D = Set(a);
   S += prod(j=1,#D, p=D[j]; c=#select(x-> x==p,Vec(a)); (f(p)/p!)^c /c!)
, [1, n], [k, k]); n! * S }; \\ Washington Bomfim, Jun 16 2020

Sage

# uses[bell_matrix from A264428]
# Adds a column 1,0,0,0, ... at the left side of the triangle.
bell_matrix(lambda n: A129271(n+1), 10) # Peter Luschny, Jan 18 2016

Formula

E.g.f.: exp(y*A(x)) where A(x) is the e.g.f. for A133686.

T(n,k) = n!/k! * Sum_{compositions p_1 + ... + p_k = n, p_i >= 1} Product_{j=1..k} f(p_j)/p_j!, where f(p)=A129271(p) = ((p-1)*e^p*GAMMA(p-1,p)+p^(p-2)*(3-p))/2.