A068011 Number of subsets of {1,2,3,...,n} that sum to 0 mod 5.
1, 1, 1, 2, 4, 8, 14, 26, 52, 104, 208, 412, 820, 1640, 3280, 6560, 13112, 26216, 52432, 104864, 209728, 419440, 838864, 1677728, 3355456, 6710912, 13421792, 26843552, 53687104, 107374208, 214748416, 429496768, 858993472, 1717986944, 3435973888, 6871947776
Offset: 0
Keywords
Links
- Sophie LeBlanc, Jan 20 2002, sci.math posting
- Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,2,-4).
Crossrefs
5th row of A068009.
Programs
-
Maple
A068011_rec := proc(n); if(0 = n) then RETURN(1); fi; if(1 = (n mod 5)) then RETURN(2*A068011_rec(n-1)-2^((n-1)/5)); fi; if(2 = (n mod 5)) then RETURN(2*A068011_rec(n-1)-2^((n-2)/5)); fi; RETURN(2*A068011_rec(n-1)); end; # second Maple program: b:= proc(n, s) option remember; `if`(n=0, `if`(s=0, 1, 0), b(n-1, s)+b(n-1, irem(s+n, 5))) end: a:= n-> b(n, 0): seq(a(n), n=0..35); # Alois P. Heinz, May 02 2025
-
Mathematica
LinearRecurrence[{2, 0, 0, 0, 2, -4}, {1, 1, 1, 2, 4, 8}, 40] (* Jean-François Alcover, Mar 06 2016 *)
Formula
a(k+1) = 2*a(k) if k == 2, 3, or 4 mod 5, 2*a(k)-2^(k/5) if k == 0 mod 5, 2*a(k)-2^((k-1)/5) if k == 1 mod 5.
G.f.: -(x^2-x+1)*(2*x^3+2*x^2-1) / ((2*x-1)*(2*x^5-1)). - Colin Barker, Dec 22 2012
If n == 0 mod 5, then a(n) = (2^n + 4*2^(n/5))/5. - Giorgos Kalogeropoulos, May 02 2025
a(n) ~ 2^n/5. - Stefano Spezia, May 02 2025
Comments