A001853 -id:A001853 - cp's OEIS frontend

A316709 Bisection of the odd-indexed Pell numbers A001853: part 2.

5, 169, 5741, 195025, 6625109, 225058681, 7645370045, 259717522849, 8822750406821, 299713796309065, 10181446324101389, 345869461223138161, 11749380235262596085, 399133058537705128729, 13558774610046711780701, 460599203683050495415105, 15646814150613670132332869, 531531081917181734003902441, 18056409971033565286000350125

Offset: 0

Wolfdieter Lang, Jul 11 2018

The other part of this bisection is given in A316708.

Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (34,-1).

Cf. A000129, A001653, A029547, A316708.

x='x+O('x^99); Vec((5-x)/(1-34*x+x^2)) \\ Altug Alkan, Jul 11 2018

a(n) = Pell(4*n+3) = A000129(4*n+3) = A001653(2*(n+1)), n >= 0.
a(n) = 34*a(n-1) - a(n-2), with a(-1) =  and a(0) = 5.
a(n) = 5*S(n, 34) - S(n-1, 34), where the Chebyshev polynomial S(n, 34) = A029547(n), n >= 0, with S(-1, x) = 0.
G.f.: (5 - x)/(1- 34*x + x^2).

A034781 Triangle of number of rooted trees with n >= 2 nodes and height h >= 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 6, 8, 4, 1, 1, 10, 18, 13, 5, 1, 1, 14, 38, 36, 19, 6, 1, 1, 21, 76, 93, 61, 26, 7, 1, 1, 29, 147, 225, 180, 94, 34, 8, 1, 1, 41, 277, 528, 498, 308, 136, 43, 9, 1, 1, 55, 509, 1198, 1323, 941, 487, 188, 53, 10, 1

Offset: 2

N. J. A. Sloane

			Triangle begins:
  1;
  1  1;
  1  2  1;
  1  4  3  1;
  1  6  8  4  1;
  1 10 18 13  5  1;
  1 14 38 36 19  6 1;
thus there are 10 trees with 7 nodes and height 2.

Alois P. Heinz, Rows n = 2..142, flattened
Marko Riedel, Counting the number of rooted trees of a certain height
Marko Riedel, Maple code for sequence (OGF)
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
J. Riordan, The enumeration of trees by height and diameter, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Columns h=2-10 give: A000065, A000235, A000299, A000342, A000393, A000418, A000429, A126085, A245068.
T(2n,n) = A245102(n), T(2n+1,n) = A245103(n).
Row sums give A000081.
Cf. A001853, A227819, A375467.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1 or k<1, 0,
     add(binomial(b((i-1)$2, k-1)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
T:= (n, k)-> b((n-1)$2, k) -b((n-1)$2, k-1):
seq(seq(T(n, k), k=1..n-1), n=2..16);  # Alois P. Heinz, Jul 31 2013

Drop[Map[Select[#, # > 0 &] &,
   Transpose[
    Prepend[Table[
      f[n_] :=
       Nest[CoefficientList[
          Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x,
            0, 10}], x] &, {1}, n]; f[m] - f[m - 1], {m, 2, 10}],
Prepend[Table[1, {10}], 0]]]], 1] // Grid (* Geoffrey Critzer, Aug 01 2013 *)
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i<1 || k<1, 0, Sum[Binomial[b[i-1, i-1, k-1]+j-1, j]*b[n-i*j, i-1, k], {j, 0, n/i}]]]; T[n_, k_] := b[n-1, n-1, k]-b[n-1, n-1, k-1]; Table[T[n, k], {n, 2, 16}, {k, 1, n-1}] // Flatten (* Jean-François Alcover, Feb 11 2014, after Alois P. Heinz *)

def A034781(n, k): return A375467(n, k) - A375467(n, k - 1)
for n in range(2, 10): print([A034781(n, k) for k in range(2, n + 1)])
# Peter Luschny, Aug 30 2024

