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,2

Comments

Row sums are A001372.

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

Links

Table of n, a(n) for n=1..54.

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

Formula

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

Example

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.

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 *)

Crossrefs

Sequence in context: A076556 A324776 A325891 * A108426 A355267 A301305

Adjacent sequences: A217856 A217857 A217858 * A217860 A217861 A217862

Keyword

nonn,tabf

Author

Geoffrey Critzer, Oct 13 2012

Status

approved