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
Examples
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.
References
- F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.
Links
- 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.
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.
Programs
-
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 *)
-
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]
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.