A073202 -id:A073202 - cp's OEIS frontend

A036987 Fredholm-Rueppel sequence.

1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane

Binary representation of the Kempner-Mahler number Sum_{k>=0} 1/2^(2^k) = A007404.
Also a(n) = A(n) mod 2 where A is any of A001700, A005573, A007854, A026641, A049027, A064063, A064088, A064090, A064092, A064325, A064327, A064329, A064331, A064613, A076026, A105523, A123273, A126694, A126930, A126931, A126982, A126983, A126987, A127016, A127053, A127358, A127360, A127361, A127363. - Philippe Deléham, May 26 2007
a(n) = (product of digits of n; n in binary notation) mod 2. This sequence is a transformation of the Thue-Morse sequence (A010060), since there exists a function f such that f(sum of digits of n) = (product of digits of n). - Ctibor O. Zizka, Feb 12 2008
a(n-1), n >= 1, the characteristic sequence for powers of 2, A000079, is the unique solution of the following formal product and formal power series identity: Product_{j>=1} (1 + a(j-1)*x^j) = 1 + Sum_{k>=1} x^k = 1/(1-x). The product is therefore Product_{l>=1} (1 + x^(2^l)). Proof. Compare coefficients of x^n and use the binary representation of n. Uniqueness follows from the recurrence relation given for the general case under A147542. - Wolfdieter Lang, Mar 05 2009
a(n) is also the number of orbits of length n for the map x -> 1-cx^2 on [-1,1] at the Feigenbaum critical value c=1.401155... . - Thomas Ward, Apr 08 2009
A054525 (Mobius transform) * A001511 = A036987 = A047999^(-1) * A001511 = the inverse of Sierpiński's gasket * the ruler sequence. - Gary W. Adamson, Oct 26 2009 [Of course this is only vaguely correct depending on how the fuzzy indexing in these formulas is made concrete. - R. J. Mathar, Jun 20 2014]
Characteristic function of A000225. - Reinhard Zumkeller, Mar 06 2012
Also parity of the Catalan numbers A000108. - Omar E. Pol, Jan 17 2012
For n >= 2, also the largest exponent k >= 0 such that n^k in binary notation does not contain both 0 and 1. Unlike for the decimal version of this sequence, A062518, where the terms are only conjectural, for this sequence the values of a(n) can be proved to be the characteristic function of A000225, as follows: n^k will contain both 0 and 1 unless n^k = 2^r-1 for some r. But this is a special case of Catalan's equation x^p = y^q-1, which was proved by Preda Mihăilescu to have no nontrivial solution except 2^3 = 3^2 - 1. - Christopher J. Smyth, Aug 22 2014
Image, under the coding a,b -> 1; c -> 0, of the fixed point, starting with a, of the morphism a -> ab, b -> cb, c -> cc. - Jeffrey Shallit, May 14 2016
Number of nonisomorphic Boolean algebras of order n+1. - Jianing Song, Jan 23 2020

			G.f. = 1 + x + x^3 + x^7 + x^15 + x^31 + x^63 + x^127 + x^255 + x^511 + ...
a(7) = 1 since 7 = 2^3 - 1, while a(10) = 0 since 10 is not of the form 2^k - 1 for any integer k.

Antti Karttunen, Table of n, a(n) for n = 0..65537
D. Bailey et al., On the binary expansions of algebraic numbers, Journal de Théorie des Nombres de Bordeaux 16 (2004), 487-518.
Paul Barry, Some observations on the Rueppel sequence and associated Hankel determinants, arXiv:2005.04066 [math.CO], 2020.
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
Mats Granvik, Mathematica program for computing Fredholm Rueppel sequences
D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions, in Sequences and their Applications, C. Ding, T. Helleseth, and H. Niederreiter, eds., Proceedings of SETA'98 (Singapore, 1998), 308-317, 1999.
Preda Mihăilescu, Primary Cyclotomic Units and a Proof of Catalan's Conjecture, J. Reine angew. Math. 572 (2004): 167-195. doi:10.1515/crll.2004.048. MR 2076124.
H. Niederreiter and M. Vielhaber, Tree Complexity and a Doubly Exponential Gap between Structured and Random Sequences, J. Complexity, 12 (1996), 187-198.
Apisit Pakapongpun and Thomas Ward, Functorial orbit counting, Journal of Integer Sequences, 12 (2009) Article 09.2.4. [From _Thomas Ward_, Apr 08 2009]
Eric Rowland and Reem Yassawi, Profinite automata, arXiv:1403.7659 [math.DS], 2014. See p. 8.
E. Sheppard, net.math post (1985)
Stephen Wolfram, [Page 1092] A New Kind of Science | Online.
Index entries for characteristic functions

