A168542 -id:A168542 - cp's OEIS frontend

A309049 Number T(n,k) of (binary) max-heaps on n elements from the set {0,1} containing exactly k 0's; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 3, 4, 4, 2, 1, 1, 1, 4, 6, 6, 5, 2, 1, 1, 1, 4, 7, 8, 7, 5, 2, 1, 1, 1, 5, 10, 12, 11, 8, 5, 2, 1, 1, 1, 5, 11, 16, 17, 13, 9, 5, 2, 1, 1, 1, 6, 15, 23, 27, 24, 16, 10, 5, 2, 1, 1, 1, 6, 16, 27, 34, 34, 27, 18, 11, 5, 2, 1, 1

Offset: 0

Alois P. Heinz, Jul 09 2019

Also the number T(n,k) of (binary) min-heaps on n elements from the set {0,1} containing exactly k 1's.

The sequence of column k satisfies a linear recurrence with constant coefficients of order A063915(k).

			T(6,0) = 1: 111111.
T(6,1) = 3: 111011, 111101, 111110.
T(6,2) = 4: 110110, 111001, 111010, 111100.
T(6,3) = 4: 101001, 110010, 110100, 111000.
T(6,4) = 2: 101000, 110000.
T(6,5) = 1: 100000.
T(6,6) = 1: 000000.
T(7,4) = T(7,7-3) = A000108(3) = 5: 1010001, 1010010, 1100100, 1101000, 1110000.
Triangle T(n,k) begins:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  1,  1;
  1, 2,  2,  1,  1;
  1, 3,  3,  2,  1,  1;
  1, 3,  4,  4,  2,  1,  1;
  1, 4,  6,  6,  5,  2,  1,  1;
  1, 4,  7,  8,  7,  5,  2,  1,  1;
  1, 5, 10, 12, 11,  8,  5,  2,  1, 1;
  1, 5, 11, 16, 17, 13,  9,  5,  2, 1, 1;
  1, 6, 15, 23, 27, 24, 16, 10,  5, 2, 1, 1;
  1, 6, 16, 27, 34, 34, 27, 18, 11, 5, 2, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Columns k=0-10 give: A000012, A110654, A114220 (for n>0), A326504, A326505, A326506, A326507, A326508, A326509, A326510, A326511.
Row sums give A091980(n+1).
T(2n,n) gives A309050.
Rows reversed converge to A000108.
Cf. A000225, A000295, A003095, A024358, A056971, A063915, A137560, A168542, A202019, A309051, A309052.

b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
      x^n+b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n)):
seq(T(n), n=0..14);

b[n_] := b[n] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f]*b[n - 1 - f]]][Min[g - 1, n - g/2]]][2^Floor[Log[2, n]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n]];
T /@ Range[0, 14] // Flatten (* Jean-François Alcover, Oct 04 2019, after Alois P. Heinz *)

Sum_{k=0..n}    k  * T(n,k) = A309051(n).
Sum_{k=0..n} (n-k) * T(n,k) = A309052(n).
Sum_{k=0..2^n-1} T(2^n-1,k) = A003095(n+1).
Sum_{k=0..2^n-1} (2^n-1-k) * T(2^n-1,k) = A024358(n).
Sum_{k=0..n} (T(n,k) - T(n-1,k)) = A168542(n).
T(m,m-n) = A000108(n) for m >= 2^n-1 = A000225(n).
T(2^n-1,k) = A202019(n+1,k+1).

A091980 Recursive sequence; one more than maximum of products of pairs of previous terms with indices summing to current index.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 16, 26, 36, 56, 81, 131, 183, 287, 417, 677, 937, 1457, 2107, 3407, 4759, 7463, 10843, 17603, 24373, 37913, 54838, 88688, 123892, 194300, 282310, 458330, 634350, 986390, 1426440, 2306540, 3221844, 5052452, 7340712, 11917232, 16500522

Offset: 1

Franklin T. Adams-Watters, Mar 15 2004

The maximum is always obtained by taking i as the power of 2 nearest to n/2. - Anna de Mier, Mar 12 2012

a(n) is the number of (binary) max-heaps on n-1 elements from the set {0,1}. a(7) = 16: 000000, 100000, 101000, 101001, 110000, 110010, 110100, 110110, 111000, 111001, 111010, 111011, 111100, 111101, 111110, 111111. - Alois P. Heinz, Jul 09 2019

A. de Mier and M. Noy, On the maximum number of cycles in outerplanar and series-parallel graphs, Graphs Combin., 28 (2012), 265-275.

Alois P. Heinz, Table of n, a(n) for n = 1..5652
F. Disanto and N. A. Rosenberg, Enumeration of ancestral configurations for matching gene trees and species trees, J. Comput. Biol. 24 (2017), 831-850. See Section 4.2.
A. de Mier and M. Noy, On the maximum number of cycles in outerplanar and series-parallel graphs, Elect. Notes Discr. Math 34 (2009) 489-493
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A003095, A056971, A309049.
Partial differences give A168542.
a(n) = A355108(n)+1.
Column k=0 of A370484 and of A372640.

