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 14 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

A306393 Number T(n,k) of defective (binary) heaps on n elements where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n >= 0, 0 <= k <= A061168(n), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 3, 6, 6, 6, 3, 8, 16, 24, 24, 24, 16, 8, 20, 60, 100, 120, 120, 120, 100, 60, 20, 80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80, 210, 840, 1890, 3150, 4200, 4830, 5040, 5040, 4830, 4200, 3150, 1890, 840, 210
Offset: 0

Views

Author

Alois P. Heinz, Feb 12 2019

Keywords

Comments

T(n,k) is the number of permutations p of [n] having exactly k pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that p(i) > p(floor(i/2^j)).
T(n,0) counts perfect (binary) heaps on n elements (A056971).

Examples

			T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 6: 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 6: 2341, 2413, 2431, 3124, 3142, 3214.
T(4,3) = 6: 1342, 1423, 1432, 2134, 2143, 2314.
T(4,4) = 3: 1234, 1243, 1324.
T(5,1) = 16: 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.
(The examples use max-heaps.)
Triangle T(n,k) begins:
   1;
   1;
   1,   1;
   2,   2,   2;
   3,   6,   6,   6,   3;
   8,  16,  24,  24,  24,  16,   8;
  20,  60, 100, 120, 120, 120, 100,  60,  20;
  80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80;
  ...

Links

Crossrefs

Columns k=0-10 give: A056971, A324062, A324063, A324064, A324065, A324066, A324067, A324068, A324069, A324070, A324071.
Row sums give A000142.
Central terms (also maxima) of rows give A324075.
Cf. A000523, A008302, A061168, A120385, A306343, A324074, A372640.
Average number of inversions of a full binary heap on 2^n-1 elements is A000337.

Programs

  • Maple
    b:= proc(u, o) option remember; local n, g, l; n:= u+o;
      if n=0 then 1
    else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
         add(x^(n-j)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
         add(x^(j-1)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o))
      fi
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);
  • Mathematica
    b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u + o;
     If[n == 0, 1, g = 2^Floor@Log[2, n]; l = Min[g - 1, n - g/2]; Expand[
     Sum[x^(n-j)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j - 1, l]}], {j, 1, u}] +
     Sum[x^(j-1)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]]]];
