A275462
Number of leaves in all simple labeled connected graphs on n nodes.
Original entry on oeis.org
0, 0, 2, 6, 48, 760, 21840, 1121568, 104510336, 18111498624, 5966666196480, 3794613745429760, 4704698796461841408, 11443317008255593064448, 54831540882238864189229056, 519046250316393184411087165440, 9726643425055315256306341282775040
Offset: 0
-
b:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*b(k), k=1..n-1)/n)
end:
a:= n-> n*(n-1)*b(n-1):
seq(a(n), n=0..20); # Alois P. Heinz, Jul 31 2016
-
nn = 15; Clear[f];f[z_] := Sum[2^Binomial[n, 2] z^n/n!, {n, 0, nn + 1}];Range[0, nn]! CoefficientList[Series[ z z D[Log[f[z]], z] , {z, 0, nn}], z]
A360603
Triangle read by rows. T(n, k) = A360604(n, k) * A001187(k) for 0 <= k <= n.
Original entry on oeis.org
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
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.
- F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.
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.
-
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);
-
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 *)
-
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]
Comments