A360603 Triangle read by rows. T(n, k) = A360604(n, k) * A001187(k) for 0 <= k <= n.

1, 0, 1, 0, 1, 1, 0, 2, 2, 4, 0, 8, 6, 12, 38, 0, 64, 32, 48, 152, 728, 0, 1024, 320, 320, 760, 3640, 26704, 0, 32768, 6144, 3840, 6080, 21840, 160224, 1866256, 0, 2097152, 229376, 86016, 85120, 203840, 1121568, 13063792, 251548592

Offset

0,8

References

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

Links

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

Algorithms for Competitive Programming, Counting labeled graphs, cp-algorithms.

Albert Nijenhuis and Herbert S Wilf, The enumeration of connected graphs and linked diagrams, Journal of Combinatorial Theory, Vol. 27(3), 1979, Pages 356-359.

Eric Weisstein's World of Mathematics, Connected Graph.

Eric Weisstein's World of Mathematics, Labeled Graph.

Formula

T(n, k) = 2^binomial(n-k, 2)*binomial(n-1, k-1) * A001187(k).

Recursion over the rows of the triangle: Set row(0) = [1] where [.] denotes a 0-based list. Assume now all rows(j) for j < n computed, next compute r = [2^binomial(n-k, 2) * binomial(n-1, k-1) * row(k)[k] for k = 1..n-1] and s = 2^(n*(n-1)/2) - Sum(r). Then row(n) = [0] & r & [s], where '&' denotes the concatenation of lists. (See the Python program for an implementation.)

T(n, n) = A001187(n) (connected labeled graphs).

T(n-1, n) = A053549(n-1) for n >= 1 (labeled rooted connected graphs).

T(n, 1) = Sum_{k>=0} T(n-1, k) = A006125(n-1) for n >= 1 (all labeled graphs).

Sum_{k=0..n-1} T(n, k) = A054592(n) for n >= 1 (disconnected labeled graphs).

See additional formulas in the cross-references.

Example

Triangle T(n, k) starts:
[0] 1;
[1] 0,       1;
[2] 0,       1,      1;
[3] 0,       2,      2,     4;
[4] 0,       8,      6,    12,    38;
[5] 0,      64,     32,    48,   152,    728;
[6] 0,    1024,    320,   320,   760,   3640,   26704;
[7] 0,   32768,   6144,  3840,  6080,  21840,  160224,  1866256;
[8] 0, 2097152, 229376, 86016, 85120, 203840, 1121568, 13063792, 251548592.

Maple

T := (n, k) -> 2^binomial(n-k, 2)*binomial(n-1, k-1)*A001187(k):
for n from 0 to 9 do seq(T(n, k), k = 0..n) od;
# Based on the recursion:
Trow := proc(n) option remember; if n = 0 then return [1] fi;
seq(2^binomial(n-k, 2) * binomial(n-1, k-1) * Trow(k)[k+1], k = 1..n-1);
2^(n*(n-1)/2) - add(j, j = [%]); [0, %%, %] end:
seq(print(Trow(n)), n = 0..8);

Mathematica

A001187[n_] := A001187[n] = 2^((n - 1)*n/2) - Sum[Binomial[n - 1, k]*2^((k - n + 1)*(k - n + 2)/2)*A001187[k + 1], {k, 0, n - 2}];
T[n_, k_] := 2^Binomial[n - k, 2]*Binomial[n - 1, k - 1]*A001187[k];
Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 02 2023, after Peter Luschny in A001187 *)

Prog

(Python)
from math import comb as binomial
from functools import cache
@cache
def A360603Row(n: int) -> list[int]:
    if n == 0: return [1]
    s = [2 ** (((k - n + 1) * (k - n)) // 2) * binomial(n - 1, k - 1) * A360603Row(k)[k] for k in range(1, n)]
    b = 2 ** (((n - 1) * n) // 2) - sum(s)
    return [0] + s + [b]

Crossrefs

Cf. A006125 Graphs on n labeled nodes, T(n+1, 1) and Sum_{k=0..n} T(n, k).

Cf. A054592 Disconnected labeled graphs with n nodes, Sum_{k=0..n-1} T(n, k).

Cf. A001187 Connected labeled graphs with n nodes, T(n, n).

Cf. A123903 Isolated nodes in all simple labeled graphs on n nodes, T(n+2, 2).

Cf. A053549 Labeled rooted connected graphs, T(n+1, n).

Cf. A275462 Leaves in all simple labeled connected graphs on n nodes T(n+2, n).

Cf. A060818 gcd_{k=0..n} T(n, k) = gcd(n!, 2^n).

Cf. A143543 Labeled graphs on n nodes with k connected components.

Cf. A095340 Total number of nodes in all labeled graphs on n nodes.

Cf. A360604, A360860 (accumulation triangle).

Sequence in context: A326127 A276151 A144412 * A337299 A240491 A113750

Adjacent sequences: A360600 A360601 A360602 * A360604 A360605 A360606

Keyword

nonn,tabl

Author

Peter Luschny, Feb 20 2023

Status

approved