10

I have invented a little exercise of combinatorics that I can't solve (without brute forcing): in how many ways can I choose 4 non-negative integers, the sum of which is 100 and they are all different? So:

$x_1+x_2+x_3+x_4=100$

$x_1, x_2, x_3, x_4 \in \mathbb N$

$x_1 \neq x_2 \neq x_3 \neq x_4$

I have thought that the result have to be the number of total combination $\binom {100 + 4 - 1} {4 - 1}$ minus the ways I can solve $2x_1 + x_2 + x_3 = 100$. Anyway, I am not able to solve it either.

The solution should be:

161664 or $\binom {100 + 4 - 1} {4 - 1} - 15187 = 176851 - 15187 = 161664$

Does anyone know how to calculate the combinations of this problem?

untitled
  • 269

3 Answers3

8

Here is a solution with generating functions. Let $a_n$ be the number of objects you wish to count, namely the ordered quadruples of distinct non-negative integers with a sum of $n$, and let $f(x)=\sum_{n\ge0}a_nx^n$ be the ordinary generating function of this sequence. Since the integers in the sum are distinct, this generating function must be $$f(x)=\left[\frac{y^4}{4!}\right]\prod_{n\ge0}(1+yx^n).$$ Then the problem of computing $a_n$ is reduced to finding the coefficient $[x^n]f(x)$. You can do this with standard techniques, but it does take some persistence! The result is an explicit formula for $a_n$, and in particular for $a_{100}$, as requested.

First, since sums are more familiar to me than products, I'll change the product to a sum by way of exponentials and logarithms: $$f(x)=\left[\frac{y^4}{4!}\right]\exp\bigl(\sum_{n\ge0}\log(1+yx^n)\bigr).$$ Since we'll eventually extract the coefficient of $y^4$, we can expand the logarithm in its Taylor series up through the 4-th order powers of $y$, using $\log(1+t)\approx t-\frac12t^2+\frac13t^3-\frac14t^4$, and then sum the resulting geometric series: \begin{eqnarray*} % \nonumber to remove numbering (before each equation) f(x) &=& \left[\frac{y^4}{4!}\right]\exp\bigl(\sum_{n\ge0}yx^i-\frac12y^2x^{2i}+\frac13y^3x^{3i}-\frac14y^4x^{4i} \bigr)\\ &=& \left[\frac{y^4}{4!}\right]\exp\bigl(\frac y{1-x}-\frac12\,\frac{y^2}{1-x^2}+\frac13\,\frac{y^3}{1-x^3}-\frac14\,\frac{y^4}{1-x^4}\bigr). \end{eqnarray*} At this stage, it's slightly easier to replace the exponential of the sum with the product of the exponentials. Then we'll expand each exponential in its Taylor series (again through the 4-th order powers of $y$), using $\exp(t)\approx1+t+\frac12t^2+\frac1{3!}t^3+\frac1{4!}t^4$: \begin{eqnarray*} % \nonumber to remove numbering (before each equation) f(x) &=& \left[\frac{y^4}{4!}\right]\exp\bigl(\frac y{1-x}\bigr) \exp\bigl(-\frac12\frac{y^2}{1-x^2}\bigr) \exp\bigl(\frac13\frac{y^3}{1-x^3}\bigr) \exp\bigl(-\frac14\frac{y^4}{1-x^4}\bigr) \\ &=& \left[\frac{y^4}{4!}\right]\left( 1+\frac y{1-x}+ \frac12\frac{y^2}{(1-x)^2}+ \frac16\frac{y^3}{(1-x)^3}+\frac1{24}\frac{y^4}{(1-x)^4}\right)\times\\ &&\quad \left( 1-\frac12\,\frac{y^2}{1-x^2}+\frac18\frac{y^4}{(1-x^2)^2}\right) \times\left( 1+\frac13\,\frac{y^3}{1-x^3}\right) \times\left( 1-\frac14\,\frac{y^4}{1-x^4}\right) . \end{eqnarray*} In the expansion of this product, there are just five terms with a coefficient of $y^4$, so $$ f(x)=\frac 8{(1-x)(1-x^3)}-\frac6{(1-x)^2(1-x^2)} +\frac1{(1-x)^4}+\frac3{(1-x^2)^2}-\frac6{1-x^4}.$$ Using basic facts about series expansions of rational functions, it is straightforward to compute the coefficient of $x^n$ in each of the five terms, resulting in \begin{eqnarray*} % \nonumber to remove numbering (before each equation) a_n &=&[x^n]f(x) \\ &=& 8\left(\lfloor n/3\rfloor+1\right) -\frac32\bigl(\{1\text{ if }2|n\}+ (n+3)(n+1)\bigr)+\\ &&\frac{(n+3)(n+2)(n+1)}{6}+3\left\{n/2+1\text{ if } 2|n\right\}-6\left\{1\text{ if }4|n\right\}. \end{eqnarray*} As in other calculations, this gives $a_{100}=161\,664$.

