3
$\begingroup$

Lets say we had a $k,m,n \in \mathbb{N}$ where $k < m \le n$. How many different sets $X_1,..,X_m$ with $|X_i|=k$ for $i=1,..,m$, where the sets do not include duplicates, for which the sum of their elements is equal to n?

$$n = X_{sum}^i := \sum_{j=1}^k x_j^i, \; x_j^i \in X_i$$

It holds, that all elements $x_j^i \le m$ and for each pair $|X_i \cap X_j| < k$, where $i=1,..,m$ and $j=1,..,m$ but $i\neq j$.

As example, we take $k=3$, $n=15$ and show all possibilities for m:

m = 6 : 6+5+4                (1)
m = 7 : 7+5+3, 7+6+2         (2)
m = 8 : 8+4+3, 8+5+2, 8+6+1  (3)
m = 9 : 9+4+2, 9+5+1         (2)
m = 10: 10+3+2, 10+4+1       (2)
m = 11: 11+3+1               (1)
m = 12: 12+2+1               (1)

Is there a general formula to calculate this values for $n,k,m$ or at least for $k=3$?

Finally my goal was if $C_{n,k,m}$ is the count of the values, the calculation of

$$C_{n,k} = \sum_{i=1}^n (C_{n,k,i} - 1).$$

I found out a formula for $C_{n,2}$ which was:

$$C_{n,2} = {n - 2 \choose 2},$$

but I was not able to generalize it for k, since it does not hold, that

$$C_{n,k} = {n - 2 \choose k},$$

for all k.

$\endgroup$
4
  • $\begingroup$ Just to be sure: is what you are looking for the number of partitions of $n$ into $k$ distinct parts, with largest part equal to $m$? $\endgroup$ Jul 17, 2014 at 12:30
  • $\begingroup$ I would say yes, just have a look at the example, here all m's are listed. But for my calculation, m is for example set to 10, which means, that the total sum is 10 instead of 12. $\endgroup$
    – Alex VII
    Jul 17, 2014 at 20:22
  • $\begingroup$ The answer to "How many different sets $X_1, \ldots, X_m$...?" would seem to be $m$... $\endgroup$ Jul 18, 2014 at 13:56
  • $\begingroup$ Very useful paper, though this gives a good approximation to the number of partitions of $n$ into exactly $k$ parts each no larger than $N$ due to Ratsaby (App. Analysis and Discrete M. 2008): doiserbia.nb.rs/img/doi/1452-8630/2008/1452-86300802222R.pdf $\endgroup$
    – apkg
    Jun 18, 2016 at 15:41

1 Answer 1

4
+100
$\begingroup$

I'm assuming from your list of examples that what you are looking for is the number of partitions of $n$ into $k$ distinct parts with largest part equal to $m$ (this is different from the question in the title, but seems to fit your examples best).

The number of partitions of $n$ with at most $k$ parts, each of length at most $m$, is the coefficient of $q^n$ in the Gaussian binomial coefficient $\binom{m+k}{k}_q$. To have only those with exactly $k$ parts, one of which is exactly of length $m$, we first get rid of all partitions in $k-1$ parts or less, and then of all those whose largest part is at most $m-1$, and add back those in at most $k-1$ parts of length at most $m-1$, which we have deleted twice. This number is then the coefficient of $q^n$ in $$\binom{m+k}{k}_q -\binom{m+k-1}{k}_q - \binom{m+k-1}{k-1}_q + \binom{m+k-2}{k-1}_q.$$

Now, we want partitions of $n$ having these conditions and having distinct parts. The trick here is to see that such partitions are in bijection with partitions of $n-\binom{k}{2}$ with exactly $k$ (not necessarily distinct) parts and largest part of length $m-k+1$. This trick is explained for instance in this answer.

Therefore, the number you are looking for is the coefficient of $q^{n-\binom{k}{2}}$ in $$\binom{m+1}{k}_q -\binom{m}{k}_q - \binom{m}{k-1}_q + \binom{m-1}{k-1}_q.$$

In the particular example where $m=12$ and $k=3$, this expression is the polynomial $$q^{30} + q^{29} + 2q^{28} + 2q^{27} + 3q^{26} + 3q^{25} + 4q^{24} + 4q^{23} + 5q^{22} + 5q^{21} + 5q^{20} + 4q^{19} + 4q^{18} + 3q^{17} + 3q^{16} + 2q^{15} + 2q^{14} + q^{13} + q^{12},$$

so for $n=15$, you look at the coefficient in front of $q^{15-\binom{k}{2}} = q^{12}$, which is $1$ as expected. For $n=23$, you would take the coefficient in front of $q^{20}$, which is $5$; this corresponds to the five partitions $12+10+1 = 12+9+2 = 12+8+3 = 12+7+4 = 12+6+5$.

$\endgroup$
2
  • $\begingroup$ This looks quite good. Can you please explain the formular with my example? Let's say k=3 and m=12. $\endgroup$
    – Alex VII
    Jul 18, 2014 at 15:32
  • $\begingroup$ I've added the example. $\endgroup$ Jul 18, 2014 at 16:08

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.