login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A215861 Number T(n,k) of simple labeled graphs on n nodes with exactly k connected components that are trees or cycles; triangle T(n,k), n>=0, 0<=k<=n, read by rows. 18
1, 0, 1, 0, 1, 1, 0, 4, 3, 1, 0, 19, 19, 6, 1, 0, 137, 135, 55, 10, 1, 0, 1356, 1267, 540, 125, 15, 1, 0, 17167, 15029, 6412, 1610, 245, 21, 1, 0, 264664, 218627, 90734, 23597, 3990, 434, 28, 1, 0, 4803129, 3783582, 1515097, 394506, 70707, 8694, 714, 36, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,8

COMMENTS

Also the Bell transform of A215851(n+1). For the definition of the Bell transform see A264428 and the links given there. - Peter Luschny, Jan 21 2016

LINKS

Alois P. Heinz, Rows n = 0..140, flattened

FORMULA

T(0,0) = 1, T(n,k) = 0 for k<0 or k>n, and otherwise T(n,k) = Sum_{i=0..n-k} C(n-1,i)*T(n-1-i,k-1)*h(i) with h(i) = 1 for i<2 and h(i) = i!/2 + (i+1)^(i-1) else.

EXAMPLE

T(4,2) = 19:

  .1 2.  .1 2.  .1-2.  .1-2.  .1 2.  .1 2.  .1 2.  .1 2.  .1 2.  .1 2.

  . /|.  .|\ .  .|/ .  . \|.  . /|.  .  |.  . / .  .|\ .  . \ .  .|  .

  .4-3.  .4-3.  .4 3.  .4 3.  .4 3.  .4-3.  .4-3.  .4 3.  .4-3.  .4-3.

  .

  .1-2.  .1-2.  .1 2.  .1-2.  .1-2.  .1 2.  .1-2.  .1 2.  .1 2.

  .|  .  . / .  .|/ .  . \ .  .  |.  . \|.  .   .  .| |.  . X .

  .4 3.  .4 3.  .4 3.  .4 3.  .4 3.  .4 3.  .4-3.  .4 3.  .4 3.

Triangle T(n,k) begins:

  1;

  0,     1;

  0,     1,     1;

  0,     4,     3,    1;

  0,    19,    19,    6,    1;

  0,   137,   135,   55,   10,   1;

  0,  1356,  1267,  540,  125,  15,   1;

  0, 17167, 15029, 6412, 1610, 245,  21,  1;

MAPLE

T:= proc(n, k) option remember; `if`(k<0 or k>n, 0,

      `if`(n=0, 1, add(binomial(n-1, i)*T(n-1-i, k-1)*

      `if`(i<2, 1, i!/2 +(i+1)^(i-1)), i=0..n-k)))

    end:

seq(seq(T(n, k), k=0..n), n=0..12);

# Alternatively, with the function BellMatrix defined in A264428:

BellMatrix(n -> `if`(n<2, 1, n!/2+(n+1)^(n-1)), 8); # Peter Luschny, Jan 21 2016

MATHEMATICA

t[0, 0] = 1; t[n_, k_] /; k < 0 || k > n = 0; t[n_, k_] := t[n, k] =Sum[ Binomial[n-1, i]*t[n-1-i, k-1]* If[i < 2, 1, i!/2 + (i+1)^(i-1)], {i, 0, n-k}]; Table[t[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 07 2013 *)

(* Alternatively, with the function BellMatrix defined in A264428: *)

g[n_] =  If[n < 2, 1, n!/2 + (n+1)^(n-1)]; BellMatrix[g, 8] (* Peter Luschny, Jan 21 2016 *)

rows = 11;

t = Table[If[n<2, 1, n!/2 + (n+1)^(n-1)], {n, 0, rows}];

T[n_, k_] := BellY[n, k, t];

Table[T[n, k], {n, 0, rows}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 22 2018, after Peter Luschny *)

PROG

(Sage)

# The function bell_matrix is defined in A264428.

bell_matrix(lambda n: factorial(n)//2 + (n+1)^(n-1) if n>=2 else 1, 8) # Peter Luschny, Jan 21 2016

CROSSREFS

Columns k=0-10 give: A000007, A215851, A215852, A215853, A215854, A215855, A215856, A215857, A215858, A215859, A215860.

Diagonal and lower diagonals give: A000012, A000217, A215862, A215863, A215864, A215865.

Row sums give: A144164.

T(2n,n) gives A309313.

Sequence in context: A117026 A316656 A083904 * A327366 A327069 A327334

Adjacent sequences:  A215858 A215859 A215860 * A215862 A215863 A215864

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Aug 25 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 24 04:30 EST 2020. Contains 332197 sequences. (Running on oeis4.)