login
A373496
Number of (binary) heaps with element set [n] and length n+1.
2
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,3
COMMENTS
These heaps contain exactly one repeated element.
LINKS
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
a(n) = A373451(n+1,n).
EXAMPLE
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.)
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);
CROSSREFS
First lower diagonal of A373451.
Cf. A056971 (without repeated elements).
Sequence in context: A331685 A029891 A151454 * A106936 A088704 A341072
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jun 06 2024
STATUS
approved