1
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.