b:= proc(n) option remember; `if`(n=0, 1, (g-> (f->
      1+b(f)*b(n-1-f))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
a:= n-> b(n-1):
seq(a(n), n=1..50);  # Alois P. Heinz, Jul 09 2019

a[n_] := a[n] = 1 + Max[Table[a[i] a[n-i], {i, n-1}]]; a[1] = 1;
Array[a, 50] (* Jean-François Alcover, Apr 30 2020 *)

a(n) = 1 + max_{i=1..n-1} a(i)*a(n-i) for n > 1, a(1) = 1.
From Alois P. Heinz, Jul 09 2019: (Start)
a(n) = Sum_{k=0..n-1} A309049(n-1,k).
a(2^(n-1)) = A003095(n). (End)

A147991 Sequence S such that 1 is in S and if x is in S, then 3x-1 and 3x+1 are in S.

Original entry on oeis.org

1, 2, 4, 5, 7, 11, 13, 14, 16, 20, 22, 32, 34, 38, 40, 41, 43, 47, 49, 59, 61, 65, 67, 95, 97, 101, 103, 113, 115, 119, 121, 122, 124, 128, 130, 140, 142, 146, 148, 176, 178, 182, 184, 194, 196, 200, 202, 284, 286, 290, 292, 302, 304, 308, 310, 338, 340, 344, 346

Offset: 1

Clark Kimberling, Dec 07 2008

nonn

Positive numbers that can be written in balanced ternary without a 0 trit. - J. Hufford, Jun 30 2015

Let S be the set of terms. Define c: Z -> P(R) so that c(m) is the translated Cantor ternary set spanning [m-0.5, m+0.5], and let C be the union of c(m) for all m in S U {0} U -S. C is the closure of the translated Cantor ternary set spanning [-0.5, 0.5] under multiplication by 3. - Peter Munn, Jan 31 2022

			0th generation: 1;
1st generation: 2 4;
2nd generation: 5 7 11 13.

Robert Israel, Table of n, a(n) for n = 1..10000
Gevorg Hmayakyan, Trig identity for a(n)
J. H. Loxton and A. J. van der Poorten, An Awful Problem About Integers in Base Four, Acta Arithmetica, volume 49, 1987, pages 193-203. In section 7, John Selfridge and Carole Lacampagne ask whether every k != 0 (mod 3) is the quotient of two terms of this sequence (cf. A351243 and A006288).
Eric Weisstein's World of Mathematics, Cantor Set
Eric Weisstein's World of Mathematics, Closure

Cf. A168542, A191108, A306556.
Cf. A006288, A351243 (non-quotients).
See also the related sequences listed in A191106.
One half of each position > 0 where A307744 sets or equals a record.
Cf. A030300.
Column k=3 of A360099.

import Data.Set (singleton, insert, deleteFindMin)
a147991 n = a147991_list !! (n-1)
a147991_list = f $ singleton 1 where
   f s = m : (f $ insert (3*m - 1) $ insert (3*m + 1) s')
         where (m, s') = deleteFindMin s
-- Reinhard Zumkeller, Feb 21 2012, Jan 23 2011

A147991:= proc(n) option remember; if n::even then 3*procname(n/2)-1 else 3*procname((n-1)/2)+1 fi end proc:
A147991(1):= 1:
[seq](A147991(i),i=1..1000); # Robert Israel, May 05 2014

nn=346; s={1}; While[s1=Select[Union[s, 3*s-1, 3*s+1], # <= nn &];  s != s1, s=s1]; s
a[ n_] := If[ n < -1 || n > 0, 3 a[Quotient[n, 2]] - (-1)^Mod[n, 2], 0]; (* Michael Somos, Dec 22 2018 *)

{a(n) = if( n<-1 || n>0, 3*a(n\2) - (-1)^(n%2), 0)}; /* Michael Somos, Dec 22 2018 */

a(n) = fromdigits(apply(b->if(b,1,-1),binary(n)), 3); \\ Kevin Ryde, Feb 06 2022

a(n) = 3*a(n/2) - 1 if n>=2 is even, 3*a((n-1)/2) + 1 if n is odd, a(0)=0. - Robert Israel, May 05 2014
G.f. g(x) satisfies g(x) = 3*(x+1)*g(x^2) + x/(1+x). - Robert Israel, May 05 2014
Product_{j=0..n-1} cos(3^j) = 2^(-n+1)*Sum_{i=2^(n-1)..2^n-1} cos(a(i)). - Gevorg Hmayakyan, Jan 15 2017
Sum_{i=2^(n-1)..2^n-1} cos(a(i)/3^(n-1)*Pi/2) = 0. - Gevorg Hmayakyan, Jan 15 2017
a(n) = -a(-1-n) for all n in Z. - Michael Somos, Dec 22 2018
For n > 0, A307744(2*a(2n)) = A307744(2*a(2n+1)) = A307744(2*a(n)) + 1. - Peter Munn, Jan 31 2022
a(n) mod 2 = A030300(n). - Alois P. Heinz, Jan 29 2023

cp's OEIS Frontend

A309049 Number T(n,k) of (binary) max-heaps on n elements from the set {0,1} containing exactly k 0's; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A091980 Recursive sequence; one more than maximum of products of pairs of previous terms with indices summing to current index.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A147991 Sequence S such that 1 is in S and if x is in S, then 3x-1 and 3x+1 are in S.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula