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.

A309049 Number T(n,k) of (binary) max-heaps on n elements from the set {0,1} containing exactly k 0's; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 3, 4, 4, 2, 1, 1, 1, 4, 6, 6, 5, 2, 1, 1, 1, 4, 7, 8, 7, 5, 2, 1, 1, 1, 5, 10, 12, 11, 8, 5, 2, 1, 1, 1, 5, 11, 16, 17, 13, 9, 5, 2, 1, 1, 1, 6, 15, 23, 27, 24, 16, 10, 5, 2, 1, 1, 1, 6, 16, 27, 34, 34, 27, 18, 11, 5, 2, 1, 1
Offset: 0

Views

Author

Alois P. Heinz, Jul 09 2019

Keywords

Comments

Also the number T(n,k) of (binary) min-heaps on n elements from the set {0,1} containing exactly k 1's.
The sequence of column k satisfies a linear recurrence with constant coefficients of order A063915(k).

Examples

			T(6,0) = 1: 111111.
T(6,1) = 3: 111011, 111101, 111110.
T(6,2) = 4: 110110, 111001, 111010, 111100.
T(6,3) = 4: 101001, 110010, 110100, 111000.
T(6,4) = 2: 101000, 110000.
T(6,5) = 1: 100000.
T(6,6) = 1: 000000.
T(7,4) = T(7,7-3) = A000108(3) = 5: 1010001, 1010010, 1100100, 1101000, 1110000.
Triangle T(n,k) begins:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  1,  1;
  1, 2,  2,  1,  1;
  1, 3,  3,  2,  1,  1;
  1, 3,  4,  4,  2,  1,  1;
  1, 4,  6,  6,  5,  2,  1,  1;
  1, 4,  7,  8,  7,  5,  2,  1,  1;
  1, 5, 10, 12, 11,  8,  5,  2,  1, 1;
  1, 5, 11, 16, 17, 13,  9,  5,  2, 1, 1;
  1, 6, 15, 23, 27, 24, 16, 10,  5, 2, 1, 1;
  1, 6, 16, 27, 34, 34, 27, 18, 11, 5, 2, 1, 1;
  ...

Links

Crossrefs

Columns k=0-10 give: A000012, A110654, A114220 (for n>0), A326504, A326505, A326506, A326507, A326508, A326509, A326510, A326511.
Row sums give A091980(n+1).
T(2n,n) gives A309050.
Rows reversed converge to A000108.
Cf. A000225, A000295, A003095, A024358, A056971, A063915, A137560, A168542, A202019, A309051, A309052.

Programs

  • Maple
    b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
      x^n+b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n)):
seq(T(n), n=0..14);
  • Mathematica
    b[n_] := b[n] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f]*b[n - 1 - f]]][Min[g - 1, n - g/2]]][2^Floor[Log[2, n]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n]];
T /@ Range[0, 14] // Flatten (* Jean-François Alcover, Oct 04 2019, after Alois P. Heinz *)

Formula

Sum_{k=0..n} k * T(n,k) = A309051(n).
Sum_{k=0..n} (n-k) * T(n,k) = A309052(n).
Sum_{k=0..2^n-1} T(2^n-1,k) = A003095(n+1).
Sum_{k=0..2^n-1} (2^n-1-k) * T(2^n-1,k) = A024358(n).
Sum_{k=0..n} (T(n,k) - T(n-1,k)) = A168542(n).
T(m,m-n) = A000108(n) for m >= 2^n-1 = A000225(n).
T(2^n-1,k) = A202019(n+1,k+1).

A024358 Sum of the sizes of binary subtrees of the perfect binary tree of height n.

Original entry on oeis.org

0, 1, 8, 105, 6136, 8766473, 8245941529080, 3508518207951157937469961, 311594265746788494170062926869662848646207622648, 1217308491239906829392988008143949647398943617188660186130545502913055217344025410733271773705
Offset: 0

Views

Author

Cyril Banderier, Jun 09 2000

Keywords

Comments

Size of binary tree = number of internal nodes.

Links

Crossrefs

Cf. A003095, A309049, A309052.

Programs

  • Maple
    B:= proc(n) B(n):= `if`(n<0, 0, expand(1+x*B(n-1)^2)) end:
a:= n-> subs(x=1, diff(B(n), x)):
seq(a(n), n=0..9);  # Alois P. Heinz, Jul 12 2019
  • Mathematica
    B[n_] := If[n<0, 0, Expand[1+x*B[n-1]^2]];
a[n_] := D[B[n], x] /. x -> 1;
Table[a[n], {n, 0, 9}] (* Jean-François Alcover, Oct 13 2022, after Alois P. Heinz *)

Formula

a(n) = B'n(1) where B{n+1}(x) = 1 + x*B_n(x)^2.
From Alois P. Heinz, Jul 12 2019: (Start)
a(n) = Sum_{k=0..2^n-1} (2^n-1-k) * A309049(2^n-1,k).
a(n) = A309052(2^n-1). (End)

Extensions

a(0) changed to 0 by Alois P. Heinz, Jul 12 2019

A309051 Total number of 0's in all (binary) max-heaps on n elements from the set {0,1}.

Original entry on oeis.org

0, 1, 3, 7, 13, 24, 42, 77, 122, 206, 332, 578, 889, 1484, 2338, 4019, 5960, 9685, 14887, 25134, 37225, 60704, 92919, 156646, 227302, 364551, 550329, 917822, 1337358, 2158150, 3258779, 5441757, 7800755, 12412461, 18546566, 30708486, 44327782, 71090442
Offset: 0

Views

Author

Alois P. Heinz, Jul 09 2019

Keywords

Comments

Also the total number of 1's in all (binary) min-heaps on n elements from the set {0,1}.

Examples

			a(4) = 13 = 4+3+2+2+1+1+0, the total number of 0's in 0000, 1000, 1010, 1100, 1101, 1110, 1111.

Links

Crossrefs

Cf. A056971, A091980, A309049, A309052.

Programs

  • Maple
    b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
      x^n+b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
a:= n-> subs(x=1, diff(b(n), x)):
seq(a(n), n=0..40);
  • Mathematica
    b[n_][x_] := b[n][x] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f][x] b[n - 1 - f][x]]][Min[g - 1, n - g/2]]][2^(Length[IntegerDigits[ n, 2]] - 1)]];
a[n_] := b[n]'[1];
a /@ Range[0, 40] (* Jean-François Alcover, Apr 22 2021, after Alois P. Heinz *)

Formula

a(n) = Sum_{k=0..n} k * A309049(n,k).
a(n) = n * A091980(n+1) - A309052(n).
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.