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

A306343 Number T(n,k) of defective (binary) heaps on n elements with k defects; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 3, 9, 9, 3, 8, 28, 48, 28, 8, 20, 90, 250, 250, 90, 20, 80, 360, 1200, 1760, 1200, 360, 80, 210, 1526, 5922, 12502, 12502, 5922, 1526, 210, 896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896, 3360, 32460, 185460, 576060, 1017060, 1017060, 576060, 185460, 32460, 3360
Offset: 0

Views

Author

Alois P. Heinz, Feb 08 2019

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 permutations p of [n] having exactly k indices i in {1,...,n} such that p(i) > p(floor(i/2)).
T(n,0) counts perfect (binary) heaps on n elements (A056971).

Examples

			T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 9: 2413, 3124, 3214, 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 9: 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2431, 3142.
T(4,3) = 3: 1234, 1243, 1324.
(The examples use max-heaps.)
Triangle T(n,k) begins:
    1;
    1;
    1,    1;
    2,    2,     2;
    3,    9,     9,     3;
    8,   28,    48,    28,      8;
   20,   90,   250,   250,     90,    20;
   80,  360,  1200,  1760,   1200,   360,    80;
  210, 1526,  5922, 12502,  12502,  5922,  1526,  210;
  896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896;
  ...

Links

Crossrefs

Columns k=0-10 give: A056971, A323957, A323958, A323959, A323960, A323961, A323962, A323963, A323964, A323965, A323966.
Row sums give A000142.
T(n,floor(n/2)) gives A306356.
Cf. A001286, A001710, A008292, A038720, A229039, A230056, A264902, A306393.

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:
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 = u + o, g, l},
     If[n == 0, 1, g := 2^Floor@Log[2, n]; 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]]];
T[n_] := CoefficientList[b[n, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 17 2021, after Alois P. Heinz *)

Formula

T(n,k) = T(n,n-1-k) for n > 0.
Sum_{k>=0} k * T(n,k) = A001286(n).
Sum_{k>=0} (k+1) * T(n,k) = A001710(n-1) for n > 0.
Sum_{k>=0} (k+2) * T(n,k) = A038720(n) for n > 0.
Sum_{k>=0} (k+3) * T(n,k) = A229039(n) for n > 0.
Sum_{k>=0} (k+4) * T(n,k) = A230056(n) for n > 0.

A372640 Number T(n,k) of defective (binary) heaps on n elements from the set {0,1} where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n>=0, read by rows.

Original entry on oeis.org

1, 2, 3, 1, 5, 2, 1, 7, 4, 3, 2, 11, 6, 7, 5, 2, 1, 16, 13, 12, 8, 10, 3, 2, 26, 22, 23, 14, 21, 10, 9, 2, 1, 36, 36, 39, 33, 33, 28, 26, 13, 9, 2, 1, 56, 54, 67, 61, 60, 59, 56, 37, 34, 11, 13, 2, 2, 81, 99, 111, 96, 117, 112, 107, 96, 76, 53, 36, 20, 14, 4, 2
Offset: 0

Views

Author

Alois P. Heinz, May 08 2024

Keywords

Comments

T(n,k) is the number of bit vectors v of length n having exactly k pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that v[i] > v[floor(i/2^j)].
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) = 4: 0010, 0100, 1001, 1011.
T(4,2) = 3: 0001, 0101, 0110.
T(4,3) = 2: 0011, 0111.
(The examples use max-heaps.)
Triangle T(n,k) begins:
   1;
   2;
   3,  1;
   5,  2,   1;
   7,  4,   3,  2;
  11,  6,   7,  5,   2,   1;
  16, 13,  12,  8,  10,   3,   2;
  26, 22,  23, 14,  21,  10,   9,  2,  1;
  36, 36,  39, 33,  33,  28,  26, 13,  9,  2,  1;
  56, 54,  67, 61,  60,  59,  56, 37, 34, 11, 13,  2,  2;
  81, 99, 111, 96, 117, 112, 107, 96, 76, 53, 36, 20, 14, 4, 2;
  ...

Links

Crossrefs

Columns k=0-1 give: A091980(n+1), A372643.
Row sums give A000079.
Main diagonal gives A372641.
T(2,n) gives A372642.
Cf. A306393, A370484.

Programs

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

A324062 Number of defective (binary) heaps on n elements where one ancestor-successor pair does not have the correct order.

Original entry on oeis.org

0, 0, 1, 2, 6, 16, 60, 240, 840, 3584, 16800, 96000, 475200, 3041280, 19219200, 153753600, 864864000, 6560153600, 47048601600, 439934976000, 3192583680000, 31434670080000, 280947363840000, 3296449069056000, 27139515346944000, 308787374614118400
Offset: 0

