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 non-null coordinates of x.

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

Offset: 0

Author

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

Keywords

• easy
• nonn

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.

Examples

			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.
		

Crossrefs

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

Programs

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