cp's OEIS Frontend

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.

%I A217756 #26 Jul 02 2020 15:47:41
%S A217756 1,1,1,4,3,1,31,19,6,1,347,195,55,10,1,4956,2707,720,125,15,1,85102,
%T A217756 46319,12082,2030,245,21,1,1698712,930947,242774,40397,4830,434,28,1,
%U A217756 38562309,21372678,5620177,938826,112287,10206,714,36,1
%N 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.
%C A217756 The Bell transform of A129271(n+1). For the definition of the Bell transform see A264428. - _Peter Luschny_, Jan 18 2016
%C A217756 From _Washington Bomfim_, May 10 2020: (Start)
%C A217756 The second formula is based on Kolchin's formula (1.4.2) [see the Kolchin reference].
%C A217756 Some special cases of T(n,k) are
%C A217756 Column 2 = n! * Sum_{j=1..floor(n/2)} f(j)/j! * f(n-j)/(n-j)!, odd n.
%C A217756            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.
%C A217756 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,
%C A217756 Diagonal T(n,n-2) = 1/8*n^4 -1/12*n^3 -5/8*n^2 +7/12*n = A215862(n-2),
%C A217756 Diagonal T(n,n-1) = 1/2*n^2- 1/2*n = A000217(n-1),
%C A217756 and Diagonal T(n,n) = 1. (End)
%D A217756 V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999, pp 30-31.
%F A217756 E.g.f.: exp(y*A(x)) where A(x) is the e.g.f. for A133686.
%F A217756 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.
%e A217756   ... o-o ........... o o ........... o o ..........
%e A217756   ...     ........... |   ........... |\  ..........
%e A217756   ... o-o ........... o-o ........... o-o ..........
%e A217756 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.
%e A217756 1;
%e A217756 1,     1;
%e A217756 4,     3,     1;
%e A217756 31,    19,    6,     1;
%e A217756 347,   195,   55,    10,   1;
%e A217756 4956,  2707,  720,   125,  15,  1;
%e A217756 85102, 46319, 12082, 2030, 245, 21, 1;
%t A217756 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
%o A217756 (Sage) # uses[bell_matrix from A264428]
%o A217756 # Adds a column 1,0,0,0, ... at the left side of the triangle.
%o A217756 bell_matrix(lambda n: A129271(n+1), 10) # _Peter Luschny_, Jan 18 2016
%o A217756 (PARI)
%o A217756 \p 1000  \\ See Peter Luschny formula in A129271.
%o A217756 f(p) = round(((p-1) * exp(p) * incgam(p-1,p) + p^(p-2) * (3-p)) /2);
%o A217756 T(n,k) = { my(S=0, D, p, c); forpart(a = n, D = Set(a);
%o A217756    S += prod(j=1,#D, p=D[j]; c=#select(x-> x==p,Vec(a)); (f(p)/p!)^c /c!)
%o A217756 , [1, n], [k, k]); n! * S }; \\ _Washington Bomfim_, Jun 16 2020
%Y A217756 Row sums = A133686.
%Y A217756 Column 1 = A129271.
%Y A217756 Cf. A144228, A000217, A215862.
%K A217756 nonn,tabl
%O A217756 1,4
%A A217756 _Geoffrey Critzer_, Mar 23 2013