A068010 - OEIS

%I #28 Mar 27 2017 10:58:29

%S 1,1,2,4,6,12,24,44,88,176,344,688,1376,2736,5472,10944,21856,43712,

%T 87424,174784,349568,699136,1398144,2796288,5592576,11184896,22369792,

%U 44739584,89478656,178957312,357914624,715828224,1431656448,2863312896

%N Number of subsets of {1,2,3,...,n} that sum to 0 mod 3.

%C Third row of A068009.

%H Charles R Greathouse IV, <a href="/A068010/b068010.txt">Table of n, a(n) for n = 0..3323</a>

%H Sophie LeBlanc, Jan 20 2002, <a href="http://groups.google.com/groups?hl=en&amp;selm=85962b5a.0201201247.4aa79c5c%40posting.google.com">sci.math posting</a>

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

%F a(0)=1, a(1)=1, a(n) = 2*a(n-1) if 3 does not divide n-1 and a(n) = 2*a(n-1)-(2^((n-1)/3)) if 3 divides n-1.

%F a(n) = (2^n + 2^((n + 1 + (4/sqrt(3))*cos(((4*n)+1)*Pi/6))/3))/3. - Fred Galvin

%F G.f.: (1-x-2*x^3)/(1-2*x-2*x^3+4*x^4). - _Colin Barker_, Feb 03 2012

%F a(0)=1, a(1)=1, a(2)=2, a(n) = 2*a(n-3) + 2^(n - 2), n>=3. - _Baris Arslan_, Mar 27 2017

%e a(4)=6 because we have: {}, {3}, {1,2}, {2,4}, {1,2,3}, {2,3,4}. - _Geoffrey Critzer_, Jan 18 2014

%p A068010 := n -> (2^n + 2^((n + 1 + (4/sqrt(3))*cos(((4*n)+1)*Pi/6))/3))/3;

%t Table[nn=(n^2+n)/2;Total[Table[Coefficient[Series[Product[1+x^i,{i,1,n}],{x,0,nn}],x^(3k)],{k,1,nn}]]+1,{n,1,33}] (* _Geoffrey Critzer_, Jan 18 2014 *)

%o (PARI) a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; -4,2,0,2]^n*[1;1;2;4])[1,1] \\ _Charles R Greathouse IV_, Mar 27 2017

%K nonn,easy

%O 0,3

%A _Antti Karttunen_, Feb 11 2002