Cf. A007404, A043545, A062518, A078885, A078585, A078886, A078887, A078888, A078889, A078890.
The first row of A073346. Occurs for first time in A073202 as row 6 (and again as row 8).
Congruent to any of the sequences A000108, A007460, A007461, A007463, A007464, A061922, A068068 reduced modulo 2. Characteristic function of A000225.
If interpreted with offset=1 instead of 0 (i.e., a(1)=1, a(2)=1, a(3)=0, a(4)=1, ...) then this is the characteristic function of 2^n (A000079) and as such occurs as the first row of A073265. Also, in that case the INVERT transform will produce A023359.
This is Guy Steele's sequence GS(1, 3), also GS(3, 1) (see A135416).
Cf. A054525, A047999. - Gary W. Adamson, Oct 26 2009
Cf. A043529, A127802.

a036987 n = ibp (n+1) where
   ibp 1 = 1
   ibp n = if r > 0 then 0 else ibp n' where (n',r) = divMod n 2
a036987_list = 1 : f [0,1] where f (x:y:xs) = y : f (x:xs ++ [x,x+y])
-- Same list generator function as for a091090_list, cf. A091090.
-- Reinhard Zumkeller, May 19 2015, Apr 13 2013, Mar 13 2013

A036987:= n-> `if`(2^ilog2(n+1) = n+1, 1, 0):
seq(A036987(n), n=0..128);

RealDigits[ N[ Sum[1/10^(2^n), {n, 0, Infinity}], 110]][[1]]
(* Recurrence: *)
t[n_, 1] = 1; t[1, k_] = 1;
t[n_, k_] := t[n, k] =
  If[n < k, If[n > 1 && k > 1, -Sum[t[k - i, n], {i, 1, n - 1}], 0],
   If[n > 1 && k > 1, Sum[t[n - i, k], {i, 1, k - 1}], 0]];
Table[t[n, k], {k, n, n}, {n, 104}]
(* Mats Granvik, Jun 03 2011 *)
mb2d[n_]:=1 - Module[{n2 = IntegerDigits[n, 2]}, Max[n2] - Min[n2]]; Array[mb2d, 120, 0] (* Vincenzo Librandi, Jul 19 2019 *)
Table[PadRight[{1},2^k,0],{k,0,7}]//Flatten (* Harvey P. Dale, Apr 23 2022 *)

{a(n) =( n++) == 2^valuation(n, 2)}; /* Michael Somos, Aug 25 2003 */

a(n) = !bitand(n, n+1); \\ Ruud H.G. van Tol, Apr 05 2023

from sympy import catalan
def a(n): return catalan(n)%2 # Indranil Ghosh, May 25 2017

def A036987(n): return int(not(n&(n+1))) # Chai Wah Wu, Jul 06 2022

