0
$\begingroup$

We are given constants $m$ and $n$. How many non-negative integer solutions are there for $2x_0+\sum_{i=1}^{m}{x_i}=n$ satisfying the condition that$x_i\neq x_j$ if $i\neq j$?

I thought a good first step might be to get the number of solutions for $\sum_{i=0}^{m}{x_i}=n$ where $x_i\neq x_j$ if $i\neq j$ and all $x_i\geq 0$, but even that seems difficult.

$\endgroup$
15
  • $\begingroup$ Is it allowed for $x_0=x_2$? $\endgroup$ – David P Jan 24 '16 at 5:37
  • 1
    $\begingroup$ A distinct solution does not mean a solution where all the elements are distinct. Are you adding that condition yourself, or is it explicitly stated in the problem? $\endgroup$ – Aaron Jan 24 '16 at 5:37
  • $\begingroup$ Is $m$ fixed? It really helps if you give the exact statement of a problem, and make clear what is your interpretation, because I agree with Aaron that I think you are misreading what is meant by a distinct solution. $\endgroup$ – Thomas Andrews Jan 24 '16 at 5:40
  • 1
    $\begingroup$ What you wrote does not exclude $x_0=x_2$. For example, $1\neq 2 \neq1$ is a true statement. You want to say $x_i\neq x_j$ if $i\neq j$. $\endgroup$ – David P Jan 24 '16 at 5:49
  • 1
    $\begingroup$ In that case, there is no harm in assuming that $x_1<x_2<\cdots<x_n$, as the total number of solutions will be $n!$ times the number where they are normalized. $\endgroup$ – Aaron Jan 24 '16 at 5:50
1
$\begingroup$

Here is a different approach to the problem than my other answer, which tries to set up a recurrence relation directly instead of passing through unordered partitions and young diagrams.

The trick is to subdivide the set of solutions into pieces that can be better analyzed. To that end, let us define several functions.

  • Let $f(m,n)$ be the number of solutions of the equation.
  • Let $g(m,n,k)$ be the number of solutions where $\min_i x_i =k$ and where the minimum is achieved by some $x_i$ with $i\neq 0$.
  • Let $h(m,n,k)$ be the number of solutions where $\min_i x_i =k$ and where the minimum is achieved by $x_0$.
  • Let $\rho(m,n)$ be the number of non-negative solutions to $\sum_{i=1}^m x_i= n$ with all variables taking on different numbers.

We have that $f(m,n)=\sum_{i\geq 0} g(m,n,i)+h(m,n,i)$. Additionally, by taking a solution contribution to $g(m,n,i)$ or $h(m,n,i)$ and subtracting $i$ from every variable, we have $g(m,n,i)=g(m,n-(m+2)i,0)$ and $h(m,n,i)=h(m,n-(m+2)i,0)$.

Further, given a solution where one of the variables is equal to zero, we can eliminate that variable (shifting the variable indexes down by one for every variable whose index was higher than the eliminated variable, assuming we are not in a solution where $x_0=0$) to get solutions with one fewer variable where every element is positive, and subtract one from every variable to get solutions to a different equation where every element is non-negative. Thus, we have

$$g(m,n,0)=mf(m-1,n-(m+1)) \qquad h(m,n,0)=\rho(m,n-m).$$

Putting everything together, we have

$f(m,n)=\sum_{i\geq 0}g(m,n-(m+2)i,0)+h(m,n-(m+2)i,0)=\sum_{i\geq 0}mf(m-1,n+1-(m+2)(i+1))+\rho(m,n+2-(m+2)(i+1))$

Using this recurrence, plus a similar one for $\rho$, a computer can easily compute $f(m,n)$ for any reasonably sized $m$ and $n$. It may also be feasible to find a generating function for $f$. However, I do not believe that there will be any nice closed form of $f$. For example, $f(1,n)$ will be $\lceil \frac{n+1}{2} \rceil-1_{n\equiv 0 \pmod{3}}$

$\endgroup$
0
$\begingroup$

Here is a sketch for how to solve the problem. It is not complete, and yields a solution only in terms of the number of partitions into at most a fixed number of parts, but it gives at least one useful way to think about the problem.

If we denote the number in question by $f(m,n)$, then $f(m,n)/n!$ is the number of partitions of $n$ into $m+2$ non-negative parts so that all but two of the parts have different sizes. We will consider three cases: all the parts are nonzero, the repeated part is zero, and a non-repeated part is zero. We will consider only the first case below. The third case reduces to the first, and the second is similar but simpler.

Let $g(m,n)$ be the collection of partitions of $n$ into an unordered sum of $m+2$ elements with exactly on repetition, and let $\lambda\in g(m,n)$ Drawing the corresponding Young diagram of $\lambda$ and taking the dual, we see that $\lambda^*$ is a partition of $n$ into an unspecified number of parts such that every part size is in the set $\{1, 2, \ldots, m+2\}$,and all but one of the sizes appears with positive multiplicity (while exactly one size does not appear). Let $k$ be the number which does not appear in $\lambda^*$. Subtracting $1$ from the multiplicity of every element in the partition, we get a new partition $\mu$ with the following properties:

  • No element in the partition is greater than $m+2$
  • $k$ appears with multiplicity zero,
  • $|\mu|=n+k-\frac{(m+2)(m+3)}{2}$.

Moreover, we see that starting from ordered pairs $(\mu,k)$ satisfying these properties, we can work backwards, adding $1$ to the multiplicities (except for $k$) and taking the dual, and so we have reduced the problem to finding the number of partitions of $x$ into parts of size at most $y$ with no parts of size $k$. This is equal to the number of partitions of $x$ into parts of size at most $y$ minus the number of partitions of $x-k$ into parts of size at most $y$.

Assuming you are comfortable expressing your answer in terms of this bounded partition function (whose closed form I do not know, but which has a very simple generating function), the problem is essentially solved. If not, I am not sure if the solution can be simplified to something that has a nicer closed form.

$\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.