8
$\begingroup$

The problem is as in the question title. Only one addition - $n$ is not divisible by $5$.

I already have a solution involving permutations, but recently I read about generating functions and I was wondering if this problem can be solved with them.

A similar problem is the following: Find the number of all subsets of $\{1, 2, \ldots, 2015\}$ and the sum of elements in each subset is divisible by 5. The generating function used is $${((1+x^0)(1+x^1)(1+x^2)(1+x^3)(1+x^4))}^{403}.$$

But this function cannot be used for my problem, since we need to count how many elements have been "used" to make the subset. Can anyone help me?

$\endgroup$
11
+100
$\begingroup$

A generating function solution.

For every $S\subset\{1,2,\ldots,2015\}$ we will write $\Sigma S=\sum_{k\in S}k$.

Let $$ f(a,x) = \prod_{k=1}^{2015} (1+a^kx) = \sum_{S\subset\{1,\ldots,2015\}} a^{\Sigma S} x^{|S|}. $$ Take the average this function over putting $5$th complex roots of unity for $a$. Let $\omega=e^{2\pi i/5}$; then $$ \frac15\sum_{j=0}^4 f(\omega^j,x) = \sum_{S\subset\{1,\ldots,2015\}} \left(\frac15\sum_{j=0}^4 \big(\omega^{\Sigma S}\big)^j\right) x^{|S|} = \sum_{\substack{S\subset\{1,\ldots,2015\}\\\Sigma S\equiv0\pmod5}} x^{|S|}. \tag{$*$} $$ On the RHS of $(*)$, the coefficient of $x^n$ is the number of $n$-element sets $S\subset\{1,\ldots,2015\}$ with $\Sigma S\equiv0\pmod5$.

On the other hand, $$ f(\omega^j,x)= \begin{cases} (1+x)^{2015} & \text{if } j=0 \\ (1+x^5)^{403} & \text{if } j=1,2,3,4 \end{cases} $$ so on the LHS of $(*)$ the coefficient of $x^n$ is: $\frac15\binom{2015}n$ if $n$ is co-prime with $5$, and $\frac15\binom{2015}n+\frac45\binom{403}{n/5}$ if $5|n$.

$\endgroup$
  • $\begingroup$ Instructive and straight forward. Very nice! (+1) $\endgroup$ – Markus Scheuer Jan 23 '16 at 16:58
  • $\begingroup$ Definitely the answer I was looking for! Simple and well explained. $\endgroup$ – thefunkyjunky Jan 23 '16 at 19:59
  • $\begingroup$ @user141614 I will most likely award the bounty here. I have added a special case to my discussion so as not to create the impression that PET would not yield the formula you propose. This special case is when $q$ is a multiple of $k$ and $k$ is prime. You are cordially invited to consult these remarks. $\endgroup$ – Marko Riedel Jan 23 '16 at 23:15
4
$\begingroup$

This is a straightforward application of the Polya Enumeration Theorem. We treat the problem of subsets with $n$ elements of the set $\{1,2,\ldots, q\}$ whose sum is divisible by $k.$ Suppose $Z(P_n)$ is the cycle index of the set operator $\mathfrak{P}_{=n}$ given by the recurrence by Lovasz which is

$$Z(P_n) = \frac{1}{n} \sum_{l=1}^n (-1)^{l+1} a_l Z(P_{n-l}) \quad\text{where}\quad Z(P_0) = 1.$$

We obtain by PET the following formula for the OGF of ordinary sets

$$Z(P_n)\left(w+w^2+\cdots+w^q\right) = Z(P_n)\left(\sum_{m=1}^q w^m\right).$$

With $\rho$ a root of unity namely $$\rho = \exp(2\pi i/k)$$

we get for the desired count the value $$\frac{1}{k} \left.\sum_{p=0}^{k-1} Z(P_n)\left(\sum_{m=1}^q w^m\right)\right|_{w=\rho^p}.$$

We will compute the value for $p=0$ separately and to do this recall the OGF of the set operator $\mathfrak{P}_{=n}$ which is

$$Z(P_n) = [z^n] \exp\left(a_1 z - a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} - a_4 \frac{z^4}{4} +\cdots \right).$$

