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.

A095133 Triangle of numbers of forests on n nodes containing k trees.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 2, 1, 1, 6, 6, 4, 2, 1, 1, 11, 11, 7, 4, 2, 1, 1, 23, 23, 14, 8, 4, 2, 1, 1, 47, 46, 29, 15, 8, 4, 2, 1, 1, 106, 99, 60, 32, 16, 8, 4, 2, 1, 1, 235, 216, 128, 66, 33, 16, 8, 4, 2, 1, 1, 551, 488, 284, 143, 69, 34, 16, 8, 4, 2, 1, 1, 1301, 1121, 636, 315, 149, 70, 34, 16, 8, 4, 2, 1, 1
Offset: 1

Views

Author

Eric W. Weisstein, May 29 2004

Keywords

Comments

Row sums are A005195.
For k > n/2, T(n,k) = T(n-1,k-1). - Geoffrey Critzer, Oct 13 2012

Examples

			Triangle begins:
    1;
    1,  1;
    1,  1,  1;
    2,  2,  1,  1;
    3,  3,  2,  1,  1;
    6,  6,  4,  2,  1, 1;
   11, 11,  7,  4,  2, 1, 1;
   23, 23, 14,  8,  4, 2, 1, 1;
   47, 46, 29, 15,  8, 4, 2, 1, 1;
  106, 99, 60, 32, 16, 8, 4, 2, 1, 1;
  ...

Links

Crossrefs

Cf. A005195 (row sums), A005196, A106240, A000055 (first column), A274937 (2nd column), A105821.
Limiting sequence of reversed rows gives A215930.
Reflected table is A136605. - Alois P. Heinz, Apr 11 2014

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:
t:= proc(n) option remember; local k; `if` (n=0, 1,
      b(n)-(add(b(k)*b(n-k), k=0..n)-`if`(irem(n, 2)=0, b(n/2), 0))/2)
    end:
g:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
      `if`(min(i, p)<1, 0, add(g(n-i*j, i-1, p-j) *
       binomial(t(i)+j-1, j), j=0..min(n/i, p)))))
    end:
