OFFSET
0,2
COMMENTS
A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. For example, the binary representations of {2,5,8} are:
2 = 10,
5 = 101,
8 = 1000,
and since there are no columns with more than one 1, {2,5,8} is counted under a(8).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..16383
FORMULA
a(2^n - 1) = A000110(n + 1).
EXAMPLE
The a(1) = 1 through a(7) = 15 subsets:
{} {} {} {} {} {} {}
{1} {1} {1} {1} {1} {1} {1}
{2} {2} {2} {2} {2} {2}
{1,2} {3} {3} {3} {3} {3}
{1,2} {4} {4} {4} {4}
{1,2} {5} {5} {5}
{1,4} {1,2} {6} {6}
{2,4} {1,4} {1,2} {7}
{3,4} {2,4} {1,4} {1,2}
{1,2,4} {2,5} {1,6} {1,4}
{3,4} {2,4} {1,6}
{1,2,4} {2,5} {2,4}
{3,4} {2,5}
{1,2,4} {3,4}
{1,2,4}
MAPLE
b:= proc(n, t) option remember; `if`(n=0, 1, b(n-1, t)+
`if`(Bits[And](n, t)=0, b(n-1, Bits[Or](n, t)), 0))
end:
a:= n-> b(n, 0):
seq(a(n), n=0..63); # Alois P. Heinz, Mar 28 2019
MATHEMATICA
binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
Table[Length[Select[Subsets[Range[n]], stableQ[#, Intersection[binpos[#1], binpos[#2]]!={}&]&]], {n, 0, 10}]
CROSSREFS
KEYWORD
nonn,look
AUTHOR
Gus Wiseman, Mar 27 2019
EXTENSIONS
a(16)-a(55) from Alois P. Heinz, Mar 28 2019
STATUS
approved