Reference gives recurrence.

T(n, k) = A375467(n, k) - A375467(n, k - 1). - Peter Luschny, Aug 30 2024

More terms from Victoria A Sapko (vsapko(AT)canes.gsw.edu), Sep 19 2003

A291336 Number F(n,h,t) of forests of t unlabeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 0, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 2, 1, 0, 4, 3, 1, 0, 3, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3, 3, 2, 1, 0, 6, 8, 3, 1, 0, 8, 4, 1, 0, 4, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3, 4, 3, 2, 1, 0, 10, 15, 9, 3, 1, 0, 18, 13, 4, 1, 0, 13, 5, 1, 0, 5, 1, 0, 1, 0

Offset: 0

Alois P. Heinz, Aug 22 2017

Elements in rows h=0 give A023531.
Positive elements in rows h=1 give A008284.
Positive row sums per layer (and - with a different offset - positive elements in column t=1) give A034781.
Positive column sums per layer give A033185.

			n h\t: 0 1 2 3 4 5 : A034781 : A033185   : A000081
-----+-------------+---------+-----------+--------
0 0  : 1           :         :           : 1
-----+-------------+---------+-----------+--------
1 0  : 0 1         :       1 : .         :
1 1  : 0           :         : 1         : 1
-----+-------------+---------+-----------+--------
2 0  : 0 0 1       :       1 : . .       :
2 1  : 0 1         :       1 : .         :
2 2  : 0           :         : 1 1       : 2
-----+-------------+---------+-----------+--------
3 0  : 0 0 0 1     :       1 : . . .     :
3 1  : 0 1 1       :       2 : . .       :
3 2  : 0 1         :       1 : .         :
3 3  : 0           :         : 2 1 1     : 4
-----+-------------+---------+-----------+--------
4 0  : 0 0 0 0 1   :       1 : . . . .   :
4 1  : 0 1 2 1     :       4 : . . .     :
4 2  : 0 2 1       :       3 : . .       :
4 3  : 0 1         :       1 : .         :
4 4  : 0           :         : 4 3 1 1   : 9
-----+-------------+---------+-----------+--------
5 0  : 0 0 0 0 0 1 :       1 : . . . . . :
5 1  : 0 1 2 2 1   :       6 : . . . .   :
5 2  : 0 4 3 1     :       8 : . . .     :
5 3  : 0 3 1       :       4 : . .       :
5 4  : 0 1         :       1 : .         :
5 5  : 0           :         : 9 6 3 1 1 : 20
-----+-------------+---------+-----------+--------

Alois P. Heinz, Layers n = 0..48, flattened

Cf. A000007, A000041, A000065, A000081, A001853, A005197, A008284, A023531, A033185, A034781, A291203, A291204, A291529.

b:= proc(n, i, t, h) option remember; expand(`if`(n=0 or h=0
       or i=1, x^(t*n), b(n, i-1, t, h)+add(x^(t*j)*binomial(
       b(i-1$2, 0, h-1)+j-1, j)*b(n-i*j, i-1, t, h), j=1..n/i)))
    end:
g:= (n, h)-> b(n$2, 1, h)-`if`(h=0, 0, b(n$2, 1, h-1)):
F:= (n, h, t)-> coeff(g(n, h), x, t):
seq(seq(seq(F(n, h, t), t=0..n-h), h=0..n), n=0..9);

b[n_, i_, t_, h_] := b[n, i, t, h] = Expand[If[n == 0 || h == 0
     || i == 1, x^(t*n), b[n, i-1, t, h] + Sum[x^(t*j)*Binomial[
     b[i-1, i-1, 0, h-1]+j-1, j]*b[n - i*j, i-1, t, h], {j, 1, n/i}]]];
