The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 2

%I #5 Jun 01 2010 03:00:00

%S 1,1,2,4,6,11,19,32,52,89,158,262,426,725,1287,2154,3498,5931,10485,

%T 17940,28965,48813,85775,150923,241735,404082,704598,1275594,2031915,

%U 3363953,5812312,10438620,17194101,28160524,48156310,85702564

%N 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.

%C 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.

%e 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.

%o # in Python (www.python.org): (replace leading dots by spaces)

%o .def q3ub(n):

%o ... sum = 0;

%o ... vlm = 2**n; # 2 to the n-th power

%o ... combi = 1; # combinatorial coefficient (n k)

%o ... for k in range(n+1): # for k := 0 to n

%o ....... c = min(combi, vlm);

%o ....... sum = sum + c;

%o ....... vlm = vlm - c;

%o ....... vlm = vlm // 2; # integer division, result is truncated

%o ....... combi = (combi * (n-k)) // (k+1) # division is exact

%o ... #end for k

%o ... return sum

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

%K easy,nonn

%O 0,3

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 30 18:31 EST 2023. Contains 367461 sequences. (Running on oeis4.)