login
A325107
Number of subsets of {1...n} with no binary containments.
11
1, 2, 4, 5, 10, 13, 18, 19, 38, 52, 77, 83, 133, 147, 166, 167, 334, 482, 764, 848, 1465, 1680, 1987, 2007, 3699, 4413, 5488, 5572, 7264, 7412, 7579, 7580, 15160, 22573, 37251, 42824, 77387, 92863, 116453, 118461, 227502, 286775, 382573, 392246, 555661, 574113
OFFSET
0,2
COMMENTS
A pair of positive integers is a binary containment if the positions of 1's in the reversed binary expansion of the first are a subset of the positions of 1's in the reversed binary expansion of the second.
LINKS
Fausto A. C. Cariboni, Table of n, a(n) for n = 0..129, (terms up to a(71) from Alois P. Heinz)
FORMULA
a(2^n - 1) = A014466(n).
EXAMPLE
The a(0) = 1 through a(6) = 18 subsets:
{} {} {} {} {} {} {}
{1} {1} {1} {1} {1} {1}
{2} {2} {2} {2} {2}
{1,2} {3} {3} {3} {3}
{1,2} {4} {4} {4}
{1,2} {5} {5}
{1,4} {1,2} {6}
{2,4} {1,4} {1,2}
{3,4} {2,4} {1,4}
{1,2,4} {2,5} {1,6}
{3,4} {2,4}
{3,5} {2,5}
{1,2,4} {3,4}
{3,5}
{3,6}
{5,6}
{1,2,4}
{3,5,6}
MAPLE
c:= proc() option remember; local i, x, y;
x, y:= map(n-> Bits[Split](n), [args])[];
for i to nops(x) do
if x[i]=1 and y[i]=0 then return false fi
od; true
end:
b:= proc(n, s) option remember; `if`(n=0, 1, b(n-1, s)+
`if`(ormap(i-> c(n, i), s), 0, b(n-1, s union {n})))
end:
a:= n-> b(n, {}):
seq(a(n), n=0..34); # 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[#, SubsetQ[binpos[#1], binpos[#2]]&]&]], {n, 0, 13}]
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 28 2019
EXTENSIONS
a(16)-a(45) from Alois P. Heinz, Mar 28 2019
STATUS
approved