Rus May
  • 2,087
4

This can be solved by inclusion/exclusion. Define $X_{ij}$ to be the set of solutions to this equation which have $x_i=x_j$, where $\{i,j\}$ varies over the six 2-element subsets of $\{1 \ldots 4\}$. As the OP mentions, the number of solutions to this problem without any restrictions on the $x_i$'s is $103 \choose 3$. To calculate $|X_{ij}|$, $i \ne j$, note that the sum $x_i + x_j = 2x_i$, can be any even number in $\{0, 2, \ldots, 100\}$. Once that sum $s$ is chosen, there are $101-s$ solutions in $X_{ij}$ having $x_i+x_j=s$, namely where the remaining two variables $x_k$ and $x_\ell$ vary over $\{(0,100-s), (1,99-s), \ldots (100-s,0)\}$. So we have $$|X_{ij}| = \displaystyle\sum_{i=0}^{50} (101-2i) = 101\times51 - 2\times\frac{50\times51}{2}=2601$$

To continue with inclusion/exclusion, we need to calculate $|X_{ij} \cap X_{k\ell}|$. There are ${6 \choose 2} = 15$ such intersections. Of these exactly 3 have all of $i, j, k, \ell$ distinct, forcing two distinct pairs of our values to be equal, such as 30 + 30 + 20 + 20 = 100. In this case, it is not hard to see that $x_i+x_j$ can be any even value in $\{0, 2, \ldots, 100\}$, and once this is chosen, there is a unique solution for $x_k$ and $x_\ell$, meaning that in this case $|X_{ij} \cap X_{k\ell}| = 51$.

The remaining twelve pairwise intersections overlap in one of the indices, so they are of the form $X_{ij} \cap X_{ik}$, with $i,j,k$ distinct. Any solution in this intersection has $x_i=x_j=x_k$; as above the sum $x_i+x_j+x_k$ can be any value in $\{0, 3, 6, \ldots 99\}$, for which there are 34 choices. Once this sum is chosen, $x_\ell$ is determined uniquely, so $|X_{ij} \cap X_{ik}| = 34$ for distinct $i,j,k$.

That takes care of the pairwise intersections; now we have to look at the 3-way intersections $X_{ij} \cap X_{k\ell} \cap X_{mn}$. There are ${6 \choose 3} = 20$ possible intersections. Of these 20, exactly 4 have $|\{i,j,k,\ell,m,n\}| = 3$, for example $\{i,j\} = \{1,2\}$, $\{k,\ell\} = \{1,3\}$ and $\{m,n\} = \{2,3\}$. In these four cases, the intersection of these three sets is the same as the intersection of just two of them, so by the above the intersection has size 34.

