How many different sets of positive integers $(a, b, c, d)$ are there such that $a \lt b \lt c \lt d$ and $a + b + c + d = 41$?

Question

Is there a general formula which I can use to calculate this and if it's with proof or reasoning would be great as well. Even if you could please solve this $4$-variable ordered set of positive integers case would be a great help indeed. Sorry I am weak in this topic.

Thanks Robert for your pointers in modifying it to $(4\times1) + (3\times2) + (2\times3) + (1\times4) = 41$, where there are no additional constraints on $x_i$

To solve this must do it manually by cases or is there a short way of calculating it using "Bars and Stars" (of which I am aware of the method)? The answer given is $321$.

But when I calculate it like this it doesn't seem to match the answer: imagine the new given equation as containing $(4+3+2+1) = 10$$x_i$'s individually so as equivalent to finding the number of positive integer solutions for $b_1 + b_2 + ... + b_{10} = 41$ which is $C(41 - 1, 10 - 1) = C(40, 9)$. Now since we have $4x_1$'s that are identical, we need to divide this by $4!$ (for its permutations of "overcounting") and similarly divide next by $3!$ (for $3x_2$'s that are equal), and $2!$ for the $2x_3$'s that are equal. How is my approach wrong here? anybody, please help me? Thanks again

As per Robert's transformation with Anil's suggestion of the generating functions method, here's my work on it:

I actually used an online calculator called "Sage Math" to do this via this website:

https://www.whitman.edu/mathematics/cgt_online/book/section03.01.html

With these modifications

$f(x)=(1-x^4)^{-1}\times(1-x^3)^{-1}\times(1-x^2)^{-1}\times(1-x)^{-1}$

show(taylor($f,x,0,33$))

