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-10 of 11 results. Next

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

A373452 Number of (binary) heaps of length n whose element set equals [k] (for some k <= n).

Original entry on oeis.org

1, 1, 2, 6, 16, 64, 252, 1460, 6256, 39760, 230056, 1920152, 12154416, 113087888, 916563592, 10586707896, 80444848064, 898922718272, 8634371968224, 117894609062176, 1160052513737280, 16638593775310528, 200744153681516384, 3415784055462112160, 38542918215425934624
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).

Examples

			a(0) = 1: the empty heap.
a(1) = 1: 1.
a(2) = 2: 11, 21.
a(3) = 6: 111, 211, 212, 221, 312, 321.
a(4) = 16: 1111, 2111, 2121, 2211, 2212, 2221, 3121, 3211, 3212, 3221, 3231, 3312, 3321, 4231, 4312, 4321.
(The examples use max-heaps.)

Links

Crossrefs

Row sums of A373451.
Cf. A000670, A056971 (distinct elements), A373450.

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-> add(add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k), k=0..n):
seq(a(n), n=0..24);
  • 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}];
a[n_] := Sum[T[n, k], {k, 0, n}];
Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Sep 24 2024, after Alois P. Heinz *)

A373449 Number A(n,k) of (binary) heaps of length n whose element set is a subset of [k]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 5, 1, 0, 1, 5, 10, 14, 7, 1, 0, 1, 6, 15, 30, 25, 11, 1, 0, 1, 7, 21, 55, 65, 53, 16, 1, 0, 1, 8, 28, 91, 140, 173, 100, 26, 1, 0, 1, 9, 36, 140, 266, 448, 400, 222, 36, 1, 0, 1, 10, 45, 204, 462, 994, 1225, 1122, 386, 56, 1, 0
Offset: 0

Views

Author

Alois P. Heinz, Jun 05 2024

Keywords

Comments

These heaps may contain repeated elements.

Examples

			A(3,1) = 1: 111.
A(3,2) = 5: 111, 211, 212, 221, 222.
A(3,3) = 14: 111, 211, 212, 221, 222, 311, 312, 313, 321, 322, 323, 331, 332, 333.
(The examples use max-heaps.)
Square array A(n,k) begins:
  1, 1,  1,   1,    1,     1,     1,     1,      1, ...
  0, 1,  2,   3,    4,     5,     6,     7,      8, ...
  0, 1,  3,   6,   10,    15,    21,    28,     36, ...
  0, 1,  5,  14,   30,    55,    91,   140,    204, ...
  0, 1,  7,  25,   65,   140,   266,   462,    750, ...
  0, 1, 11,  53,  173,   448,   994,  1974,   3606, ...
  0, 1, 16, 100,  400,  1225,  3136,  7056,  14400, ...
  0, 1, 26, 222, 1122,  4147, 12428, 32028,  73644, ...
  0, 1, 36, 386, 2336, 10036, 34242, 98922, 251922, ...

Links

Crossrefs

Columns k=0-2 give: A000007, A000012, A091980(n+1).
Rows n=0-6 give: A000012, A001477, A000217, A000330, A001296, A207361, A001249(k-1).
Main diagonal gives A373450.
Cf. A373451.

Programs

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

Formula

A(n,k) = Sum_{j=0..k} binomial(k,j) * A373451(n,k-j).

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

A373632 Number of (binary) heaps where n is the sum of their length and the size of the element set [k].

Original entry on oeis.org

1, 0, 1, 1, 2, 4, 8, 17, 41, 103, 282, 792, 2239, 6680, 21143, 70647, 245357, 871255, 3202552, 12334046, 49635128, 205403510, 856780528, 3601169551, 15507530896, 69267381313, 320345619798, 1518428936730, 7345400773513, 36469929240960, 186875135258481
Offset: 0

Views

Author

Alois P. Heinz, Jun 11 2024

Keywords

Comments

These heaps may contain repeated elements. Their element sets are gap-free and contain 1 (if nonempty).

Examples

			a(0) = 1: the empty heap.
a(2) = 1: 1.
a(3) = 1: 11.
a(4) = 2: 111, 21.
a(5) = 4: 1111, 211, 212, 221.
a(6) = 8: 11111, 2111, 2121, 2211, 2212, 2221, 312, 321.
a(7) = 17: 111111, 21111, 21211, 22111, 22112, 22121, 22122, 22211, 22212, 22221, 3121, 3211, 3212, 3221, 3231, 3312, 3321.
(The examples use max-heaps.)

Links

Crossrefs

Antidiagonal sums of 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:
T:= (n, k)-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k):
a:= n-> add(T(n-j, j), j=0..n/2):
seq(a(n), n=0..30);

Formula

a(n) = Sum_{j=0..floor(n/2)} A373451(n-j,j).

A373496 Number of (binary) heaps with element set [n] and length n+1.

Original entry on oeis.org

0, 1, 3, 7, 23, 70, 320, 985, 4690, 19600, 121920, 549600, 3775200, 21964800, 186700800, 983954400, 7898290400, 53301248000, 523712716800, 3600440064000, 37065077913600, 315001589760000, 3848127528960000, 30288467049984000, 357688760600371200, 3481899302289408000
Offset: 0

Views

Author

Alois P. Heinz, Jun 06 2024

Keywords

Comments

These heaps contain exactly one repeated element.

Examples

			a(1) = 1: 11.
a(2) = 3: 211, 212, 221.
a(3) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321.
a(4) = 23: 42311, 42312, 42321, 43112, 43121, 43122, 43123, 43132, 43211, 43212, 43213, 43221, 43231, 43312, 43321, 43412, 43421, 44123, 44132, 44213, 44231, 44312, 44321.
(The examples use max-heaps.)