or

$$Z(P_n) = [z^n] \exp\left(\sum_{r\ge 1} (-1)^{r+1} a_r \frac{z^r}{r}\right).$$

On substituting this into our formula we get

$$\frac{1}{k} \sum_{p=0}^{k-1} \left. [z^n] \exp\left(\sum_{r\ge 1} (-1)^{r+1} \frac{z^r}{r} \sum_{m=1}^q w^{rm} \right) \right|_{w=\rho^p}.$$

When $p=0$ we obtain $$\frac{1}{k} [z^n] \exp\left(q\sum_{r\ge 1} (-1)^{r+1} \frac{z^r}{r}\right) = \frac{1}{k} [z^n] \exp\left(q \log (1+z)\right) \\ = \frac{1}{k} [z^n] (1+z)^q = \frac{1}{k} {q\choose n}.$$

We switch to algorithmics for the remainder of this discussion.

In treating the case $p\ge 1$ we make the following observation. When substituting into the terms of the cycle index those $a_r$ from the product where $pr$ is a multiple of $k$ produce the value $q$ while the remaining $a_r$ create a sequence of period $k$ that depends only on the remainder $b$ when $q$ is divided by $k$ where we take $1\le b\le k.$

This yields an algorithm where we iterate over the cycle index, extract eventual powers of $q$ from the terms and interpolate the rest in terms of $b.$ The algorithm can be used to compute formulae for fixed combinations of $n$ and $k$ like the ones at this MSE link automatically.

We obtain for $(n,k) = (3,3)$ $$1/18\,{q}^{3}+1/3\,{b}^{2}-1/6\,{q}^{2}-{\frac {11\,b}{9}}+q/3+2/3$$ and sure enough comparing it to the link these are the right values.

Supposing now that we are interested in divisibility by five of three-element subsets i.e. the pair $(n,k) = (3,5)$ we find

$$1/12\,{b}^{4}-{\frac {13\,{b}^{3}}{15}}+1/30\,{q}^{3}+{\frac { 181\,{b}^{2}}{60}}-1/10\,{q}^{2}-{\frac {127\,b}{30}}+q/15+2$$

which gives the sequence (starting at $q=3$)

$$0, 0, 2, 4, 7, 11, 16, 24, 33, 44, 57, 72, 91, \ldots$$

For the pair $(11,5)$ we obtain

$${\frac {{q}^{11}}{199584000}}-{\frac {{q}^{10}}{3628800}}+{ \frac {{q}^{9}}{151200}}-{\frac {11\,{q}^{8}}{120960}}+{\frac { 683\,{q}^{7}}{864000}}+{\frac {{b}^{4}{q}^{2}}{1200}}\\-{\frac { 781\,{q}^{6}}{172800}}-{\frac {{b}^{4}q}{80}}-{\frac {{b}^{3}{q }^{2}}{120}}+{\frac {31063\,{q}^{5}}{1814400}}+1/24\,{b}^{4}+1/ 8\,{b}^{3}q+{\frac {7\,{b}^{2}{q}^{2}}{240}}\\-{\frac {1529\,{q}^ {4}}{36288}}-{\frac {631\,{b}^{3}}{1500}}-{\frac {859\,{b}^{2}q }{2000}}-{\frac {137\,b{q}^{2}}{3000}}+{\frac {16103\,{q}^{3}}{ 252000}}+{\frac {863\,{b}^{2}}{600}}\\+{\frac {129\,bq}{200}}-{ \frac {419\,{q}^{2}}{12600}}-{\frac {25\,b}{12}}-{\frac {31\,q }{110}}+1$$

which gives the sequence (starting at $q=11$)

$$0, 2, 15, 72, 273, 873, 2474, 6363, 15114, 33592, \ldots.$$

Another interesting pair is $(3,6)$ which gives

