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.
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(n-1), n>=2.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for 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^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).
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) + a(n+3) = 3*2^n = A007283(n).
a(n+6)-a(n) = 21*2^n = A175805(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
David Applegate, Aug 22 2003
STATUS
approved