1 followed by a string of 2^k - 1 0's. Also a(n)=1 iff n = 2^m - 1.
a(n) = a(floor(n/2)) * (n mod 2) for n>0 with a(0)=1. - Reinhard Zumkeller, Aug 02 2002 [Corrected by Mikhail Kurkov, Jul 16 2019]
Sum_{n>=0} 1/10^(2^n) = 0.110100010000000100000000000000010...
1 if n=0, floor(log_2(n+1)) - floor(log_2(n)) otherwise. G.f.: (1/x) * Sum_{k>=0} x^(2^k) = Sum_{k>=0} x^(2^k-1). - Ralf Stephan, Apr 28 2003
a(n) = 1 - A043545(n). - Michael Somos, Aug 25 2003
a(n) = -Sum_{d|n+1} mu(2*d). - Benoit Cloitre, Oct 24 2003
Dirichlet g.f. for right-shifted sequence: 2^(-s)/(1-2^(-s)).
a(n) = A000108(n) mod 2 = A001405(n) mod 2. - Paul Barry, Nov 22 2004
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*Sum_{j=0..k} binomial(k, 2^j-1). - Paul Barry, Jun 01 2006
A000523(n+1) = Sum_{k=1..n} a(k). - Mitch Harris, Jul 22 2011
a(n) = A209229(n+1). - Reinhard Zumkeller, Mar 07 2012
a(n) = Sum_{k=1..n} A191898(n,k)*cos(Pi*(n-1)*(k-1))/n; (conjecture). - Mats Granvik, Mar 04 2013
a(n) = A000035(A000108(n)). - Omar E. Pol, Aug 06 2013
a(n) = 1 iff n=2^k-1 for some k, 0 otherwise. - M. F. Hasler, Jun 20 2014
a(n) = ceiling(log_2(n+2)) - ceiling(log_2(n+1)). - Gionata Neri, Sep 06 2015
From John M. Campbell, Jul 21 2016: (Start)
a(n) = (A000168(n-1) mod 2).
a(n) = (A000531(n+1) mod 2).
a(n) = (A000699(n+1) mod 2).
a(n) = (A000891(n) mod 2).
a(n) = (A000913(n-1) mod 2), for n>1.
a(n) = (A000917(n-1) mod 2), for n>0.
a(n) = (A001142(n) mod 2).
a(n) = (A001246(n) mod 2).
a(n) = (A001246(n) mod 4).
a(n) = (A002057(n-2) mod 2), for n>1.
a(n) = (A002430(n+1) mod 2). (End)
a(n) = 2 - A043529(n). - Antti Karttunen, Nov 19 2017
a(n) = floor(1+log(n+1)/log(2)) - floor(log(2n+1)/log(2)). - Adriano Caroli, Sep 22 2019
This is also the decimal expansion of -Sum_{k>=1} mu(2*k)/(10^k - 1), where mu is the Möbius function (A008683). - Amiram Eldar, Jul 12 2020

Edited by M. F. Hasler, Jun 20 2014

A073200 Number of simple Catalan bijections of type B.

Original entry on oeis.org

0, 1, 0, 3, 1, 0, 2, 2, 1, 0, 7, 3, 3, 1, 0, 8, 4, 2, 3, 1, 0, 6, 6, 8, 2, 3, 1, 0, 4, 5, 7, 7, 2, 3, 1, 0, 5, 7, 6, 6, 8, 2, 3, 1, 0, 17, 8, 5, 8, 7, 7, 2, 2, 1, 0, 18, 9, 4, 4, 6, 8, 7, 3, 3, 1, 0, 20, 10, 22, 5, 5, 5, 8, 4, 2, 2, 1, 0, 21, 14, 21, 17, 4, 4, 6, 5, 8, 3, 3, 1, 0

Offset: 0

Antti Karttunen, Jun 25 2002

Each row is a permutation of nonnegative integers induced by a Catalan bijection (constructed as explained below) acting on the parenthesizations/plane binary trees as encoded and ordered by A014486/A063171.
The construction process is akin to the constructive mapping of primitive recursive functions to N: we have two basic primitives, A069770 (row 0) and A072796 (row 1), of which the former swaps the left and the right subtree of a binary tree and the latter exchanges the positions of the two leftmost subtrees of plane general trees, unless the tree's degree is less than 2, in which case it just fixes it. From then on, the even rows are constructed recursively from any other Catalan bijection in this table, using one of the five allowed recursion types:
0 - Apply the given Catalan bijection and then recurse down to both subtrees of the new binary tree obtained. (last decimal digit of row number = 2)
1 - First recurse down to both subtrees of the old binary tree and only after that apply the given Catalan bijection. (last digit = 4)
2 - Apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree obtained. (last digit = 6)
3 - First recurse down to the right subtree of old binary tree and only after that apply the given Catalan bijection. (last digit = 8)
4 - First recurse down to the left subtree of old binary tree, after that apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree. (last digit = 0)
The odd rows > 2 are compositions of the rows 0, 1, 2, 4, 6, 8, ... (i.e. either one of the primitives A069770 or A072796, or one of the recursive compositions) at the left hand side and any Catalan bijection from the same array at the right hand side. See the scheme-functions index-for-recursive-sgtb and index-for-composed-sgtb how to compute the positions of the recursive and ordinary compositions in this table.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Four other tables giving the corresponding cycle-counts: A073201, counts of the fixed elements: A073202, the lengths of the largest cycles: A073203, the LCM's of all the cycles: A073204. The ordinary compositions are encoded using the N X N -> N bijection A054238 (which in turn uses the bit-interleaving function A000695).
The first 21 rows of this table:.
Row 0: A069770. Row 1: A072796. Row 2: A057163. Row 3: A073269, Row 4: A057163 (duplicate), Row 5: A073270, Row 6: A069767, Row 7: A001477 (identity perm.), Row 8: A069768, Row 9: A073280.
Row 10: A069770 (dupl.), Row 11: A072796 (dupl.), Row 12: A057511, Row 13: A073282, Row 14: A057512, Row 15: A073281, Row 16: A057509, Row 17: A073280 (dupl.), Row 18: A057510, Row 19: A073283, Row 20: A073284.
Other Catalan bijection-induced EIS-permutations which occur in this table. Only the first known occurrence is given. Involutions are marked with *, others paired with their inverse:.
Row 164: A057164*, Row 168: A057508*, Row 179: A072797*.
Row 41: A073286 - Row 69: A073287. Row 105: A073290 - Row 197: A073291. Row 416: A073288 - Row 696: A073289.
Row 261: A057501 - Row 521: A057502. Row 2618: A057503 - Row 5216: A057504. Row 2614: A057505 - Row 5212: A057506.
Row 10435: A073292 - Row ...: A073293. Row 17517: A057161 - Row ...: A057162.
For a more practical enumeration system of (some) Catalan automorphisms see table A089840 and its various "recursive derivations".

