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

1, 1, 1, 1, 2, 4, 8, 15, 30, 60, 116, 230, 458, 912, 1824, 3648, 7286, 14572, 29144, 58264, 116524, 233044, 466048, 932096, 1864192, 3728300, 7456600, 14913200, 29826224, 59652440, 119304872, 238609408, 477218816, 954437632, 1908874584

Offset

0,5

Links

Robert Israel, Table of n, a(n) for n = 0..3321

Mathematics StackExchange, Let S = 1,2,3,4,...,2070 find the number of subsets of S whose sum of elements in S is divisible by 9

Robert Israel, Proof of conjectured g.f.

Formula

Empirical G.f.: -(4*x^12-2*x^9-x^7+2*x^6+2*x^5+2*x^4-3*x^3-x^2-x+1) / ((2*x-1)*(2*x^3-1)*(2*x^9-1)). [Colin Barker, Dec 22 2012]

Empirical G.f. verified: see link. - Robert Israel, Apr 30 2019

Maple

G:= Array(0..100, 0..8):
G[0, 0]:= 1; for j from 1 to 8 do G[0, j]:= 0 od:
for n from 1 to 100 do
  for j from 0 to 8 do
     k:= j - n mod 9;
     G[n, j]:= G[n-1, j] + G[n-1, k];
od od:
seq(G[n, 0], n=0..100); # Robert Israel, Apr 30 2019

Crossrefs

9th row of A068009.

Sequence in context: A189101 A018089 A124312 * A251707 A251712 A251742

Adjacent sequences: A068027 A068028 A068029 * A068031 A068032 A068033

Keyword

nonn

Author

Antti Karttunen, Feb 11 2002

Status

approved