In the other 16 cases, the intersection has only one solution, namely $x_1 = x_2 = x_3 = x_4 = 25$. A solution in $X_{ij} \cap X_{k\ell} \cap X_{mn}$ has $x_i = x_j$, $x_k = x_\ell$ and $x_m = x_n$. If $\{i,j\}$ and $\{k, \ell\}$ overlap (say $j=\ell$), then we have $x_i = x_j = x_k$, with $i,j,k$ distinct. Since all four indices must appear, we know that one of $m$ or $n$ must be in $\{i,j,k\}$, while the other is the other index. This forces all four variables to be equal. If $\{i,j\}$ and $\{k,\ell\}$ are disjoint, then one of $m$ or $n$ must be in $\{i,j\}$ and the other must be in $\{k,\ell\}$, which again forces all variables to be equal.

Fortunately, this latter case covers all of the 4-way, 5-way and 6-way intersections of our sets; they all have size 1. So using inclusion/exclusion, we get the number of solutions: $${103 \choose 3} - 6\times2601+ (3 \times 51 + 12 \times 34) - (4 \times 34 + 16) + 15 - 6 +1 = {103 \choose 3} - 15187$$

Jeremy Dover
  • 1,592
2

Here is the solution from my side. One can translate this problem into a partition problem.

The much-studied partition function $p_k(n)$ is defined as the number of solutions of the equation $x_1+\cdots+x_k=n$ where $x_1\ge x_2\ge\cdots\ge x_k\ge1$; those solutions are called the partitions of $n$ into (exactly) $k$ parts. For fixed $k$, the generating function is $$\sum_{k=0}^\infty p_k(n)x^n=\frac{x^k}{(1-x)(1-x^2)\cdots(1-x^k)}.$$ For $n\ge k\gt1$ we have the recurrence equation $$p_k(n)=p_{k-1}(n-1)+p_k(n-k)$$

with initial values $p_0(0) = 1$ and $p_k(n) = 0$ if $n \le 0$ or $k \le 0$ , and $n$ and $k$ are not both zero

$x_1 + x_2 +x_3 +x_4 = 100$, where $x_i$ is non-negative integer.

Let, $x_1 = a_1$, $x_2 = x_1 + a_2$, $x_3 = x_2 + a_3$, $x_4 = x_3 + a_4$;

Where $a_1 \ge 0$ and $a_2, a_3, a_4 \ge 1$. This is to ensure that the numbers stay distinct

$4a_1 + 3a_2 + 2a_3 + a_4 = 100$

This is the exact same relation that appears when one resolves the equation of standard partition problem, except that $a_1$ should be $\ge 1$ and $a_2, a_3, a_4$ should be $\ge 0$. We can do this by the following transformations

$a_1 = t_1 - 1$, $a_2 = t_2 + 1$, $a_3 = t_3 + 1$, $a_4 = t_4 + 1$

This satisfies our assumptions and now $t_1 \ge 1$ and $t_2, t_3, t_4 \ge 0$.

$4t_1 + 3t_2 + 2t_3 + t_4 = 98$

This is equivalent to dividing 98 into exactly 4 parts. Since all the 4 numbers can be aranged in any order to form other combinations of distinct non-negative $x_1, x_2, x_3, x_4$, therefore $4!$ should be multiplied.

The final answer would be $\Rightarrow 4! \cdot p_4(98)$

$p_4(98)$ can be calculated using the recurrence relation through hand or a computer program, but luckily we have closed form solutions available for certain values of $k$ in $p_k(n)$

$$p_4(n) = \left[ \frac{1}{144}t_4^3(n) - \frac{1}{48}t_4(n) \right]$$ for n is even $$p_4(n) = \left[ \frac{1}{144}t_4^3(n) - \frac{1}{12}t_4(n) \right]$$ for n is odd

Here $\left[ \cdot \right]$ stands for nearest integer function and $t_k(n) = n + \frac{1}{4}.k(k-3)$

Subsitution values gives us $p_4(98) = \left[ \frac{99^3}{144} - \frac{99}{48} \right] = 6736$, $4! = 24$, $\Longrightarrow 24* 6736 = 161\:644$

A generalized approach for this problem has been disussed in this StackExchange question. This answer was also inspired by this answer

Chitranshu Vashishth
  • 21