A023359 Number of compositions (ordered partitions) of n into powers of 2.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 18, 31, 56, 98, 174, 306, 542, 956, 1690, 2983, 5272, 9310, 16448, 29050, 51318, 90644, 160118, 282826, 499590, 882468, 1558798, 2753448, 4863696, 8591212, 15175514, 26805983, 47350056, 83639030, 147739848, 260967362

Offset: 0

David W. Wilson

a(n) is the number of partitions of 2n into n parts, with each partition realized into non-symmetric permutations ignoring 1's. For example a(6): the partitions of 12 into 6 are: 111117 (1), 111126 (1), 111135 (1), 111144 (1), 111225 (2), 111234 (3), 111333 (1), 112233 (3), 112224 (2), 122223 (2), 222222 (1), where the number in brackets is the number of non-symmetric permutations ignoring 1's (e.g., 111234, ignore 1's -> 234 and we can also have 243 and 324, 112233->2233 or 2323 or 2332). The sum of the bracketed numbers is a(6)=18. - Jon Perry, Jun 22 2003
a(n) is an eigensequence for the sequence array of the Fredholm-Rueppel sequence A036987. - Paul Barry, Nov 03 2010
a(n) is the number of ways to express n in Napier's location numerals (see Wikipedia). - P. Christopher Staecker, Jul 04 2024

			A(x) = A(x^2) + x*A(x^2)^2 + x^2*A(x^2)^3 + x^3*A(x^2)^4 + ... = 1 + x + 2x^2 + 3x^3 + 6x^4 + 10x^5 + 18x^6 + 31x^7 + ....
From _Joerg Arndt_, Dec 28 2012: (Start)
There are a(6)=18 compositions of 6 into powers of 2:
[ 1]  [ 1 1 1 1 1 1 ]
[ 2]  [ 1 1 1 1 2 ]
[ 3]  [ 1 1 1 2 1 ]
[ 4]  [ 1 1 2 1 1 ]
[ 5]  [ 1 1 2 2 ]
[ 6]  [ 1 1 4 ]
[ 7]  [ 1 2 1 1 1 ]
[ 8]  [ 1 2 1 2 ]
[ 9]  [ 1 2 2 1 ]
[10]  [ 1 4 1 ]
[11]  [ 2 1 1 1 1 ]
[12]  [ 2 1 1 2 ]
[13]  [ 2 1 2 1 ]
[14]  [ 2 2 1 1 ]
[15]  [ 2 2 2 ]
[16]  [ 2 4 ]
[17]  [ 4 1 1 ]
[18]  [ 4 2 ]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n = 0..200 from T. D. Noe)
G. Alkauskas, Congruence properties of the function that counts compositions into powers of 2, J. Integer Sequences 13 (2010), Article: 10.5.3, 2010.
Giedrius Alkauskas, Algebraic functions with Fermat property, eigenvalues of transfer operator and Riemann zeros, and other open problems, arXiv:1609.09842 [math.NT], 2016. Mentions this sequence.
Jung-Chao Ban, Wen-Guei Hu, Guan-Yu Lai, and Lingmin Liao, Entropy of axial product of multiplicative subshifts, arXiv:2402.19324 [math.DS], 2024. See p. 13.
N. J. A. Sloane, Transforms.
Wikipedia, Location arithmetic.