$$-{\frac {{b}^{5}q}{90}}-{\frac {{b}^{5}}{90}}+{\frac {7\,{b}^{4 }q}{36}}+1/4\,{b}^{4}-{\frac {23\,{b}^{3}q}{18}}-2\,{b}^{3}+{ \frac {35\,{b}^{2}q}{9}}\\+1/36\,{q}^{3}+7\,{b}^{2}-{\frac {242\, bq}{45}}-1/12\,{q}^{2}-{\frac {313\,b}{30}}+{\frac {17\,q}{6}}+5$$

and $(4,7)$ which produces

$${\frac {{b}^{6}}{360}}-{\frac {3\,{b}^{5}}{40}}+{\frac {389\,{b }^{4}}{504}}+{\frac {{q}^{4}}{168}}-{\frac {215\,{b}^{3}}{56}}- 1/28\,{q}^{3}\\+{\frac {3041\,{b}^{2}}{315}}+{\frac {11\,{q}^{2} }{168}}-{\frac {403\,b}{35}}-q/28+5.$$

The Maple code for this including a total enumeration routine for verification and some code to prettify the formulae for $k$ small was as follows.

with(combinat);

pet_cycleind_set :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add((-1)^(l+1)*a[l]*pet_cycleind_set(n-l), l=1..n));
end;

pet_flatten_term :=
proc(varp)
local terml, d, cf, v;

    terml := [];

    cf := varp;
    for v in indets(varp) do
        d := degree(varp, v);
        terml := [op(terml), seq(v, k=1..d)];
        cf := cf/v^d;
    od;

    [cf, terml];
end;

V :=
proc(q, n, k)
    local comb, res;
    option remember;

    res := 0;
    comb := firstcomb(q, n);

    while type(comb, set) do
        if add(p, p in comb) mod k = 0 then
            res := res + 1;
        fi;

        comb := nextcomb(comb, q);
    od;

    res;
end;

CF :=
proc(n, k)
    local term, rho, res, p, flat, ixvar, rmd, m,
    rep, qpow, w, ex, vals, val;
    option remember;

    res := 0; rho := exp(2*Pi*I/k);

    for term in pet_cycleind_set(n) do
        flat := pet_flatten_term(term);

        for p to k-1 do
            vals := []; rep := []; qpow := 0;

            for ixvar in flat[2] do
                ex := p*op(1, ixvar);

                if ex mod k = 0 then
                    qpow := qpow + 1;
                else
                    rep := [op(rep), ixvar];
                fi;
            od;


            for rmd to k do
                val := 1;

                for ixvar in rep do
                    ex := p*op(1, ixvar);
                    val := val * add(w^(ex*m), m=1..rmd);
                od;

                vals :=
                [op(vals), subs(w=rho, expand(val))];
            od;

            res := res + flat[1]*q^qpow *
            interp([seq(b, b=1..k)], vals, b);
        od;
    od;

    binomial(q,n)/k + res/k;
end;

CFsimp :=
proc(n, k)
    local form, res, term, lcf, cnst;
    option remember;

    form := collect(expand(CF(n,k)), {b,q}, `distributed`);

    cnst := coeff(coeff(form, b, 0), q, 0);

    res := 0;

    for term in form-cnst do
        lcf := lcoeff(term);

        res := res +
        simplify(Re(lcf))*term/lcf;
    od;

    res + simplify(cnst);
end;

F :=
proc(qv, n, k)
local bv;

    if qv mod k = 0 then
        bv := k;
    else
        bv := qv mod k;
    fi;

    subs({q=qv, b=bv}, CFsimp(n,k));
end;

The reader is invited to contribute a better simplification routine making more effective use of the mathematical givens. The Maple code should be considered betaware.

Remark Sat Jan 23 2016. I present one of the special cases where radical simplification is possible. Start from the formula

$$\frac{1}{k} {q\choose n} + \frac{1}{k} \sum_{p=1}^{k-1} \left. [z^n] \exp\left(\sum_{r\ge 1} (-1)^{r+1} \frac{z^r}{r} \sum_{m=1}^q w^{rm} \right) \right|_{w=\rho^p}.$$

Now suppose that $q$ is a multiple of $k$ and $k$ is an odd prime. Observe that the sum $$\sum_{m=1}^q w^{rm}$$ is equal to $q/k\times k = q$ if $pr$ is a multiple of $k$ and zero otherwise. But $pr$ can only be a multiple of $k$ if $r$ is a multiple of $k.$ This yields