And have gotten the verification that $321$ is indeed the answer after some tedious algebra (please note that since we are looking for the coefficient of $x^41$ in the expansion Anil wrote which has $x^(4+3+2+1) = x^10$ factored outside meaning in the remaining Newton's Binomial Expansions with negative exponent, we only need to determine the coefficient of $x^(41-10)= x^31$ in it which is "$321$" as the answer suggested (please see image below):

Answer 1

If we solve the problem without the condition $a<b<c<d$ then the answer is $40\choose3$.

Now we want to count the number of sets with at least $2$ equal variables.

Note that all $4$ of them can't be equal, because if they are then their sum should be divisible by $4$.

Case $1$ : Exactly $2$ of them are equal.

We need to solve the equation $$2x_1+x_2+x_3=41 : x_1,x_2,x_3\in \mathbb{N}$$

where $x_1,x_2$ and $x_3$ are pairwise distinct.

If $x_1 = k$ then the number solutions is ${41-2k-1\choose1} = 41-2k-1$, for any $1\leq k\leq13$ we have counted $2$ extra solutions ($x_2 = k$ and $x_3=k$).

Thus the number of solutions for this case is ${4\choose2}(38+36+\dots + 2 - 26) = {4\choose2}2(19+18+\dots + 1 - 13) = 2124$

Case 2 : Exactly $3$ of them are equal.

We calculate the number of solutions like Case $1$.

The number of solutions for this case is $13{4\choose3} = 52$.

So there are ${40\choose3} - (52 + 2124) = 7704$ solutions.

For every pairwise distinct $a,b,c,d$ there is exactly 1 permutation such that $a<b<c<d$. we counted each set $(a,b,c,d)$, $4!$ times.

So the answer is $\frac{7704}{4!}=321$.

Answer 2

As has been suggested by @Robert Shore, transform the problem to

$4x_1 + 3x_2 +2x_3 + x_4 = 41,\; x_i \in N$

Now when multinomials in $x$ are multiplied together, the exponents get added up, so if we multiply

$(x^4 +x^8 +....\infty)(x^3+x^6+...\infty)(x^2+x^4+....\infty)(x+x^2+....\infty)$

we will find the answer in the coefficient of $x^{41}$, which represents all possible combos where the sum of the exponents in the multiplied terms is $41$.

We can simplify the expression to $\left(\frac{x^4}{1-x^4}\cdot\frac{x^3}{1-x^3}\cdot\frac{x^2}{1-x^2}\cdot\frac{x}{1-x}\right)$.

Multiplying it out gives the answer of $\;\boxed{321}$

This is a simple example of generating functions of whose rudimentary uses you could learn bit by bit

Answer 3

Thanks some info from OEIS, and some help from Mathworld, we have the following:

Let the number of partitions of $n$ into $k$ distinct parts be $Q(n, k)$. Then $Q(n,k)$ has the recurrence:

$$Q(n,k) = Q(n-k, k) + Q(n-k, k-1)$$

where $Q(n,1) = 1, Q(n,0) = 0$.

---

If you prefer, we have a (possibly easier?) method: $Q(n, k) = P(n- \binom{k}{2}, k)$, where $P(n,k)$ has the recurrence:

$$P(n,k) = P(n-1, k-1) + P(n-k, k)$$

where $P(n,1) = P(n,n) = 1$. We'll want $P(35,4)$ of course. Either way, the OEIS link gives $Q(41,4) = P(35,4) = 321$.

---

If you must have a closed-form function, Mathworld has you... "covered," in the loosest sense of the term, and only for $P(n,k)$ up to $k=4$. The function involved is

$$P(n,4) = \textstyle \frac1{864} \displaystyle \left\{ 3 \left(n+1 \right) \left[2n \left(n+2 \right)-13+9 \left(-1 \right)^n \right] - 96 \cos \frac{2 \pi n}{3}+ \\ \left( 108 \left(-1 \right)^ \left(n/2 \right) \right) \big(\bmod \left(n+1,2 \right) \big)+32 \sqrt{3} \sin \left(\frac{2 \pi n}{3} \right)\right\}$$

And yes, for $n=35$ it does in fact evaluate to $321$.

Answer 4

As said in the comments, by assuming $a=x_1, b=x_1+x_2, c=x_1+x_2+x_3$ and $d=x_1+x_2+x_3+x_4$, the problem transforms into finding the number of sets $(x_1, x_2,x_3, x_4)$ of positive integers such that: $x_1+2x_2+3x_3+4x_4=41.$

It is very easy to note that $1 \leq x_4 \leq8$ because $x_1, x_2, x_3 \geq1.$

Moreover, observe that, for a positive integer $k$;

if $x_1+2x_2=2k$, then there are $k-1$ pairs of $(x_1, x_2)$ satisfying the equation;

and if $x_1+2x_2=2k+1$, then there are $k$ pairs of $(x_1, x_2)$ satisfying the equation.

Now, with the help of the information above, we can use the approach below, which is limited to very simple calculations in spite of considering $8$ cases.

---

Case $1$: $x_4=1$.

$$(x_4, x_3)=(1,11) \implies x_1+2x_2=4 \implies 1 \ solution \\ (x_4, x_3)=(1,10) \implies x_1+2x_2=7 \implies 3 \ solutions \\ (x_4, x_3)=(1,9) \implies x_1+2x_2=10 \implies 4 \ solutions\\ (x_4, x_3)=(1,8) \implies x_1+2x_2=13 \implies 6 \ solutions\\ (x_4, x_3)=(1,7) \implies x_1+2x_2=16 \implies 7 \ solutions\\ (x_4, x_3)=(1,6) \implies x_1+2x_2=19 \implies 9 \ solutions\\ (x_4, x_3)=(1,5) \implies x_1+2x_2=22 \implies 10 \ solutions\\ (x_4, x_3)=(1,4) \implies x_1+2x_2=25 \implies 12 \ solutions\\ (x_4, x_3)=(1,3) \implies x_1+2x_2=28 \implies 13 \ solutions\\ (x_4, x_3)=(1,2) \implies x_1+2x_2=31 \implies 15 \ solutions\\ (x_4, x_3)=(1,1) \implies x_1+2x_2=34 \implies 16 \ solutions;$$ hence, in this case, the total number is $96$.

---

Case $2$: $x_4=2.$ $$(x_4, x_3)=(2,10) \implies x_1+2x_2=3 \implies 1 \ solution \\ (x_4, x_3)=(2,9) \implies x_1+2x_2=6 \implies 2 \ solutions \\ (x_4, x_3)=(2,8) \implies x_1+2x_2=9 \implies 4 \ solutions\\ (x_4, x_3)=(2,7) \implies x_1+2x_2=12 \implies 5 \ solutions\\ (x_4, x_3)=(2,6) \implies x_1+2x_2=15 \implies 7 \ solutions\\ (x_4, x_3)=(2,5) \implies x_1+2x_2=18 \implies 8 \ solutions\\ (x_4, x_3)=(2,4) \implies x_1+2x_2=21 \implies 10 \ solutions\\ (x_4, x_3)=(2,3) \implies x_1+2x_2=24 \implies 11 \ solutions\\ (x_4, x_3)=(2,2) \implies x_1+2x_2=27 \implies 13 \ solutions\\ (x_4, x_3)=(2,1) \implies x_1+2x_2=30 \implies 14 \ solutions;\\$$

hence, in this case, the total number is $75$.

---

Case $3$: $x_4=3.$ $$(x_4, x_3)=(3,8) \implies x_1+2x_2=5 \implies 2 \ solutions \\ (x_4, x_3)=(3,7) \implies x_1+2x_2=8 \implies 3 \ solutions \\ (x_4, x_3)=(3,6) \implies x_1+2x_2=11 \implies 5 \ solutions\\ (x_4, x_3)=(3,5) \implies x_1+2x_2=14 \implies 6 \ solutions\\ (x_4, x_3)=(3,4) \implies x_1+2x_2=17 \implies 8 \ solutions\\ (x_4, x_3)=(3,3) \implies x_1+2x_2=20 \implies 9 \ solutions\\ (x_4, x_3)=(3,2) \implies x_1+2x_2=23 \implies 11 \ solutions\\ (x_4, x_3)=(3,1) \implies x_1+2x_2=26 \implies 12 \ solutions;\\$$ hence, in this case, the total number is $56$.

---

Case $4$: $x_4=4.$ $$(x_4, x_3)=(4,7) \implies x_1+2x_2=4 \implies 1 \ solution \\ (x_4, x_3)=(4,6) \implies x_1+2x_2=7 \implies 3 \ solutions \\ (x_4, x_3)=(4,5) \implies x_1+2x_2=10 \implies 4 \ solutions\\ (x_4, x_3)=(4,4) \implies x_1+2x_2=13 \implies 6 \ solutions\\ (x_4, x_3)=(4,3) \implies x_1+2x_2=16 \implies 7 \ solutions\\ (x_4, x_3)=(4,2) \implies x_1+2x_2=19 \implies 9 \ solutions\\ (x_4, x_3)=(4,1) \implies x_1+2x_2=22 \implies 10 \ solutions;\\$$ hence, in this case, the total number is $40$.

---

Case $5$: $x_4=5.$

$$(x_4, x_3)=(5,6) \implies x_1+2x_2=3 \implies 1 \ solution \\ (x_4, x_3)=(5,5) \implies x_1+2x_2=6 \implies 2 \ solutions \\ (x_4, x_3)=(5,4) \implies x_1+2x_2=9 \implies 4 \ solutions\\ (x_4, x_3)=(5,3) \implies x_1+2x_2=12 \implies 5 \ solutions\\ (x_4, x_3)=(5,2) \implies x_1+2x_2=15 \implies 7 \ solutions\\ (x_4, x_3)=(5,1) \implies x_1+2x_2=18 \implies 8 \ solutions;\\$$

hence, in this case, the total number is $27$.

---

Case $6$: $x_4=6.$

$$(x_4, x_3)=(6,4) \implies x_1+2x_2=5 \implies 2 \ solutions \\ (x_4, x_3)=(6,3) \implies x_1+2x_2=8 \implies 3 \ solutions \\ (x_4, x_3)=(6,2) \implies x_1+2x_2=11 \implies 5 \ solutions\\ (x_4, x_3)=(6,1) \implies x_1+2x_2=14 \implies 6 \ solutions;\\$$ hence, in this case, the total number is $16$.

---

Case $7$: $x_4=7.$

$$(x_4, x_3)=(7,3) \implies x_1+2x_2=4 \implies 1 \ solution \\ (x_4, x_3)=(7,2) \implies x_1+2x_2=7 \implies 3 \ solutions \\ (x_4, x_3)=(7,1) \implies x_1+2x_2=10 \implies 4 \ solutions;\\$$ hence, in this case, the total number is $8$.

---

Case $8$: $x_4=8.$

$$(x_4, x_3)=(8,2) \implies x_1+2x_2=3 \implies 1 \ solution \\ (x_4, x_3)=(8,1) \implies x_1+2x_2=6 \implies 2 \ solutions;$$ hence, in this case, the total number is $3$.

---

Finally, the answer is $96+75+56+40+27+16+8+3=321.$