Links

Crossrefs

First lower diagonal of A373451.
Cf. A056971 (without repeated elements).

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-> add(binomial(n, j)*(-1)^j*b(n+1, n-j), j=0..n):
seq(a(n), n=0..29);

Formula

a(n) = A373451(n+1,n).

A373500 Number of (binary) heaps of length 2n whose element set equals [n].

Original entry on oeis.org

1, 1, 5, 55, 1004, 27456, 1077657, 59699950, 3944644671, 319905929418, 32390662046661, 4181039787994506, 602128996908467070, 102537208988632300118, 20497804459093071390108, 4978144718604701947160364, 1232227300264551117529973052, 335016989869301170468736520008
Offset: 0

Views

Author

Alois P. Heinz, Jun 06 2024

Keywords

Comments

These heaps contain repeated elements and their element sets are gap-free and contain 1 (if nonempty).

Examples

			a(0) = 1: the empty heap.
a(1) = 1: 11.
a(2) = 5: 2111, 2121, 2211, 2212, 2221.
a(3) = 55: 312111, 312112, 313112, 321111, ..., 333221, 333231, 333312, 333321.
a(4) = 1004: 41311121, 41311211, 41311221, 41311231, ... 44444213, 44444231, 44444312, 44444321.
(The examples use max-heaps.)

Links

Crossrefs

Cf. A056971, 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-> add(binomial(n, j)*(-1)^j*b(2*n, n-j), j=0..n):
seq(a(n), n=0..17);

Formula

a(n) = A373451(2n,n).

A373608 Number of (binary) heaps of length n whose element set equals [k], where k is chosen so as to maximize this number.

Original entry on oeis.org

1, 1, 1, 3, 7, 23, 92, 502, 1880, 12008, 66730, 516610, 3194229, 29181056, 224463264, 2481941592, 18805353654, 203330533890, 1845535279170, 25328291231632, 244141112078994, 3361871786122320, 39998248932957744, 674899378544965360, 7394457611253245344
Offset: 0

Views

Author

Alois P. Heinz, Jun 10 2024

Keywords

Comments

These heaps may contain repeated elements. Their element sets are gap-free and contain 1 (if nonempty).

Examples

			a(4) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321 (with k=3).
a(6) = 92: 413112, 423111, 423112, 423113, 423121, 423122, 423123, ..., 443421, 444123, 444132, 444213, 444231, 444312, 444321 (with k=4).
a(7) = 502: 5141123, 5141132, 5241113, 5241123, 5241131, 5241132, 5241133, ..., 5553421, 5554123, 5554132, 5554213, 5554231, 5554312, 5554321 (with k=5).
(The examples use max-heaps.)

Links

Crossrefs

Row maxima of A373451.
Cf. A002869.

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):
a:= n-> max(seq(T(n, k), k=0..n)):
seq(a(n), n=0..24);

Formula

a(n) = max({ A373451(n,k) : 0 <= k <= n }).

A373897 Number of (binary) heaps of length n-k whose element set equals [k], where k is chosen so as to maximize this number.

Original entry on oeis.org

1, 0, 1, 1, 1, 3, 5, 9, 23, 55, 147, 386, 1004, 3128, 8113, 27456, 111574, 321433, 1150885, 4888981, 17841912, 80566518, 332583340, 1188065665, 5473922425, 21725492503, 99894124075, 548452369329, 2185136109838, 11339193480666, 59140581278157, 288137011157366
Offset: 0

Views

Author

Alois P. Heinz, Jun 21 2024

Keywords

Comments

These heaps may contain repeated elements. Their element sets are gap-free and contain 1 (if nonempty).

Examples

			a(6) = 5: 2111, 2121, 2211, 2212, 2221 (with k=2).
a(7) = 9: 21111, 21211, 22111, 22112, 22121, 22122, 22211, 22212, 22221 (with k=2).
a(8) = 23: 31211, 32111, 32112, 32121, 32122, 32211, 32212, 32221, 32311, 32312, 32321, 33112, 33121, 33122, 33123, 33132, 33211, 33212, 33213, 33221, 33231, 33312, 33321 (with k=3).
(The examples use max-heaps.)

Links

Crossrefs

Antidiagonal maxima of A373451.
Cf. A373632.

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):
a:= n-> max(seq(T(n-j, j), j=0..n/2)):
seq(a(n), n=0..31);

Formula

a(n) = max({ A373451(n-j,j) : 0 <= j <= floor(n/2) }).

A376962 Number of (binary) heaps of length n whose element set equals {1,2,3}.

Original entry on oeis.org

2, 7, 23, 55, 147, 281, 633, 1241, 2849, 5187, 11195, 21369, 47933, 83821, 174245, 324571, 712247, 1263211, 2660843, 4999291, 11056139, 19236203, 39793055, 73882568, 161646306, 286178632, 601791336, 1129403320, 2495184864, 4326802772, 8921711316, 16528692452
Offset: 3

Views

Author

Alois P. Heinz, Oct 10 2024

Keywords

Examples

			a(4) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321.
a(5) = 23: 31211, 32111, 32112, 32121, 32122, 32211, 32212, 32221, 32311, 32312, 32321, 33112, 33121, 33122, 33123, 33132, 33211, 33212, 33213, 33221, 33231, 33312, 33321.
(The examples use max-heaps.)

Links

Crossrefs

Column k=3 of 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-> (k-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k))(3):
seq(a(n), n=3..35);
Showing 1-10 of 11 results. Next

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

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