# counting 11-element subsets of {1, 2, …, n} with sum divisible by 5

What possibly easy ways are there to count the number of subsets of $\{1, 2, ..., n\}$ with $11$ elements, sum of which is divisible by $5$?

I started with making smaller subsets out of $\{6, 7, ..., n\}$ and then adding the remainder-correcting number(s) from $\{1, 2, 3, 4, 5\}$, but this approach leads to complications of its own. So any idea?

• I assume for large $n$ the value is close to $\frac{n\choose{11}}{5}$ – Guy May 29 '17 at 12:30
• There was an extensive discussion of this problem with different users participating at the following MSE link. – Marko Riedel May 29 '17 at 21:05
• @Guy Yeah I agree. Is the formula generally true for when n is a multiple of 5? – Sajad May 30 '17 at 7:17
• @Sajad if you follow the link Marko posted, you will find the exact formulas for $(5,n)=1$ and $5|n$ – Guy May 30 '17 at 10:39

Consider the function $$f(x,t)=\prod_{i=1}^n(1+xt^n).$$ The $x^at^b$ coefficient here is the number of $a$-element subsets of $\{1,\ldots,n\}$ with sum $b$. To sieve out those sets which are multiples of $5$ consider $$g(x)=\frac{f(x,1)+f(x,\zeta)+f(x,\zeta^2)+f(x,\zeta^3)+f(x,\zeta^4)}5$$ with $\zeta=\exp(2\pi i/5)$. The coefficient of $x^a$ in $g(x)$ is the number of $a$ element subsets of $\{1,\ldots,n\}$ which sum to a multiple of $5$.
Obviously $$f(x,1)=(1+x)^n.$$ If $n=5r+q$ with $0\le q\le1$ then $$f(x,\zeta^k)=(1+x^5)^r\prod_{j=1}^q(1+x\zeta^k)$$ for $k\in\{1,2,3,4\}$. You'll need to treat the values of $q$ individually.