

A115993


Size S of the largest subset S of {0,1}^n whose measure m(S) is <= 2^n, where m is the additive measure defined on each element x of S by m({x}) = 2^k(x), where k(x) is the number of nonnull coordinates of x.


2



1, 1, 2, 4, 6, 11, 19, 32, 52, 89, 158, 262, 426, 725, 1287, 2154, 3498, 5931, 10485, 17940, 28965, 48813, 85775, 150923, 241735, 404082, 704598, 1275594, 2031915, 3363953, 5812312, 10438620, 17194101, 28160524, 48156310, 85702564
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

This is an upper bound to sequence A115992; I do not know whether the two sequences are equal. The proof goes by projecting a queen (see definition of A115992), i.e. an element q of {0,1,2}^n, to the element p(q) of {0,1}^n obtained by substituting 0 for 2. Let also D(q) = { q' in {0,2}^n  if q_i <> 1 then q'_i = q_i }; then D(q) = m(p(q)). Two queens q and q' attack each other if and only if either p(q)=p(q') or D(q) and D(q') meet. Conclusion left to the reader.


LINKS



EXAMPLE

a(4)=6=S with S containing (0,0,0,0) (of measure 1), plus the 4 permutations of (1,0,0,0) (each of measure 2), plus (1,1,0,0) (of measure 4). Total measure of S is 1+4*2+4=13, while {0,1}^4 itself has measure 16 and all remaining elements of {0,1} have measure >= 4 so none of them can complete S.


PROG

# in Python (www.python.org): (replace leading dots by spaces)
.def q3ub(n):
... sum = 0;
... vlm = 2**n; # 2 to the nth power
... combi = 1; # combinatorial coefficient (n k)
... for k in range(n+1): # for k := 0 to n
....... c = min(combi, vlm);
....... sum = sum + c;
....... vlm = vlm  c;
....... vlm = vlm // 2; # integer division, result is truncated
....... combi = (combi * (nk)) // (k+1) # division is exact
... #end for k
... return sum


CROSSREFS

Cf. A115992 (of which this is an easier upper bound).


KEYWORD

easy,nonn


AUTHOR

Frederic van der Plancke (fplancke(AT)hotmail.com), Feb 10 2006


STATUS

approved



