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.

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

(Python)

def q3ub(n):

sum = 0;

vlm = 2**n; # 2 to the n-th 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 * (n-k)) // (k+1) # division is exact

#end for k

return sum

CROSSREFS

KEYWORD

easy,nonn

AUTHOR

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

STATUS

approved