1,2

Motivation: consideration of the "hats" problem (which boils down to normal hamming covering codes) in the case when the people are indistinguishable or unlabeled.

If (n mod 6 = 5) then sum(binomial(n, 3*i+1), i=0..n/3); elif (n mod 6 = 2) then sum(binomial(n, 3*i), i=0..n/3)+1; else sum(binomial(n, 3*i), i=0..n/3); fi;

G.f.: x(2x^3-2x^2+1)/(-2x^4+x^3-2x+1).

hatwork := proc(n, i, covered) local val, val2; options remember;

# computes the minimum cover of the i-bit through n-bit words.

# if covered is true the i-bit words are already covered (by the (i-1)-bit words)

if (i>n or (i = n and covered)) then 0; elif (i = n and not covered) then 1; else

# one choice is to include the i-bit words in the cover

val := hatwork(n, i+1, true) + binomial(n, i);

# the other choice is not to include the i-bit words in the cover

if (covered) then val2 := hatwork (n, i+1, false); if (val2 < val) then val := val2; fi; else

# if the i-bit words were not covered by (i-1), they must be covered by the (i+1)-bit words

if (i <= n) then val2 := hatwork (n, i+2, true) + binomial(n, i+1); if (val2 < val) then val := val2; fi; fi; fi; val; fi; end proc;

A081374 := proc (n) hatwork(n, 0, false); end proc;

Cf. A083322.

Sequence in context: A003228 A110182 A075125 this_sequence A117400 A005637 A104080

Adjacent sequences: A081371 A081372 A081373 this_sequence A081375 A081376 A081377

nonn

David Applegate (david(AT)research.att.com), Aug 22 2003