A143543 Triangle read by rows: T(n,k) = number of labeled graphs on n nodes with k connected components, 1<=k<=n.

1, 1, 1, 4, 3, 1, 38, 19, 6, 1, 728, 230, 55, 10, 1, 26704, 5098, 825, 125, 15, 1, 1866256, 207536, 20818, 2275, 245, 21, 1, 251548592, 15891372, 925036, 64673, 5320, 434, 28, 1, 66296291072, 2343580752, 76321756, 3102204, 169113, 11088, 714, 36, 1

Offset

1,4

Comments

The Bell transform of A001187(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 17 2016

Links

Alois P. Heinz, Rows n = 1..82, flattened (first 25 rows from Marko Riedel)

Marko Riedel, Maple implementation of memoized recurrence.

Marko Riedel et al., Proof of recurrence relation.

Formula

SUM[n,k=0..oo] T(n,k) * x^n * y^k / n! = exp( y*( F(x) - 1 ) ) = ( SUM[n=0..oo] 2^binomial(n, 2)*x^n/n! )^y, where F(x) is e.g.f. of A001187.

T(n,k) = Sum_{q=0..n-1} C(n-1, q) T(q, k-1) 2^C(n-q,2) - Sum_{q=0..n-2} C(n-1, q) T(q+1, k) 2^C(n-1-q, 2) where T(0,0) = 1 and T(0,k) = 0 and T(n,0) = 0. - Marko Riedel, Feb 04 2019

Sum_{k=1..n} k * T(n,k) = A125207(n) - Alois P. Heinz, Feb 02 2024

Example

The triangle T(n,k) starts as:
n=1:     1;
n=2:     1,    1;
n=3:     4,    3,   1;
n=4:    38,   19,   6,   1;
n=5:   728,  230,  55,  10,  1;
n=6: 26704, 5098, 825, 125, 15, 1;
...

Maple

g:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-add(
      binomial(n, k)*2^((n-k)*(n-k-1)/2)*g(k)*k, k=1..n-1)/n)
    end:
b:= proc(n) option remember; `if`(n=0, 1, add(expand(
      b(n-j)*binomial(n-1, j-1)*g(j)*x), j=1..n))
    end:
T:= (n, k)-> coeff(b(n$2), x, k):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Feb 02 2024

Mathematica

a= Sum[2^Binomial[n, 2] x^n/n!, {n, 0, 10}];
Rest[Transpose[Table[Range[0, 10]! CoefficientList[Series[Log[a]^n/n!, {x, 0, 10}], x], {n, 1, 10}]]] // Grid (* Geoffrey Critzer, Mar 15 2011 *)

Prog

(Sage) # uses[bell_matrix from A264428, A001187]
# Adds a column 1, 0, 0, 0, ... at the left side of the triangle.
bell_matrix(lambda n: A001187(n+1), 9) # Peter Luschny, Jan 17 2016

Crossrefs

Cf. A001187 (first column), A006125 (row sums), A106240 (unlabeled variant).

Cf. A125207.

T(2n,n) gives A369827.

Sequence in context: A203412 A217756 A154960 * A176863 A349989 A067017

Adjacent sequences: A143540 A143541 A143542 * A143544 A143545 A143546

Keyword

nonn,tabl

Author

Max Alekseyev, Aug 23 2008

Status

approved