5
$\begingroup$

I am struggling with the following problem: how many ways are there to add $N$ distinct, non-negative integers so that the result is $mN$, with $m$ an (odd) integer.

I have come accross some posts regarding the method of stars and bars (like this, this or this) but neither fits exactly this problem.

For example, for $m = N = 3$ we would have the following allowed possibilities:

$ (6 + 3 + 0), (6 + 2 + 1), (5 + 4 + 0), (5 + 3 + 1), (4 + 3 + 2) $

I am sorry if I have missed some post that is relevant for the question. Thank you in advance!

--- EDIT ---

Maybe I should have stated that I am not only interested in a closed formula (which, I am aware, may not exist), but that a recursive formula or even a (not too rough) estimate will also be very helpful.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

Following Hao Sun's advice, let us try to turn this problem into a partition problem.

Note that finding the number of $N$ distinct, nonnegative integers that add up to $m\cdot N$ is equivalent to finding the number of partitions of $(m+1) \cdot N$ that are comprised of $N$ distinct parts. This is because there is a natural bijection between the two. Namely, to get from $N$ distinct, nonnegative integers that up to $m \cdot N$ to a partition of $(m+1) \cdot N$ with $N$ distinct parts, just add one to all of the $N$ nonnegative integers.

For instance in your example of $m = 3, N = 3$, $(6,3,0)$ would turn into $(6+1,3+1,0+1)=(7,4,1)$ which we see is a partition of $(3+1)\cdot 3 = 12$ with $3$ distinct parts.

Note that the inverse of this function is just to subtract one from all of the parts.

So now we have turned our problem into counting partitions of $(m+1)\cdot N$ with $N$ distinct parts. Well this is the same as counting partitions of $M =(m+1)\cdot N - \binom{N}{2}$ with $N$ parts. We can see this by another bijection. Namely we take our partition of $(m+1)\cdot N$ with $N$ distinct parts and subtract $N-1$ from the largest part, $N-2$ from the second largest part, ... , $1$ from the second smallest part, and $0$ from the smallest part. This will give us a partition of $M$ with $N$ parts.

For example taking $m = 3, N=3$, we saw that $(7,4,1)$ was a partition of $12$ with $3$ distinct parts. Under our map this would turn into the partition $(7-2,4-1,1-0)=(5,3,1)$ which is a partition of $(3+1) \cdot 3 - \binom{3}{2} = 9$ with $3$ parts. Note that the parts of the resulting partition need not be distinct. For instance the partition $(9,2,1)$ would get sent to $(7,1,1)$.

Therefore we just need to count how many partitions of $M$ with $N$ parts are there. This is the same as counting the number of partitions of $M$ where the largest part has size $N$. I'll leave the bijection or proof of this for you to think about.

The number of partitions of $M$ with largest part equal to $N$ is precisely the coefficient of $x^{M}$ in the generating function $$x^{N}\cdot \prod_{i=1}^{N} \frac{1}{1-x^{i}}$$ which can be found in the Wiki link of partitions that Hao Sun posted.

Mark Haiman has a nice PDF on partitions that covers part of what I detailed above: https://math.berkeley.edu/~mhaiman/math172-spring10/partitions.pdf

$\endgroup$
0
$\begingroup$

have you looked into the theory of partitions? http://mathworld.wolfram.com/Partition.html https://onlinelibrary.wiley.com/doi/abs/10.1002/zamm.19790590632 https://artofproblemsolving.com/wiki/index.php/Partition_(combinatorics) https://en.wikipedia.org/wiki/Partition_(number_theory)#Odd_parts_and_distinct_parts Also have you looked at generating functions https://www.math.upenn.edu/~wilf/gfology2.pdf pg 105 talks a abit about partitions as well edit I realized you asked for distinct parts theres a nice theorem about odd partition = distinct partition https://en.wikipedia.org/wiki/Glaisher%27s_theorem

$\endgroup$
2
  • 1
    $\begingroup$ Note that the asker is looking for distinct integers, while partitions can be made of nondistinct integers. $\endgroup$
    – Jam
    Jul 26, 2019 at 21:16
  • $\begingroup$ Maybe I should have stated that I am not only interested in a closed formula (which, I am aware, may not exist), but that a recursive formula or even a (not too rough) estimate will also be very helpful. I will edit the post now. $\endgroup$ Jul 26, 2019 at 21:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .