login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.

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.

The main diagonal in the table above is A001045, the adjacent upper diagonals are A078008, A048573 and A062092. (End)

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) - A083322(n-1) = A010892(n-1) 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 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

Cf. A083322.

Sequence in context: A247354 A317877 A075125 * A243338 A245306 A296530

Adjacent sequences:  A081371 A081372 A081373 * A081375 A081376 A081377

KEYWORD

nonn

AUTHOR

David Applegate, Aug 22 2003

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 16 04:19 EST 2018. Contains 318158 sequences. (Running on oeis4.)