|
|
A081374
|
|
Size of "uniform" Hamming covers of distance 1, that is, Hamming covers in which all vectors of equal weight are treated the same, included or excluded from the cover together.
|
|
5
|
|
|
1, 2, 2, 5, 10, 22, 43, 86, 170, 341, 682, 1366, 2731, 5462, 10922, 21845, 43690, 87382, 174763, 349526, 699050, 1398101, 2796202, 5592406, 11184811, 22369622, 44739242, 89478485, 178956970, 357913942, 715827883, 1431655766, 2863311530, 5726623061
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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 we add a(0)=1 in front and build the table of a(n) and iterated differences in further rows we get:
1, 1, 2, 2, 5, 10,
0, 1, 0, 3, 5, 12,
1, -1, 3, 2, 7, 9,
-2, 4, -1, 5, 2, 13,
6, -5, 6, -3, 11, 6
-11, 11, -9, 14, -5, 21.
The first column is the inverse binomial transform, which is 1,0 followed by (-1)^n*A083322(n-1), n>=2.
|
|
LINKS
|
|
|
FORMULA
|
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*(2*x^3-2*x^2+1)/( (1-2*x)*(1+x)*(1-x+x^2) ).
a(n)=2*a(n-1)-a(n-3)+2*a(n-4).
a(n+1) - 2*a(n) has period length 6: repeat 0, -2, 1, 0, 2, -1 (see A080425).
a(n) + a(n+3) = 3*2^n = A007283(n).
|
|
MAPLE
|
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;
|
|
MATHEMATICA
|
LinearRecurrence[{2, 0, -1, 2}, {1, 2, 2, 5}, 40] (* Harvey P. Dale, Feb 11 2015 *)
|
|
PROG
|
(Magma) I:=[1, 2, 2, 5]; [n le 4 select I[n] else 2*Self(n-1)-Self(n-3)+2*Self(n-4): n in [1..40]]; // Vincenzo Librandi, Jul 08 2016
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|