I am trying to find the number of integral solution to the given equation
x1+x2+x3+x4=n given that x1>x2>x3>x4
But could not figure out any mathematical formula to it. If someone knows how to solve it please help
UPD: xi>=0 (all number are greater than or equal to zero)
Thanks
The number is $$$\infty$$$, because for all $$$x > n$$$ the tuple $$$(x, n, 0, -x)$$$ is a solution.
Sorry, I forgot to mention all numbers are positive integers
Now I have updated that
Auto comment: topic has been updated by singhpriyank (previous revision, new revision, compare).
$$$O(N^{4})$$$: Iterate over all $$$x_{i}$$$.
$$$O(N^{3})$$$: Iterate over $$$x_{1}, x_{2}, x_{3}$$$, then you can check how much more you need and if that's greater than $$$x_{3}$$$, then you add 1.
$$$O(N^{2})$$$: Iterate over $$$x_{1}$$$ and $$$x_{2}$$$, then you calculate how much more you need. Both of them need to be at least $$$x_{2}$$$, so you subtract $$$2x_{2}$$$ more. Now whatever you've got, say $$$X$$$, there are $$$\frac{X-1}{2}$$$ ways [If $$$X$$$ is negative or zero, It's not possible, so skip].
Can't think of any $$$O(N)$$$ optimization, maybe someone else can help.
Thank You
But if someone can tell a mathematical formula or O(N) solution it would be great
This might be an overkill, I suspect there might be a simpler solution.
$$$y_1 = x_1, y_i = x_i-x_{i-1}-1$$$ for $$$i > 0$$$
Now we need to solve for number of solutions $$$y_4 + 2y_3 + 3y_2 + 4y_3 = n + 6 = N$$$ for $$$y_i \geq 0$$$.
Let $$$G(x)=\sum_{0\leq i}x^i$$$.
This can be computed as coefficient of $$$x^N$$$ in $$$P(x) = G(x)G(x^2)G(x^3)G(x^4)$$$.
We only care about coefficients $$$x^0, x^1, ..x^N$$$ in each of the 4 terms on RHS.
So we can multiply the polynomials in $$$O(nlogn)$$$ using fft, as the degree of each polynomial being multiplied is atmost $$$N$$$. And answer is the coefficient of $$$x^N$$$.
I suppose we can do it in $$$O(N)$$$ if we write $$$G(x) = 1 / (1-x)$$$, but I don't know how, but maybe something on these lines.
On expanding the denominator of $$$P$$$, we can write $$$P(x) = 1/(1-R(x))$$$, we can see that $$$R(x)$$$ is a polynomial of size 10 without a constant term. And we can write $$$P(x) = \sum R(x)^i$$$, and we need to look at just the first N terms as $$$R(x)$$$ doesn't have a constant term.
I've done it in O(N), It can be done in math formula, doesn't even have to require fft.
Could you briefly explain?
It can be done with simple series formulae, while iterating through x4 from (0, (n-6)/4), which is almost O(N). You do need to consider even, odd cases here tho.
can you explain more ?
~~ That's why you should not learn fft.~~ You can OEIS this problem btw. However, if I couldn't use OEIS I would use the following DP:
Let's set y_i to 0. Now let's increment them in order. First we increment $$$y_0$$$, then $$$y_1$$$, etc.
$$$dp[s][i] =$$$ number of ways to get sum s such that last increment operation was applied to $$$y_i$$$. Transitions: we either increment $$$y_i$$$ again or increment $$$y_{i+1}$$$. It could be sped up using matrix exponentiation.
P. S. https://oeis.org/A026810
A bit of case work got me $$$\binom{n+3}{3} - 6*(n/2 + 1)*(n/2 + 2) + 18*(n\%2==0)*(n/4 + 1) + 8*(n/3 + 1) - 15 * (n\%4==0)$$$
All divisions are integer divisions.
The problem is equivalent to $$$1/24$$$th the number of solutions to equation $$$x_1 + x_2 + x_3 + x_4 = n$$$ with the condition that $$$x_1$$$, $$$x_2$$$, $$$x_3$$$ and $$$x_4$$$ are pairwise distinct and are non-negative. For $$$i < j$$$, define $$$S_{ij}$$$ as the set of all solutions for the equation $$$x_1 + x_2 + x_3 + x_4 = n$$$ with condition that $$$x_i = x_j$$$ and $$$x_1, x_2, x_3, x_4 \geq 0$$$. So we need to compute
This can be simplified using Inclusion-Exclusion to
where
The above values can be computed in $$$\mathcal{O}(1)$$$ using the formulas
Thanks a lot!!!