The column sums of the table A073265.

Cf. A073267, A073202, A073288.

a:= proc(n) option remember;
      `if`(n=0, 1, add(a(n-2^i), i=0..ilog2(n)))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jan 11 2014

CoefficientList[Series[1/(1 - Sum[x^(2^i), {i, 0, 20}]), {x, 0, 20}], x]
a[0] = 1; a[n_] := a[n] = Sum[a[n-2^k], {k, 0, Log[2, n]}]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Oct 25 2015, after Alois P. Heinz *)

{a(n) = local(A, m); if( n<0, 0, m=1; A = 1 + O(x); while( m<=n, m*=2; A = 1 /(1 / subst(A, x, x^2) - x)); polcoeff(A, n))}; /* Michael Somos, Dec 20 2002 */

N=66; x='x+O('x^N);
Vec( 1/(1-sum(k=0,ceil(log(N)/log(2)), x^(2^k) ) ) )
/* Joerg Arndt, Oct 21 2012 */

G.f.: 1 / (1 - Sum_{k>=0} x^(2^k)). - Joerg Arndt, Oct 21 2012
a(n) = [n=0] + Sum_{k>=0} a(n-2^k). - Len Smiley, May 07 2001
A(x) = A(x^2)/(1 - x*A(x^2)). - Paul D. Hanna, Dec 16 2002
INVERT transform of characteristic function of powers of 2, i.e., A036987 interpreted with an offset 1 instead of 0. - Antti Karttunen, Dec 12 2003
a(n) seems to be asymptotic to A*B^n where A=0.332198..., B=1.766398... - Benoit Cloitre, Dec 17 2002. More accurately: B=1.76639811455017359722848839244009973023206928795707277527828507440838434..., A=0.58679374529351144845013208294162259198824401250194713608555348278359775... - Vaclav Kotesovec, Apr 30 2014
Satisfies A(x) = 1 + A(x) * Sum_{k>=0} x^(2^k). a(m) == 1 (mod 2) when m=2^n-1, otherwise a(m) == 0 (mod 2). - Paul D. Hanna, Aug 27 2003
a(m) == 0 (mod 4) if A000120(m+2) >= 4. In general, a(m) == 0 (mod 2^N) if A000120(m+2^(N-1)) >= 2^N. - Giedrius Alkauskas, Mar 05 2010

Edited by Franklin T. Adams-Watters, Aug 05 2005

