cp's OEIS Frontend

A116549 a(0) = 1. a(m + 2^n) = a(n) + a(m), for 0 <= m <= 2^n - 1.

%I A116549 #34 Jul 23 2019 04:25:00
%S A116549 1,2,3,4,4,5,6,7,5,6,7,8,8,9,10,11,5,6,7,8,8,9,10,11,9,10,11,12,12,13,
%T A116549 14,15,6,7,8,9,9,10,11,12,10,11,12,13,13,14,15,16,10,11,12,13,13,14,
%U A116549 15,16,14,15,16,17,17,18,19,20
%N A116549 a(0) = 1. a(m + 2^n) = a(n) + a(m), for 0 <= m <= 2^n - 1.
%C A116549 Consider the following bijection between the natural numbers and hereditarily finite sets. For each n, write out n in binary. Assign to each set already given a natural number m the (m+1)-th digit of the binary number (reading from right to left). Let the set assigned to n contain all and only those sets which have a 1 for their digit. Then a(n) gives the number of pairs of braces appearing in the n-th set written out in full, e.g., for 3, we have {{{}}{}}, with 4 pairs of braces. - _Thomas Anton_, Mar 16 2019
%H A116549 Reinhard Zumkeller, <a href="/A116549/b116549.txt">Table of n, a(n) for n = 0..10000</a>
%F A116549 For n > 0: a(n) = a(A000523(n)) + a(A053645(n)). - _Reinhard Zumkeller_, Aug 27 2014
%e A116549 From _Gus Wiseman_, Jul 22 2019: (Start)
%e A116549 A finitary (or hereditarily finite) set is equivalent to a rooted identity tree. The following list shows the first few rooted identity trees together with their corresponding index in the sequence (o = leaf).
%e A116549    0: o
%e A116549    1: (o)
%e A116549    2: ((o))
%e A116549    3: (o(o))
%e A116549    4: (((o)))
%e A116549    5: (o((o)))
%e A116549    6: ((o)((o)))
%e A116549    7: (o(o)((o)))
%e A116549    8: ((o(o)))
%e A116549    9: (o(o(o)))
%e A116549   10: ((o)(o(o)))
%e A116549   11: (o(o)(o(o)))
%e A116549   12: (((o))(o(o)))
%e A116549   13: (o((o))(o(o)))
%e A116549   14: ((o)((o))(o(o)))
%e A116549   15: (o(o)((o))(o(o)))
%e A116549   16: ((((o))))
%e A116549   17: (o(((o))))
%e A116549   18: ((o)(((o))))
%e A116549   10: (o(o)(((o))))
%e A116549 (End)
%t A116549 Nest[Append[#1, #1[[#3 + 1]] + #1[[#2 - 2^#3 + 1]] & @@ {#1, #2, Floor@ Log2@ #2}] & @@ {#, Length@ #} &, {1}, 63] (* _Michael De Vlieger_, Apr 21 2019 *)
%t A116549 bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
%t A116549 dab[n_]:=1+Total[dab/@(bpe[n]-1)];
%t A116549 Array[dab,30,0] (* _Gus Wiseman_, Jul 22 2019 *)
%o A116549 (Haskell)
%o A116549 import Data.Function (on); import Data.List (genericIndex)
%o A116549 a116549 = genericIndex a116549_list
%o A116549 a116549_list = 1 : zipWith ((+) `on` a116549) a000523_list a053645_list
%o A116549 -- _Reinhard Zumkeller_, Aug 27 2014
%Y A116549 Cf. A000523, A053645.
%Y A116549 Cf. A000081, A000120, A004111, A029931, A048793, A061775, A070939, A072639, A276625, A279861, A326031.
%K A116549 easy,nonn
%O A116549 0,2
%A A116549 _Leroy Quet_, Mar 16 2006