Views

Author

Alois P. Heinz, Feb 13 2019

Keywords

Comments

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

Examples

			a(4) = 6: 3241, 3412, 3421, 4123, 4132, 4213.
a(5) = 16: 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.
(The examples use max-heaps.)

Links

Crossrefs

Column k=1 of A306393.
Cf. A056971.

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:
a:= n-> coeff(b(n, 0), x, 1):
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[ 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}]]]];
a[n_] := Coefficient[b[n, 0], x, 1];
a /@ Range[0, 25] (* Jean-François Alcover, Apr 22 2021, after Alois P. Heinz *)

A324063 Number of defective (binary) heaps on n elements where two ancestor-successor pairs do not have the correct order.

Original entry on oeis.org

0, 0, 0, 2, 6, 24, 100, 480, 1890, 8960, 47040, 288000, 1584000, 10644480, 74131200, 615014400, 3783780000, 29520691200, 230015385600, 2199674880000, 17239951872000, 172890685440000, 1660143513600000, 19778694414336000, 174145223476224000, 2007117934991769600
Offset: 0

Views

Author

Alois P. Heinz, Feb 13 2019

Keywords

Comments

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

Links

Crossrefs

Column k=2 of A306393.
Cf. A056971.

A324064 Number of defective (binary) heaps on n elements where three ancestor-successor pairs do not have the correct order.

Original entry on oeis.org

0, 0, 0, 0, 6, 24, 120, 640, 3150, 16128, 94080, 614400, 3801600, 26864640, 203174400, 1757184000, 11783772000, 95122227200, 794598604800, 7821066240000, 65767223808000, 675845406720000, 6895980748800000, 83909612666880000, 784784318782464000
Offset: 0

Views

Author

Alois P. Heinz, Feb 13 2019

Keywords

Comments

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

Links

Crossrefs

Column k=3 of A306393.
Cf. A056971.

A324065 Number of defective (binary) heaps on n elements where four ancestor-successor pairs do not have the correct order.

Original entry on oeis.org

0, 0, 0, 0, 3, 24, 120, 720, 4200, 24192, 151200, 1056000, 7286400, 54743040, 442041600, 3997593600, 29081052000, 244365721600, 2164235673600, 21996748800000, 197620929792000, 2090405560320000, 22475789107200000, 280198170869760000, 2772753817946112000
Offset: 0

Views

Author

Alois P. Heinz, Feb 13 2019

Keywords

Comments

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

Links

Crossrefs

Column k=4 of A306393.
Cf. A056971.

A324066 Number of defective (binary) heaps on n elements where five ancestor-successor pairs do not have the correct order.

Original entry on oeis.org

0, 0, 0, 0, 0, 16, 120, 720, 4830, 31360, 211680, 1555200, 11880000, 95293440, 815443200, 7687680000, 60432372000, 530552422400, 4945330790400, 51912327168000, 496766020608000, 5425624055808000, 61093281300480000, 781258429366272000, 8157685988035584000
Offset: 0

Views

Author

Alois P. Heinz, Feb 13 2019

Keywords

Comments

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

Links

Crossrefs

Column k=5 of A306393.
Cf. A056971.

A324067 Number of defective (binary) heaps on n elements where six ancestor-successor pairs do not have the correct order.

Original entry on oeis.org

0, 0, 0, 0, 0, 8, 100, 720, 5040, 36736, 268800, 2073600, 17186400, 147502080, 1331616000, 13047091200, 110053944000, 1011903692800, 9874978713600, 106953080832000, 1086116967936000, 12275238666240000, 144074916311040000, 1890064025321472000
Offset: 0

Views

Author

Alois P. Heinz, Feb 13 2019

Keywords

Comments

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

Links

Crossrefs

Column k=6 of A306393.
Cf. A056971.

A324068 Number of defective (binary) heaps on n elements where seven ancestor-successor pairs do not have the correct order.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 60, 640, 5040, 39424, 315840, 2572800, 22730400, 207820800, 1979577600, 20119756800, 180756576000, 1740900761600, 17732095180800, 197872975872000, 2123068147200000, 24858537099264000, 303091124244480000, 4076808466857984000
Offset: 0

Views

Author

Alois P. Heinz, Feb 13 2019

Keywords

Comments

Or number of permutations p of [n] having exactly seven pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that p(i) > p(floor(i/2^j)).

Links

Crossrefs

Column k=7 of A306393.
Cf. A056971.
Showing 1-10 of 15 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.