A057546 Number of Catalan objects of size n fixed by Catalan Automorphism A057511/A057512 (deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 10, 11, 18, 21, 34, 35, 68, 69, 137, 148, 316, 317, 759, 760, 1869, 1915, 4833, 4834, 12796, 12802, 34108, 34384, 92792, 92793, 254752, 254753, 703083, 704956, 1958210, 1958231, 5485330, 5485331, 15427026, 15440591, 43618394, 43618395, 123807695, 123807696, 352561832, 352664217, 1007481494, 1007481495, 2887387009

Offset: 0

Antti Karttunen, Sep 07 2000

nonn

Greater than A003238 because there exists also parenthesizations like ((() (())) ((()) ())) and (((()) ()) (() (()))) which are fixed by recursive deep rotation, corresponding to Catalan mountain ranges below:
...../\..../\............................./\......../\
../\/\../\/\.....and.its."dual"....../\/\../\/\
./____\/____\......................./____\/____\
It's obvious that a(p) = a(p-1)+1 for all primes p.

Index entries for sequences related to parenthesizing

The first row of A079216. The leftmost edge of the triangle A079217 and also its row sums shifted by one. Occurs for first time in A073202 as row 12. Cf. A057513, A079223-A079227, A034731, A003238.

with(numtheory,divisors); A057546 := proc(n) local d; if(0=n) then RETURN(1); else RETURN(add(A079216bi(d-1,n/d),d=divisors(n))); fi; end;

a(0)=1, a(n) = A079216(n, 1) = Sum_{d|n} A079216(d-1, n/d). - Antti Karttunen, Jan 03 2003

A073267 Number of compositions (ordered partitions) of n into exactly two powers of 2.

Original entry on oeis.org

0, 0, 1, 2, 1, 2, 2, 0, 1, 2, 2, 0, 2, 0, 0, 0, 1, 2, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

Starting with 1 = self-convolution of A036987, the characteristic function of the powers of 2. [Gary W. Adamson, Feb 23 2010]

			For 2 there is only composition {1+1}, for 3 there is {1+2, 2+1}, for 4 {2+2}, for 5 {1+4, 4+1}, for 6 {2+4,4+2}, for 7 none, thus a(2)=1, a(3)=2, a(4)=1, a(5)=2, a(6)=2 and a(7)=0.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Sen-Peng Eu, Shu-Chung Liu and Yeong-Nan Yeh, Catalan and Motzkin numbers modulo 4 and 8, Eur. J. Combinat. 29 (2008) 1449-1466.

The second row of the table A073265. The essentially same sequence 1, 1, 2, 1, 2, 2, 0, 1, ... occurs for first time in A073202 as row 105 (the fix count sequence of A073290). The positions of 1's for n > 1 is given by the characteristic function of A000079, i.e. A036987 with offset 1 instead of 0 and the positions of 2's is given by A018900. Cf. also A023359.

Cf. A036987. [Gary W. Adamson, Feb 23 2010]

a073267 n = sum $ zipWith (*) a209229_list $ reverse $ take n a036987_list
-- Reinhard Zumkeller, Mar 07 2012

f:= proc(n) local d;
d:= convert(convert(n,base,2),`+`);
if d=2 then 2 elif d=1 then 1 else 0 fi
end proc:
0, 0, seq(f(n),n=2..100); # Robert Israel, Jul 07 2016

Table[Count[Map[{#, n - #} &, Range[0, n]], k_ /; Times @@ Boole@ Map[IntegerQ@ Log2@ # &, k] == 1], {n, 0, 88}] (* Michael De Vlieger, Jul 08 2016 *)

N=166; x='x+O('x^N);
v=Vec( 'a0 + sum(k=0,ceil(log(N)/log(2)), x^(2^k) )^2 );
v[1] -= 'a0;  v
/* Joerg Arndt, Oct 21 2012 */

def A073267(n): return m if n>1 and (m:=n.bit_count())<3 else 0 # Chai Wah Wu, Oct 30 2024

G.f.: (Sum_{k>=0} x^(2^k) )^2. - Vladeta Jovovic, Mar 28 2005
a(n+1) = A000108(n) mod 4, n>=1 [Theorem 2.3 of Eu et al.]. - R. J. Mathar, Feb 27 2008
a(n) = sum (A209229(k)*A036987(n-k): k = 0..n), convolution of characteristic functions of 2^n and 2^n-1. [Reinhard Zumkeller, Mar 07 2012]
a(n+2) = A000168(n) mod 4. - John M. Campbell, Jul 07 2016

A073201 Array of cycle count sequences for the table A073200.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 7, 4, 1, 1, 1, 22, 11, 3, 1, 1, 1, 66, 31, 7, 2, 1, 1, 1, 217, 96, 22, 4, 3, 1, 1, 1, 715, 305, 66, 11, 7, 2, 1, 1, 1, 2438, 1007, 217, 30, 22, 4, 2, 2, 1, 1, 8398, 3389, 715, 93, 66, 11, 3, 5, 1, 1, 1, 29414, 11636, 2438, 292, 217, 30, 6, 14, 2, 2, 1, 1

Offset: 0

Antti Karttunen, Jun 25 2002

Each row of this table gives the counts of separate orbits/cycles to which the Catalan bijection given in the corresponding row of A073200 partitions each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Note that for involutions (self-inverse Catalan bijections) this is always (A000108(n)+Affffff(n))/2, where Affffff is the corresponding "fix-count sequence" from the table A073202.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Only the first known occurrence(s) given (marked with ? if not yet proved/unclear): rows 0, 2, 4, etc.: A007595, Row 1: A073191, Rows 6 (& 8): A073431, Row 7: A000108, Rows 12, 14, 20, ...: A057513, Rows 16, 18, ...: A003239, Row 57, ..., 164: A007123, Row 168: A073193, Row 261: A002995, Row 2614: A057507, Row 2618 (?), row 17517: A001683.

A073190 Number of general plane trees which are either empty (the case a(0)), or whose root degree is either 1 (i.e., the planted trees) or the two leftmost subtrees (of the root node) are identical.

Original entry on oeis.org

1, 1, 2, 3, 8, 20, 60, 181, 584, 1916, 6476, 22210, 77416, 272840, 971640, 3488925, 12621168, 45946156, 168206604, 618853270, 2286974856, 8485246456, 31596023208, 118037654258, 442287721872, 1661790513944, 6259494791096

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

The Catalan bijection A072796 fixes only these kinds of trees, so this occurs in the table A073202 as row 1.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Occurs for first time in A073202 as row 1. A073191(n) = (A000108(n)+A073190(n))/2. Cf. also A073192.

A073190 := proc(n) local d; Cat(n-1)+ add( (`mod`((n-d+1),2))*Cat((n-d-2)/2)*Cat(d), d=0..n-2); end;
Cat := n -> binomial(2*n,n)/(n+1);

a[n_] := CatalanNumber[n - 1] + Sum[Mod[n - d + 1, 2]*CatalanNumber[(n - d - 2)/2]*CatalanNumber[d], {d, 0, n - 2}]; a[0] = 1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 06 2016 *)

Cat(n) = binomial(2*n,n)/(n+1);
a(n) = if (n==0, 1, Cat(n-1) + sum(i=0, n-2, if (!((n-i)%2), Cat((n-i-2)/2)*Cat(i)))); \\ Michel Marcus, May 30 2018

a(0)=1, a(n) = Cat(n-1) + Sum_{i=0..n-2, (n-i) is even} Cat((n-i-2)/2)*Cat(i), where Cat(n) is A000108(n).

A079438 a(0) = a(1) = 1, a(n) = 2*(floor((n+1)/3) + (if n >= 14) (floor((n-10)/4) + floor((n-14)/8))).

Original entry on oeis.org

1, 1, 2, 2, 2, 4, 4, 4, 6, 6, 6, 8, 8, 8, 12, 12, 12, 14, 16, 16, 18, 18, 22, 24, 24, 24, 28, 28, 28, 30, 34, 34, 36, 36, 38, 40, 40, 40, 46, 46, 46, 48, 50, 50, 52, 52, 56, 58, 58, 58, 62, 62, 62, 64, 68, 68, 70, 70, 72, 74, 74, 74, 80, 80, 80, 82, 84, 84, 86, 86, 90, 92, 92, 92

Offset: 0

Antti Karttunen, Jan 27 2003

nonn

The original definition was: Number of rooted general plane trees which are symmetric and will stay symmetric after the underlying plane binary tree has been reflected, i.e., number of integers i in range [A014137(n-1)..A014138(n-1)] such that A057164(i) = i and A057164(A057163(i)) = A057163(i).
(Thus also) the number of fixed points in range [A014137(n-1)..A014138(n)] of permutation A071661 (= Donaghey's automorphism M "squared"), which is equal to condition A057164(i) = A069787(i) = i, i.e., the size of the intersection of fixed points of permutations A057164 and A069787 in the same range.
Additional comment from Antti Karttunen, Dec 13 2017: (Start)
However, David Callan's A123050 claims to give more correct version of that count from n=26 onward, so I probably made a little mistake when converting my insights into the formula given here. At that time I reckoned that if the conjecture given in A080070 were true, then it would imply that the formula given here were exact, otherwise it would give only a lower bound.
It would be nice to know what an empirical program would give as the count of fixed points of A071661 for n in range [A014137(25)..A014138(26)] = [6619846420553 .. 24987199492704], with total A000108(26) = 18367353072151 points to check.
(End)

D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees--History of Combinatorial Generation, vi+120pp. ISBN 0-321-33570-8 Addison-Wesley Professional; 1ST edition (Feb 06, 2006).

G. C. Greubel, Table of n, a(n) for n = 0..10000
R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
A. Karttunen, C-program for counting the initial terms of this sequence (empirically)
A. Karttunen, Illustration of initial terms for trees of sizes n=2..18
A. Karttunen, On the fixed points of A071661 (Notes in OEIS Wiki)
D. E. Knuth, Pre-Fascicle 4a: Generating All Trees, Exercise 17, 7.2.1.6.

Cf. A000108, A057163, A057164, A057505, A069787, A071661, A079437, A079439, A079442, A080070, A243490,  A243491, A243492.
From n>= 2 onward A079440(n) = a(n)/2.
Occurs in A073202 as row 13373289.
Differs from A123050 for the first time at n=26.

A079438 := n -> `if`((n<2),1,2*(floor((n+1)/3) + `if`((n>=14),floor((n-10)/4)+floor((n-14)/8),0)));

a[0]:= 1; a[1]:= 1; a[n_]:= a[n] = 2*Floor[(n+1)/3] +2*If[ n >= 14, (Floor[(n-10)/4] +Floor[(n-14)/8]), 0]; Table[a[n], {n, 0, 100}] (* G. C. Greubel, Jan 18 2019 *)

{a(n) = if(n==0, 1, if(n==1, 1, 2*floor((n+1)/3) + 2*if(n >= 14, floor( (n-10)/4) + floor((n-14)/8), 0)))}; \\ G. C. Greubel, Jan 18 2019

a(0) = a(1) = 1, a(n) = 2*(floor((n+1)/3) + (if n >= 14) (floor((n-10)/4) + floor((n-14)/8))).

Entry edited (the definition replaced by a formula, the old definition moved to the comments) - Antti Karttunen, Dec 13 2017

A034731 Dirichlet convolution of b_n=1 with Catalan numbers.

Original entry on oeis.org

1, 2, 3, 7, 15, 46, 133, 436, 1433, 4878, 16797, 58837, 208013, 743034, 2674457, 9695281, 35357671, 129646266, 477638701, 1767268073, 6564120555, 24466283818, 91482563641, 343059672916, 1289904147339, 4861946609466

Offset: 1

Erich Friedman

nonn

Also number of objects fixed by permutations A057509/A057510 (induced by shallow rotation of general parenthesizations/plane trees).

G. C. Greubel, Table of n, a(n) for n = 1..1000

Occurs for first time in A073202 as row 16.

Cf. A000108, A057509, A057510, A057546.

a[n_] := DivisorSum[n, CatalanNumber[#-1]&]; Array[a, 26] (* Jean-François Alcover, Dec 05 2015 *)

a(n) = sumdiv(n, d, binomial(2*(d-1),d-1)/d) \\ Michel Marcus, Jun 07 2013

{a(n) = my(A = sum(m=1, n, (1 - sqrt(1 - 4*x^m +x*O(x^n)))/2 )); polcoeff(A, n)}
for(n=1, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Jan 12 2021

{a(n) = my(A = sum(m=1, n, binomial(2*m-2,m-1)/m * x^m/(1 - x^m +x*O(x^n)) )); polcoeff(A, n)}
for(n=1, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Jan 12 2021

a(n) = Sum_{d divides n} C(d-1) where C() are the Catalan numbers (A000108).
a(n) ~ 4^(n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Dec 05 2015
L.g.f.: -log(Product_{k>=1} (1 - x^k)^(binomial(2*k-2,k-1)/k^2)) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, May 23 2018
G.f.: Sum_{n>=1} (1 - sqrt(1 - 4*x^n))/2. - Paul D. Hanna, Jan 12 2021
G.f.: Sum_{n>=1} A000108(n-1) * x^n/(1 - x^n) where A000108(n) = binomial(2*n,n)/(n+1). - Paul D. Hanna, Jan 12 2021

More comments from Antti Karttunen, Jan 03 2003

cp's OEIS Frontend

A036987 Fredholm-Rueppel sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A073200 Number of simple Catalan bijections of type B.

Views

Author

Keywords

Comments

Links

Crossrefs

A023359 Number of compositions (ordered partitions) of n into powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A057546 Number of Catalan objects of size n fixed by Catalan Automorphism A057511/A057512 (deep rotation of general parenthesizations/plane trees).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A073267 Number of compositions (ordered partitions) of n into exactly two powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A073201 Array of cycle count sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

A073190 Number of general plane trees which are either empty (the case a(0)), or whose root degree is either 1 (i.e., the planted trees) or the two leftmost subtrees (of the root node) are identical.

Views

Author

Keywords

Comments

Links

Crossrefs