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

1, 1, 1, 2, 3, 6, 12, 22, 44, 88, 172, 344, 688, 1368, 2736, 5472, 10928, 21856, 43712, 87392, 174784, 349568, 699072, 1398144, 2796288, 5592448, 11184896, 22369792, 44739328, 89478656, 178957312, 357914112, 715828224, 1431656448, 2863311872, 5726623744

Offset

0,4

Links

David A. Corneth, Table of n, a(n) for n = 0..2000

Formula

Empirical g.f.: (x-1)*(2*x^4+3*x^3+x^2-1) / ((2*x-1)*(2*x^3-1)). - Colin Barker, Dec 22 2012

From David A. Corneth, Sep 13 2025: (Start)

Conjecture: a(n) = 2*a(n-1) for n > 2 and 3 does not divide n-1.

a(3*k+1) = 2*a(3*k) - 2^(k-1), k >= 1, 3*k + 1 = n.

This conjecture holds for 1 <= n <= 2000.

If this conjecture is true then a(3*k + 1 + r) = ((2*4^k - 2)/3 + 1)*2^(k-1+r) where k >= 1 and r in {0, 1, 2}.

(End)

Maple

b:= proc(n, s) option remember; `if`(n=0, `if`(s=0, 1, 0),
      b(n-1, s)+b(n-1, irem(s+n, 6)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..35);  # Alois P. Heinz, May 02 2025

Mathematica

b[n_, s_] := b[n, s] = If[n == 0, If[s == 0, 1, 0], b[n-1, s] + b[n-1, Mod[s+n, 6]]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Sep 04 2025, after Alois P. Heinz *)

Crossrefs

6th row of A068009.

Sequence in context: A371793 A355850 A363582 * A261930 A019138 A154324

Adjacent sequences: A068009 A068010 A068011 * A068013 A068014 A068015

Keyword

nonn

Author

Antti Karttunen, Feb 11 2002

Status

approved