A217859 Triangular array read by rows. T(n,k) is the number of functions on n unlabeled nodes that have exactly k unique components (n >= 1, k >= 1).

1, 3, 5, 2, 12, 7, 21, 25, 1, 58, 63, 9, 126, 178, 39, 341, 466, 140, 4, 867, 1253, 470, 25, 2334, 3418, 1431, 135, 6218, 9365, 4358, 544, 6, 17016, 25924, 12871, 2042, 50, 46351, 72207, 37993, 7056, 291, 127842, 202345, 111142, 23483, 1383, 4, 353297, 568822, 325359, 75701, 5754, 60

Offset: 1

Author

Geoffrey Critzer, Oct 13 2012

Keywords

• nonn
• tabf

Comments

Row sums are A001372.

T(n,1) = A002861(n) + 1 when n is prime (counts connected functions and the identity function).

Examples

			Triangle begins:
       1;
       3,
       5,      2;
      12,      7;
      21,     25,      1;
      58,     63,      9;
     126,    178,     39;
     341,    466,    140,     4;
     867,   1253,    470,    25;
    2334,   3418,   1431,   135;
    6218,   9365,   4358,   544,    6;
   17016,  25924,  12871,  2042,   50;
   46351,  72207,  37993,  7056,  291;
  127842, 202345, 111142, 23483, 1383,  4;
  353297, 568822, 325359, 75701, 5754, 60;
T(3,2)=2 because (in the link) the third and the fifth digraphs on 3 nodes are composed of 2 unique components.
		

Links

• N. J. A. Sloane, Illustration of initial terms

Programs

Mathematica

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2 k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i] s[n-1,i] i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];c=Drop[Apply[Plus,Table[Take[CoefficientList[CycleIndex[CyclicGroup[n],s]/.Table[s[j]->Table[Sum[rt[[i]] x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],{n,1,30}]],1];CoefficientList[Series[Product[((y x^i +1-x^i)/(1-x^i))^c[[i]],{i,1,nn-1}],{x,0,15}],{x,y}]//Grid
(* after code given by Robert A. Russell in A000081 *)

Formula

O.g.f.: Product_{n>=1} ((y*x^n - x^n + 1)/(1 - x^n))^A002861(n).