A182223 Triangular array read by rows. T(n,k) is the number of simple unlabeled graphs with n nodes having exactly k distinct components.

1, 1, 2, 3, 1, 8, 3, 22, 12, 117, 37, 2, 854, 182, 8, 11140, 1163, 43, 261085, 13365, 218, 11716804, 286878, 1474, 12, 1006700566, 12281795, 15449, 54, 164059836867, 1031025763, 309546, 416, 50335907869220, 166110822083, 12673543, 3106, 29003487463212294, 50667148427178, 1045561143, 34873, 31397381142761243738, 29104659809891176, 167232513148, 660454, 252

Offset

0,3

Comments

These graphs may contain identical components but they have a total of k different "types". Cf. A207828.

Row sums = A000088.

Links

Table of n, a(n) for n=0..45.

Formula

O.g.f.: Product_{n>=1}: y/(1-x^n)^A001349(n) - y + 1, where A001349 is the number of connected graphs.

Example

1
1
2
3     1
8     3
22    12
117   37    2
854   182   8
T(4,1) = 8 because we have 6 connected graphs and *-* *-*, and * * * * .

Mathematica

nn = 15; c = (A000088 = Table[NumberOfGraphs[n], {n, 0, nn}]; f[x_] = 1 - Product[1/(1 - x^k)^a[k], {k, 1, nn}]; a[0] = a[1] = a[2] = 1; coes = CoefficientList[Series[f[x], {x, 0, nn}], x]; sol = First[Solve[Thread[Rest[coes + A000088] == 0]]]; Table[a[n], {n, 0, nn}] /. sol); f[list_] := Select[list, # > 0 &]; g = Product[y/(1 - x^n)^c[[n + 1]] - y + 1, {n, 1, nn}]; Map[f, CoefficientList[Series[g, {x, 0, nn}], {x, y}]] // Flatten (* Mma code for c in the above is given by Jean-Francois Alcover in A001349 *)

Crossrefs

Sequence in context: A266614 A175314 A331123 * A011152 A078298 A096063

Adjacent sequences: A182220 A182221 A182222 * A182224 A182225 A182226

Keyword

nonn,tabf

Author

Geoffrey Critzer, Apr 19 2012

Status

approved