g[n_, h_] := b[n, n, 1, h] - If[h == 0, 0, b[n, n, 1, h-1]];
F[n_, h_, t_] := Coefficient[g[n, h], x, t];
Table[Table[Table[F[n, h, t], {t, 0, n-h}], {h, 0, n}], {n, 0, 9}] //
Flatten (* Jean-François Alcover, Mar 10 2022, after Alois P. Heinz *)

Sum_{d=0..n} Sum_{i=0..d} F(n,i,d-i) = A000081(n+1).
Sum_{h=0..n} Sum_{t=0..n-h} t * F(n,h,t) = A005197(n).
Sum_{h=0..n} Sum_{t=0..n-h} (h+1) * F(n,h,t) = A001853(n+1) for n>0.
Sum_{t=0..n-1} F(n,1,t) = A000065(n) = A000041(n) - 1.
F(n,1,1) = 1 for n>1.
F(n,0,0) = A000007(n).

A291559 Total height of all (unlabeled) rooted identity trees with n vertices.

Original entry on oeis.org

0, 0, 1, 2, 5, 10, 23, 52, 120, 275, 644, 1508, 3558, 8418, 20012, 47699, 114082, 273476, 657250, 1582817, 3819514, 9233059, 22356918, 54216429, 131663670, 320158789, 779461271, 1899830067, 4635492672, 11321595218, 27677333555, 67720658475, 165835173692

Offset: 0

Alois P. Heinz, Aug 26 2017

nonn

			: a(5) = 10 = 4 + 3 + 3 : a(4) = 5 = 3 + 2 :
:                       :                  :
:    o    o      o      :    o    o        :
:    |    |     / \     :    |   / \       :
:    o    o    o   o    :    o  o   o      :
:    |   / \   |        :    |  |          :
:    o  o   o  o        :    o  o          :
:    |  |      |        :    |             :
:    o  o      o        :    o             :
:    |                  :                  :
:    o                  :                  :
:                       :                  :

Alois P. Heinz, Table of n, a(n) for n = 0..300

Cf. A001853, A004111, A291529.

b:= proc(n, i, t, h) option remember; expand(`if`(n=0 or h=0 or i=1,
      `if`(n<2, x^(t*n), 0), b(n, i-1, t, h)+add(x^(t*j)*binomial(
       b(i-1$2, 0, h-1), j)*b(n-i*j, i-1, t, h), j=1..n/i)))
    end:
g:= (n, h)-> b(n$2, 1, h)-`if`(h=0, 0, b(n$2, 1, h-1)):
F:= (n, h, t)-> coeff(g(n, h), x, t):
a:= n-> add(add((h+1)*F(n-1, h, t), t=1..n-1-h), h=0..n-2):
seq(a(n), n=0..37);

b[n_, i_, t_, h_] := b[n, i, t, h] = Expand[If[n == 0 || h == 0 || i == 1,
   If[n < 2, x^(t*n), 0], b[n, i-1, t, h] + Sum[x^(t*j)*Binomial[
   b[i-1, i-1, 0, h-1], j]*b[n-i*j, i-1, t, h], {j, 1, n/i}]]];
g[n_, h_] := b[n, n, 1, h] - If[h == 0, 0, b[n, n, 1, h-1]];
F[n_, h_, t_] := Coefficient[g[n, h], x, t];
a[n_] := Sum[Sum[(h+1)*F[n-1, h, t], {t, 1, n-1-h}], {h, 0, n-2}];
Table[a[n], {n, 0, 37}] (* Jean-François Alcover, Dec 08 2023, after Alois P. Heinz *)

a(n) = Sum_{h=0..n-2} Sum_{t=1..n-1-h} (h+1) * A291529(n-1,h,t).

cp's OEIS Frontend

A316709 Bisection of the odd-indexed Pell numbers A001853: part 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A034781 Triangle of number of rooted trees with n >= 2 nodes and height h >= 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A291336 Number F(n,h,t) of forests of t unlabeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A291559 Total height of all (unlabeled) rooted identity trees with n vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula