

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.


4



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
(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.
Contribution from Paul Curtz, May 26 2011: (Start)
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(n1), n>=2.
The main diagonal in the table above is A001045, the adjacent upper diagonals are A078008, A048573 and A062092. (End)


LINKS

Table of n, a(n) for n=1..31.
Index to sequences with linear recurrences with constant coefficients, signature (2,0,1,2).


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^32*x^2+1)/( (12*x)*(1+x)*(1x+x^2) ).
a(n)=2*a(n1)a(n3)+2*a(n4).
From Paul Curtz, May 26 2011: (Start)
a(n+1)  2*a(n) has period length 6: repeat 0, 2, 1, 0, 2, 1 (see A080425).
a(n)  A083322(n1) = A010892(n1) has period length 6.
a(n) + a(n+3) = 3*2^n = A007283(n).
a(n+6)a(n) = 21*2^n = A175805(n).
a(n)  A131708(n) = A131531(n). (End)


MAPLE

hatwork := proc(n, i, covered) local val, val2; options remember;
# computes the minimum cover of the ibit through nbit words.
# if covered is true the ibit words are already covered (by the (i1)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 ibit words in the cover
val := hatwork(n, i+1, true) + binomial(n, i);
# the other choice is not to include the ibit words in the cover
if (covered) then val2 := hatwork (n, i+1, false); if (val2 < val) then val := val2; fi; else
# if the ibit words were not covered by (i1), 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;


CROSSREFS

Cf. A083322.
Sequence in context: A223062 A208788 A075125 * A117400 A005637 A233018
Adjacent sequences: A081371 A081372 A081373 * A081375 A081376 A081377


KEYWORD

nonn


AUTHOR

David Applegate, Aug 22 2003


STATUS

approved



