cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

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.

Original entry on oeis.org

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
Offset: 0

Views

Author

Alois P. Heinz, Aug 25 2012

Keywords

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

Examples

			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;
  ...

Links

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.

Programs

  • 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 *)
  • Sage
    # uses[bell_matrix from A264428]
bell_matrix(lambda n: factorial(n)//2 + (n+1)^(n-1) if n>=2 else 1, 8) # Peter Luschny, Jan 21 2016

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.

A215978 Number of simple unlabeled graphs on n nodes with connected components that are trees or cycles.

Original entry on oeis.org

1, 1, 2, 4, 8, 14, 28, 52, 104, 206, 429, 903, 1982, 4430, 10206, 23966, 57522, 140236, 347302, 870682, 2207819, 5651437, 14590703, 37948338, 99358533, 261684141, 692906575, 1843601797, 4926919859, 13220064562, 35604359531, 96218568474, 260850911485
Offset: 0

Views

Author

Alois P. Heinz, Aug 29 2012

Keywords

Examples

			a(4) = 8:
.o-o.  .o-o.  .o-o.  .o-o.  .o-o.  .o-o.  .o-o.  .o o.
.| |.  .|  .  .|\ .  .|/ .  .|  .  .   .  .   .  .   .
.o-o.  .o-o.  .o o.  .o o.  .o o.  .o-o.  .o o.  .o o.

Links

Crossrefs

Row sum of A215977.
The labeled version is A144164. The inverse Euler transform is A215981.

Programs

  • Maple
    with(numtheory):
b:= proc(n) option remember; local d, j; `if`(n<=1, n,
      (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/(n-1))
    end:
g:= proc(n) option remember; local k; `if`(n>2, 1, 0)+ b(n)-
      (add(b(k)*b(n-k), k=0..n) -`if`(irem(n, 2)=0, b(n/2), 0))/2
    end:
p:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(g(i)+j-1,j)*p(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> p(n, n):
seq(a(n), n=0..40);
  • Mathematica
    b[n_] := b[n] = If[n <= 1, n, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}])/(n - 1)];
g[n_] := g[n] = If[n > 2, 1, 0] + b[n] - (Sum[b[k]*b[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2;
p[n_, i_] := p[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[g[i] + j - 1, j]*p[n - i*j, i - 1], {j, 0, n/i}]]];
a[n_] := p[n, n];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 21 2017, translated from Maple *)
  • Python
    from sympy.core.cache import cacheit
from sympy import binomial, divisors
@cacheit
def b(n): return n if n<2 else sum([sum([d*b(d) for d in divisors(j)])*b(n - j) for j in range(1, n)])//(n - 1)
@cacheit
def g(n): return (1 if n>2 else 0) + b(n) - (sum([b(k)*b(n - k) for k in range(n + 1)]) - (b(n//2) if n%2==0 else 0))//2
@cacheit
def p(n, i): return 1 if n==0 else 0 if i<1 else sum([binomial(g(i) + j - 1, j)*p(n - i*j, i - 1) for j in range(n//i + 1)])
def a(n): return p(n, n)
print([a(n) for n in range(41)]) # Indranil Ghosh, Aug 07 2017

Formula

a(n) = Sum_{k=0..n} A215977(n,k).
a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.95576528565199497471481752412... is Otter's rooted tree constant, and c = 1.085767435235426664262830616636... . - Vaclav Kotesovec, Mar 22 2017

A144163 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges where each maximally connected subgraph is either a tree or a cycle.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 3, 3, 1, 1, 6, 15, 20, 3, 1, 10, 45, 120, 150, 12, 1, 15, 105, 455, 1185, 1473, 70, 1, 21, 210, 1330, 5565, 14469, 18424, 465, 1, 28, 378, 3276, 19635, 81060, 213990, 280200, 3507, 1, 36, 630, 7140, 57393, 334656, 1385076, 3732300, 5029218, 30016
Offset: 0

Views

Author

Alois P. Heinz, Sep 12 2008

Keywords

Examples

			T(4,3) = 20, because there are 20 simple graphs on 4 labeled nodes with 3 edges, where each maximally connected subgraph is either a tree or a cycle, 16 of these graphs consist of a single tree with 4 nodes and 4 consist of a cycle with 3 and a tree with 1 node:
  .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. .1-2.
  .|/|. .|\|. ..X.. ..X|. ..X.. .|X.. ../|. .|\.. .|/.. ..\|.
  .4.3. .4.3. .4.3. .4.3. .4-3. .4.3. .4-3. .4-3. .4.3. .4.3.
Triangle begins:
  1;
  1,  0;
  1,  1,  0;
  1,  3,  3,   1;
  1,  6, 15,  20,   3;
  1, 10, 45, 120, 150, 12;

Links

Crossrefs

Columns k=0-3 give: A000012, A000217, A050534, A093566.
Main diagonal gives A001205.
Row sums give A144164.
Cf. A138464, A144161, A007318, A000142.

Programs

  • Maple
    f:= proc(n,k) option remember; local j; if k=0 then 1 elif k<0 or n<=k then 0 elif k=n-1 then n^(n-2) else add(binomial(n-1,j) *f(j+1,j) *f(n-1-j,k-j), j=0..k) fi end:
c:= proc(n,k) option remember; local i,j; if k=0 then 1 elif k<0 or n
  • Mathematica
    f[n_, k_] := f[n, k] = Which[k == 0, 1, k<0 || n <= k, 0, k == n-1, n^(n-2), True, Sum[Binomial[n-1, j]*f[j+1, j]*f[n-1-j, k-j], {j, 0, k}]]; c[n_, k_] := c[n, k] = Which[k == 0, 1 , k<0 || nJean-François Alcover, Jan 21 2014, translated from Alois P. Heinz's Maple code *)

Formula

T(n,k) = A138464(n,k) + Sum_{j=3..k} C(n,j) A138464(n-j,k-j) A144161 (j,j).
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.