$$\frac{1}{k} {q\choose n} + \frac{1}{k} \sum_{p=1}^{k-1} \left. [z^n] \exp\left(\sum_{r\ge 1} (-1)^{kr+1} \frac{z^{kr}}{kr} \sum_{m=1}^q w^{krm} \right) \right|_{w=\rho^p} \\ = \frac{1}{k} {q\choose n} + \frac{1}{k} \sum_{p=1}^{k-1} \left. [z^n] \exp\left(\sum_{r\ge 1} (-1)^{kr+1} \frac{z^{kr}}{kr} \frac{q}{k}\times k \right) \right|_{w=\rho^p} \\ = \frac{1}{k} {q\choose n} + \frac{1}{k} \sum_{p=1}^{k-1} [z^n] \exp\left(\frac{q}{k} \sum_{r\ge 1} (-1)^{kr+1} \frac{z^{kr}}{r}\right) \\ = \frac{1}{k} {q\choose n} + \frac{1}{k} \sum_{p=1}^{k-1} [z^n] \exp\left(-\frac{q}{k} \sum_{r\ge 1} \frac{(-z)^{kr}}{r}\right) \\ = \frac{1}{k} {q\choose n} + \frac{1}{k} \sum_{p=1}^{k-1} [z^n] \exp\left(-\frac{q}{k} \log\frac{1}{1-(-z)^k}\right) \\ = \frac{1}{k} {q\choose n} + \frac{1}{k} \sum_{p=1}^{k-1} [z^n] (1+z^k)^{q/k}.$$

Therefore if $n$ is coprime to $k$ we obtain $$\frac{1}{k} {q\choose n}$$

and if it is a multiple of $k$

$$\frac{1}{k} {q\choose n} + \frac{k-1}{k} {q/k\choose n/k}.$$

$\endgroup$
  • $\begingroup$ Instructive approach! (+1) $\endgroup$ – Markus Scheuer Jan 24 '16 at 7:00
  • $\begingroup$ Thank you for the kind remark. What I have here is not as simple as it could be but it features a variant of the exponential formula which I present frequently in order to encourage its use. This formula is central to combinatorics, producing e.g. a variety of statistics on random permutations. $\endgroup$ – Marko Riedel Jan 24 '16 at 10:15
  • $\begingroup$ Your answers look indeed sometimes complicated. But, nevertheless most of them are worth to read and analyse it. I'm awaiting to see more of your applications of the exponential formula! :-) $\endgroup$ – Markus Scheuer Jan 24 '16 at 19:40
2
$\begingroup$

The answer is $\frac{1}{5}\binom{2015}{n}$.

For each subset of $n$ elements (not necessarily with sum multiple of $5$) consider the set of the $2015$ translations of the $n$-set. In other words, if we have $\{a_1,a_2\dots a_n\}$ Consider the family of sets of the form $\{r(a_1+k),r(a_2+k),\dots r(a_3+k)\}$ with $k\in\{0,1,\dots 2015\}$, and where $r(m)$ is simply the smallest positive integer congruent to $m\bmod 2015$.

It should be clear this splits the $n-sets$ into $\binom{2015}{n}/2015$ families, each containing $2015$ sets.

Moreover, the sum of the sets in the familiy of $\{a_1,a_2\dots a_{2015}\}$ are congruent to:

$S,S+n,S+2n,\dots ,S+2015n$, where $S=a_1+a_2+\dots + a_n$

Because $n$ is coprime with $5$ we deduce $\{S,S+n,S+2n\dots S+4n\}$ is a complete reside system $\bmod 5$, as well as $\{S+5n,S+6n,S+7n,S+8n, S+9n\}$ etcetera. Because of this, exactly $2015/5$ of the sets of each family have sums which are multiples of $5$. The result follows.

$\endgroup$
  • $\begingroup$ Thank you. The solution is interesting. But as I have said in my question, I'm interested whether the problem can be solved using generating functions. $\endgroup$ – thefunkyjunky Jan 19 '16 at 18:40

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.