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,3

Comments

Third row of A068009.

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).

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

Example

a(4)=6 because we have: {}, {3}, {1,2}, {2,4}, {1,2,3}, {2,3,4}. - Geoffrey Critzer, Jan 18 2014

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 *)

Prog

(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

Crossrefs

Sequence in context: A244896 A048115 A047151 * A375438 A095848 A208767

Adjacent sequences: A068007 A068008 A068009 * A068011 A068012 A068013

Keyword

nonn,easy

Author

Antti Karttunen, Feb 11 2002

Status

approved