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.

A056971 Number of (binary) heaps on n elements.

Original entry on oeis.org

1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, 3143467008000, 25540669440000, 299677188096000, 2261626278912000, 25732281217843200, 241240136417280000
Offset: 0

Views

Author

Eric W. Weisstein

Keywords

Comments

A sequence {a_i}{i=1..N} forms a (binary) heap if it satisfies a_i<a{2i} and a_i
Proof of recurrence: a_1 must take the greatest of the n values. Deleting a_1 gives 2 heaps of size b+r1, b+r2. - Sascha Kurz, Mar 24 2002
Note that A132862(n)*a(n) = n!. - Alois P. Heinz, Nov 22 2007

Examples

			There is 1 heap if n is in {0,1,2}, 2 heaps for n=3, 3 heaps for n=4 and so on.
a(5) = 8 (min-heaps): 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254.

Links

Crossrefs

Cf. A053644, A056972, A132862, A373452 (allows repeated elements).
Column k=2 of A273693.
Column k=0 of A306343 and of A306393.
Main diagonal of A373451.

Programs

  • Maple
    a[0] := 1: a[1] := 1:
for n from 2 to 50 do
h := ilog2(n+1)-1:
b := 2^h-1: r := n-1-2*b: r1 := r-floor(r/2^h)*(r-2^h): r2 := r-r1:
a[n] := binomial(n-1, b+r1)*a[b+r1]*a[b+r2]:end do:
q := seq(a[j], j=0..50);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> a(f)*
      binomial(n-1, f)*a(n-1-f))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
seq(a(n), n=0..28);  # Alois P. Heinz, Feb 14 2019
  • Mathematica
    a[0] = 1; a[1] = 1; For[n = 2, n <= 50, n++, h = Floor[Log[2, n + 1]] - 1; b = 2^h - 1; r = n - 1 - 2*b; r1 = r - Floor[r/2^h]*(r - 2^h); r2 = r - r1; a[n] = Binomial[n - 1, b + r1]*a[b + r1]*a[b + r2]]; Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Oct 22 2012, translated from Maple program *)
  • Python
    from functools import lru_cache
from math import comb
@lru_cache(maxsize=None)
def A056971(n):
    if n<=1: return 1
    h = (n+1).bit_length()-2
    b = (1<A056971(b+r1)*A056971(b+r2) # Chai Wah Wu, May 06 2024

Formula

See recurrence in Maple and Mma programs.

Extensions

More terms from Sascha Kurz, Mar 24 2002
Offset and some terms corrected by Alois P. Heinz, Nov 21 2007

A373451 Number T(n,k) of (binary) heaps of length n whose element set equals [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 5, 7, 3, 0, 1, 9, 23, 23, 8, 0, 1, 14, 55, 92, 70, 20, 0, 1, 24, 147, 386, 502, 320, 80, 0, 1, 34, 281, 1004, 1861, 1880, 985, 210, 0, 1, 54, 633, 3128, 8113, 12008, 10237, 4690, 896, 0, 1, 79, 1241, 8039, 27456, 54900, 66730, 48650, 19600, 3360
Offset: 0

Views

Author

Alois P. Heinz, Jun 05 2024

Keywords

Comments

These heaps may contain repeated elements. Their element sets are gap-free and contain 1 (if nonempty).
T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k<=n. T(n,k) = 0 for k>n.

Examples

			T(4,1) = 1: 1111.
T(4,2) = 5: 2111, 2121, 2211, 2212, 2221.
T(4,3) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321.
T(4,4) = 3: 4231, 4312, 4321.
(The examples use max-heaps.)
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,  1;
  0, 1,  3,   2;
  0, 1,  5,   7,    3;
  0, 1,  9,  23,   23,    8;
  0, 1, 14,  55,   92,   70,    20;
  0, 1, 24, 147,  386,  502,   320,    80;
  0, 1, 34, 281, 1004, 1861,  1880,   985,  210;
  0, 1, 54, 633, 3128, 8113, 12008, 10237, 4690, 896;
  ...

Links

Crossrefs

Columns k=0-4 give A000007, A057427, A091980(n+1)-2, A376962, A376963.
Row sums give A373452.
Row maxima give A373608.
Main diagonal gives A056971.
First lower diagonal gives A373496.
T(2n,n) gives A373500.
Antidiagonal sums give A373632.
Antidiagonal maxima give A373897.
Cf. A019590, A373449.

Programs

  • Maple
    b:= proc(n, k) option remember; `if`(n=0, 1,
     (g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)
             )(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
T:= (n, k)-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k):
seq(seq(T(n, k), k=0..n), n=0..12);
  • Mathematica
    b[n_, k_] := b[n, k] = If[n == 0, 1,
   Function[g, Function[f, Sum[b[f, j]*b[n-1-f, j], {j, 1, k}]][
      Min[g-1, n-g/2]]][2^(Length@IntegerDigits[n, 2]-1)]];
T[n_, k_] := Sum[Binomial[k, j]*(-1)^j*b[n, k-j], {j, 0, k}];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Sep 20 2024, after Alois P. Heinz *)

Formula

T(n,k) = Sum_{j=0..k} binomial(k,j) * (-1)^j * A373449(n,k-j).
Sum_{k=0..n} (-1)^k * T(n,n-k) = A019590(n+1).

A373450 Number of (binary) heaps of length n whose element set is a subset of [n].

Original entry on oeis.org

1, 1, 3, 14, 65, 448, 3136, 32028, 251922, 2891801, 30684797, 464651863, 5434037232, 92246217970, 1379368317328, 29135744093948, 414052904722966, 8546218817446727, 152935671938144301, 3857215760145872627, 70913916905782150177, 1881992311219764068420
Offset: 0

Views

Author

Alois P. Heinz, Jun 05 2024

Keywords

Comments

These heaps may contain repeated elements.

Examples

			a(0) = 1: the empty heap.
a(1) = 1: 1.
a(2) = 3: 11, 21, 22.
a(3) = 14: 111, 211, 212, 221, 222, 311, 312, 313, 321, 322, 323, 331, 332, 333.
(The examples use max-heaps.)

Links

Crossrefs

Main diagonal of A373449.
Cf. A056971 (distinct elements), A373452 (gap-free element sets including 1).
Cf. A007318, A373451.

Programs

  • Maple
    b:= proc(n, k) option remember; `if`(n=0, 1,
     (g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)
             )(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..21);

Formula

a(n) = A373449(n,n).
a(n) = Sum_{k=0..n} binomial(n,k)*A373451(n,k).
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.