A081374 - OEIS

%I #25 Sep 08 2022 08:45:09

%S 1,2,2,5,10,22,43,86,170,341,682,1366,2731,5462,10922,21845,43690,

%T 87382,174763,349526,699050,1398101,2796202,5592406,11184811,22369622,

%U 44739242,89478485,178956970,357913942,715827883,1431655766,2863311530,5726623061

%N 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.

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

%C From _Paul Curtz_, May 26 2011: (Start)

%C If we add a(0)=1 in front and build the table of a(n) and iterated differences in further rows we get:

%C 1,    1,  2,  2,  5, 10,

%C 0,    1,  0,  3,  5, 12,

%C 1,   -1,  3,  2,  7,  9,

%C -2,   4, -1,  5,  2, 13,

%C 6,   -5,  6, -3, 11,  6

%C -11, 11, -9, 14, -5, 21.

%C The first column is the inverse binomial transform, which is 1,0 followed by (-1)^n*A083322(n-1), n>=2.

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

%H Vincenzo Librandi, <a href="/A081374/b081374.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1,2).

%F 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;

%F G.f.: x*(2*x^3-2*x^2+1)/( (1-2*x)*(1+x)*(1-x+x^2) ).

%F a(n)=2*a(n-1)-a(n-3)+2*a(n-4).

%F From _Paul Curtz_, May 26 2011: (Start)

%F a(n+1) - 2*a(n) has period length 6: repeat 0, -2, 1, 0, 2, -1 (see A080425).

%F a(n) - A083322(n-1) = A010892(n-1) has period length 6.

%F a(n) + a(n+3) = 3*2^n = A007283(n).

%F a(n+6)-a(n) = 21*2^n = A175805(n).

%F a(n) - A131708(n) = -A131531(n).  (End)

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

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

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

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

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

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

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

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

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

%p 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;

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

%t LinearRecurrence[{2,0,-1,2},{1,2,2,5},40] (* _Harvey P. Dale_, Feb 11 2015 *)

%o (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

%Y Cf. A083322.

%K nonn

%O 1,2

%A _David Applegate_, Aug 22 2003