T[n_] := CoefficientList[b[n, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 15 2021, after Alois P. Heinz *)

Formula

T(n,k) = T(n,A061168(n)-k) for n > 0.
Sum_{k=0..A061168(n)} k * T(n,k) = A324074(n).

A370484 Number T(n,k) of defective (binary) heaps on n elements from the set {0,1} with k defects; triangle T(n,k), n>=0, read by rows.

Original entry on oeis.org

1, 2, 3, 1, 5, 2, 1, 7, 6, 3, 11, 11, 9, 1, 16, 20, 24, 4, 26, 32, 52, 16, 2, 36, 60, 100, 52, 8, 56, 100, 192, 120, 40, 4, 81, 162, 351, 300, 111, 18, 1, 131, 255, 631, 627, 313, 77, 13, 1, 183, 427, 1067, 1311, 821, 241, 41, 5, 287, 692, 1856, 2484, 1894, 764, 184, 28, 3
Offset: 0

Views

Author

Alois P. Heinz, May 06 2024

Keywords

Comments

A defect in a defective heap is a parent-child pair not having the correct order.
T(n,k) is the number of bit vectors v of length n having exactly k indices i in [n] such that v[i] > v[floor(i/2)].
T(n,0) counts perfect (binary) heaps on n elements from the set {0,1}.
T(n,k) is defined for all n>=0 and k>=0. The triangle displays only positive terms. All other terms are zero.

Examples

			T(4,0) = 7: 0000, 1000, 1010, 1100, 1101, 1110, 1111.
T(4,1) = 6: 0001, 0010, 0100, 0101, 1001, 1011.
T(4,2) = 3: 0011, 0110, 0111.
(The examples use max-heaps.)
Triangle T(n,k) begins:
    1;
    2;
    3,   1;
    5,   2,    1;
    7,   6,    3;
   11,  11,    9,    1;
   16,  20,   24,    4;
   26,  32,   52,   16,   2;
   36,  60,  100,   52,   8;
   56, 100,  192,  120,  40,   4;
   81, 162,  351,  300, 111,  18,  1;
  131, 255,  631,  627, 313,  77, 13, 1;
  183, 427, 1067, 1311, 821, 241, 41, 5;
  ...

Links

Crossrefs

Columns k=0-1 give: A091980(n+1), A372628.
Row sums give A000079.
T(2n,n) gives A372489.
Cf. A045623, A056971, A139756, A306343, A372640.

Programs

  • Maple
    b:= proc(n, t) option remember; `if`(n=0, 1, (g-> (f->
      expand(b(f, 1)*b(n-1-f, 1)*t+b(f, x)*b(n-1-f, x)))(
      min(g-1, n-g/2)))(2^ilog2(n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..15);
  • Mathematica
    b[n_, t_] := b[n, t] = If[n == 0, 1, Function[g, Function [f,
   Expand[b[f, 1]*b[n - 1 - f, 1]*t + b[f, x]*b[n - 1 - f, x]]][
   Min[g - 1, n - g/2]]][2^(Length[IntegerDigits[n, 2]] - 1)]];
T[n_] := CoefficientList[b[n, 1], x];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 09 2024, after Alois P. Heinz *)

Formula

Sum_{k>=0} k * T(n,k) = A139756(n) = ceiling((n-1)*2^n/4).
Sum_{k>=0} (k+1) * T(n,k) = A045623(n) = ceiling((n+3)*2^n/4).

A323957 Number of defective (binary) heaps on n elements with exactly one defect.

Original entry on oeis.org

0, 1, 2, 9, 28, 90, 360, 1526, 7616, 32460, 190800, 947760, 6382464, 37065600, 296524800, 1812861600, 15283107840, 105015593280, 1017540576000, 7304720544000, 74472335308800, 629300251008000, 7429184791142400, 62417372203929600, 746041213793075200
Offset: 1

Views

Author

Alois P. Heinz, Feb 09 2019

Keywords

Comments

Or number of permutations p of [n] having exactly one index i in {1,...,n} such that p(i) > p(floor(i/2)).

Examples

			a(2) = 1: 12.
a(3) = 2: 213, 231.
a(4) = 9: 2413, 3124, 3214, 3241, 3412, 3421, 4123, 4132, 4213.
a(5) = 28: 25134, 25143, 35124, 35142, 35214, 35241, 42315, 42351, 43125, 43152, 43215, 43251, 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.
a(6) = 90: 362451, 362541, 436125, 436215, ..., 652314, 652413, 653124, 653214.
(The examples use max-heaps.)

Links

Crossrefs

Column k=1 of A306343.
Cf. A056971, A372628, A372643.

Programs

  • Maple
    b:= proc(u, o) option remember; local n, g, l; n:= u+o;
      if n=0 then 1
    else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
         add(add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
         add(add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o)*x)
      fi
    end:
a:= n-> coeff(b(n, 0), x, 1):
seq(a(n), n=1..25);
  • Mathematica
    b[u_, o_] := b[u, o] = Module[{n = u+o, g, l}, If[n == 0, 1,
     g = 2^(Length[IntegerDigits[n, 2]] - 1);
     l = Min[g - 1, n - g/2]; Expand[
     Sum[ Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j-1, l]}], {j, 1, u}] +
     Sum[Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]*x]]];
a[n_] := Coefficient[b[n, 0], x, 1];
Array[a, 25] (* Jean-François Alcover, Apr 22 2021, after Alois P. Heinz *)

A306356 Number of defective (binary) heaps on n elements with floor(n/2) defects.

Original entry on oeis.org

1, 1, 1, 2, 9, 48, 250, 1760, 12502, 111776, 1017060, 11165280, 123760560, 1602344832, 21025461600, 314958758400, 4765553385120, 80958196300800, 1386261729792960, 26344715667079680, 502986050203680000, 10556482426015426560, 222685725334400064000
Offset: 0

Views

Author

Alois P. Heinz, Feb 09 2019

Keywords

Comments

Or number of permutations p of [n] having exactly floor(n/2) indices i in {1,...,n} such that p(i) > p(floor(i/2)).

Examples

			a(2) = 1: 12.
a(3) = 2: 213, 231.
a(4) = 9: 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2431, 3142.
a(5) = 48: 14523, 14532, 15234, 15243, 15324, 15342, 15423, 15432, 24135, 24153, 24513, 24531, 25314, 25341, 25413, 25431, 31245, 31254, 32145, 32154, 32415, 32451, 32514, 32541, 34125, 34152, 34215, 34251, 34512, 34521, 35412, 35421, 41235, 41253, 41325, 41352, 42135, 42153, 42513, 42531, 51234, 51243, 51324, 51342, 51423, 51432, 52134, 52143.
(The examples use max-heaps.)

Links

Crossrefs

Cf. A056971, A306343.

