A068010 Number of subsets of {1,2,3,...,n} that sum to 0 mod 3.
1, 1, 2, 4, 6, 12, 24, 44, 88, 176, 344, 688, 1376, 2736, 5472, 10944, 21856, 43712, 87424, 174784, 349568, 699136, 1398144, 2796288, 5592576, 11184896, 22369792, 44739584, 89478656, 178957312, 357914624, 715828224, 1431656448, 2863312896
Offset: 0
Examples
a(4)=6 because we have: {}, {3}, {1,2}, {2,4}, {1,2,3}, {2,3,4}. - _Geoffrey Critzer_, Jan 18 2014
Links
- Charles R Greathouse IV, Table of n, a(n) for n = 0..3323
- Sophie LeBlanc, Jan 20 2002, sci.math posting
- Index entries for linear recurrences with constant coefficients, signature (2,0,2,-4).
Programs
-
Maple
A068010 := n -> (2^n + 2^((n + 1 + (4/sqrt(3))*cos(((4*n)+1)*Pi/6))/3))/3;
-
Mathematica
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 *) -
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
Formula
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.
a(n) = (2^n + 2^((n + 1 + (4/sqrt(3))*cos(((4*n)+1)*Pi/6))/3))/3. - Fred Galvin
G.f.: (1-x-2*x^3)/(1-2*x-2*x^3+4*x^4). - Colin Barker, Feb 03 2012
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
Comments