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

Author

Antti Karttunen, Feb 11 2002

Keywords

• nonn

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.

Crossrefs

9th row of A068009.

Programs

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

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