a:= (n, k)-> g(n, n, k):
seq(seq(a(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Aug 20 2012
  • Mathematica
    nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);ft=Table[a[i]-Sum[a[j]a[i-j],{j,1,i/2}]+If[OddQ[i],0,a[i/2](a[i/2]+1)/2],{i,1,nn}];CoefficientList[Series[Product[1/(1-y x^i)^ft[[i]],{i,1,nn}],{x,0,20}],{x,y}]//Grid (* Geoffrey Critzer, Oct 13 2012, after code given by Robert A. Russell in A000055 *)

Formula

T(n, k) = sum over the partitions of n, 1M1 + 2M2 + ... + nMn, with exactly k parts, of Product_{i=1..n} binomial(A000055(i) + Mi - 1, Mi). - Washington Bomfim, May 12 2005

Extensions

More terms from Vladeta Jovovic, Jun 03 2004

A136605 Triangle read by rows: T(n,k) = number of forests on n unlabeled nodes with k edges (n>=1, 0<=k<=n-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 3, 1, 1, 2, 4, 6, 6, 1, 1, 2, 4, 7, 11, 11, 1, 1, 2, 4, 8, 14, 23, 23, 1, 1, 2, 4, 8, 15, 29, 46, 47, 1, 1, 2, 4, 8, 16, 32, 60, 99, 106, 1, 1, 2, 4, 8, 16, 33, 66, 128, 216, 235, 1, 1, 2, 4, 8, 16, 34, 69, 143, 284, 488, 551, 1, 1, 2, 4, 8, 16, 34, 70, 149, 315, 636, 1121, 1301
Offset: 1

Views

Author

N. J. A. Sloane, May 09 2008

Keywords

Examples

			Triangle begins:
1
1,1
1,1,1
1,1,2,2
1,1,2,3,3
1,1,2,4,6,6 <- T(6,3) = 4 forests on 6 nodes with 3 edges.
1,1,2,4,7,11,11
1,1,2,4,8,14,23,23
1,1,2,4,8,15,29,46,47
1,1,2,4,8,16,32,60,99,106
1,1,2,4,8,16,33,66,128,216,235
1,1,2,4,8,16,34,69,143,284,488,551
1,1,2,4,8,16,34,70,149,315,636,1121,1301
1,1,2,4,8,16,34,71,152,330,710,1467,2644,3159

References

  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.

Links

Crossrefs

Row sums give A005195. Rightmost diagonal gives A000055. Cf. A001858, A138464.
Rows converge to A215930. Reflected table is A095133. - Alois P. Heinz, Apr 11 2014

Programs

  • Maple
    with(numtheory):
b:= proc(n) option remember; `if`(n<=1, n, (add(add(
      d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1))
    end:
t:= n-> `if`(n=0, 1, b(n)-(add(b(k)*b(n-k), k=0..n)-
        `if`(irem(n, 2)=0, b(n/2), 0))/2):
g:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, expand(add(binomial(t(i)+j-1, j)*
       g(n-i*j, i-1)*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, n-i), i=0..n-1))(g(n$2)):
seq(T(n), n=1..14);  # Alois P. Heinz, Apr 11 2014
  • 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)]; t[n_] := If[n == 0, 1, b[n] - (Sum[b[k]*b[n-k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]; g[n_, i_] := g[n, i] = If[n == 0, 1, If[i < 1, 0, Expand[Sum[Binomial[t[i] + j - 1, j]*g[n - i*j, i-1]*x^j, {j, 0, n/i}]]]]; T[n_] := CoefficientList[g[n, n], x] // Reverse // Most; Table[T[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Apr 16 2014, after Alois P. Heinz *)

Formula

G.f.: Product_{k>=1} 1/(1 - y^(k-1)*x^k)^A000055(k). - Geoffrey Critzer, Nov 10 2014

A105821 Triangle of the numbers of different forests with one or more isolated vertices. Those forests have order N and m trees.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 2, 1, 1, 0, 3, 3, 2, 1, 1, 0, 6, 6, 4, 2, 1, 1, 0, 11, 11, 7, 4, 2, 1, 1, 0, 23, 23, 14, 8, 4, 2, 1, 1, 0, 47, 46, 29, 15, 8, 4, 2, 1, 1, 0, 106, 99, 60, 32, 16, 8, 4, 2, 1, 1, 0, 235, 216, 128, 66, 33, 16, 8, 4, 2, 1, 1, 0, 551, 488, 284, 143, 69, 34, 16, 8, 4, 2, 1, 1
Offset: 1

Views

Author

Washington Bomfim, Apr 25 2005

Keywords

Comments

The unique tree with an isolated node has order one. For N > 1 and m > 1 there is at least one partition of N in m parts, with a part equal to 1, so a(n) > 0, when m > 1 and a(n) = 0, when m = 1 and N > 1. A095133(n) = A105821(n) + A105820(n).
a(2*n+1,n+1) = A215930(n) for n>=0. - Alois P. Heinz, Jul 10 2013

Examples

			a(5,2) = 2 because 5 vertices can be partitioned in two trees only in one way: one tree gets 4 nodes and the other tree gets 1. Since A000055(4) = 2 and A000055(1) = 1, there are 2 forests. The forests of order less than or equal to 5 are depicted in the Weisstein "Forest" link.
1;
0, 1;
0, 1, 1;
0, 1, 1, 1;
0, 2, 2, 1, 1;
0, 3, 3, 2, 1, 1;
0, 6, 6, 4, 2, 1, 1;
0, 11, 11, 7, 4, 2, 1, 1;
0, 23, 23, 14, 8, 4, 2, 1, 1;
0, 47, 46, 29, 15, 8, 4, 2, 1, 1;
0, 106, 99, 60, 32, 16, 8, 4, 2, 1, 1;
0, 235, 216, 128, 66, 33, 16, 8, 4, 2, 1, 1;

Links

Crossrefs

Cf. A095133, A105820, A215930, row-reversed variant of A136605.

Formula

a(n) = sum over the partitions of N: 1K1 + 2K2 + ... + NKN, with exactly m parts and one or more parts equal to 1, of Product_{i=1..N} binomial(A000055(i)+Ki-1, Ki).
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.