Programs

  • Maple
    b:= proc(u, o) option remember; local n, g, l; n:= u+o;
      if n=0 then 1
    else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
         add(add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
         add(add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o)*x)
      fi
    end:
a:= n-> coeff(b(n, 0), x, iquo(n, 2)):
seq(a(n), n=0..25);
  • Mathematica
    b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u+o; If[n == 0, 1,
   g = 2^(Length@IntegerDigits[n, 2]-1); l = Min[g-1, n-g/2]; Expand[
   Sum[Sum[Binomial[j-1, i]*Binomial[n-j, l-i]*
   b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j-1, l]}], {j, 1, u}] +
   Sum[Sum[Binomial[j-1, i]*Binomial[n-j, l-i]*
   b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]*x]]];
a[n_] := Coefficient[b[n, 0], x, Quotient[n, 2]];
a /@ Range[0, 25] (* Jean-François Alcover, Mar 26 2021, after Alois P. Heinz *)

Formula

a(n) = A306343(n,floor(n/2)).

A323958 Number of defective (binary) heaps on n elements with exactly two defects.

Original entry on oeis.org

0, 2, 9, 48, 250, 1200, 5922, 34160, 185460, 1201920, 6837600, 49680576, 314028000, 2611065600, 17913619680, 162456519680, 1235053617600, 12593800627200, 99016069824000, 1062491684981760, 9425603347776000, 114292447803494400, 1026754912019865600
Offset: 2

Views

Author

Alois P. Heinz, Feb 09 2019

Keywords

Comments

Or number of permutations p of [n] having exactly two indices i in {1,...,n} such that p(i) > p(floor(i/2)).

Links

Crossrefs

Column k=2 of A306343.
Cf. A056971.

A323959 Number of defective (binary) heaps on n elements with exactly three defects.

Original entry on oeis.org

0, 3, 28, 250, 1760, 12502, 82880, 576060, 4200960, 29987760, 239978112, 1744142400, 15361632000, 119854864800, 1159352230400, 9698664271680, 103688467983360, 906866458156800, 10282952826685440, 97685444140416000, 1224926383944806400, 11906083013106585600
Offset: 3

Views

Author

Alois P. Heinz, Feb 09 2019

Keywords

Comments

Or number of permutations p of [n] having exactly three indices i in {1,...,n} such that p(i) > p(floor(i/2)).

Links

Crossrefs

Column k=3 of A306343.
Cf. A056971.

A323960 Number of defective (binary) heaps on n elements with exactly four defects.

Original entry on oeis.org

0, 8, 90, 1200, 12502, 111776, 1017060, 8762880, 77887920, 705522048, 6268548000, 60169824000, 543692724960, 5645713615360, 52992483226560, 596317674101760, 5840267078534400, 70071467744931840, 725037082634304000, 9448088175337574400, 100728713738898432000
Offset: 4

Views

Author

Alois P. Heinz, Feb 09 2019

Keywords

Comments

Or number of permutations p of [n] having exactly four indices i in {1,...,n} such that p(i) > p(floor(i/2)).

Links

Crossrefs

Column k=4 of A306343.
Cf. A056971.

A323961 Number of defective (binary) heaps on n elements with exactly five defects.

Original entry on oeis.org

0, 20, 360, 5922, 82880, 1017060, 11165280, 123760560, 1310267904, 14197154400, 153775564800, 1646888944800, 18660402342400, 201542310930240, 2419644394552320, 26818494698361600, 342175409500446720, 3913572812111424000, 53353484649907200000
Offset: 5

Views

Author

Alois P. Heinz, Feb 09 2019

Keywords

Comments

Or number of permutations p of [n] having exactly five indices i in {1,...,n} such that p(i) > p(floor(i/2)).

Links

Crossrefs

Column k=5 of A306343.
Cf. A056971.

A323962 Number of defective (binary) heaps on n elements with exactly six defects.

Original entry on oeis.org

0, 80, 1526, 34160, 576060, 8762880, 123760560, 1602344832, 21025461600, 264121228800, 3365570435040, 42633973724160, 535972460752320, 7005009151595520, 88526770797830400, 1212423433054986240, 15530632515845568000, 223695310100356300800, 2930160761881213132800
Offset: 6

Views

Author

Alois P. Heinz, Feb 09 2019

Keywords

Comments

Or number of permutations p of [n] having exactly six indices i in {1,...,n} such that p(i) > p(floor(i/2)).

Links

Crossrefs

Column k=6 of A306343.
Cf. A056971.
Showing 1-10 of 14 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.