singhpriyank's blog

By singhpriyank, history, 4 years ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

The number is $$$\infty$$$, because for all $$$x > n$$$ the tuple $$$(x, n, 0, -x)$$$ is a solution.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, I forgot to mention all numbers are positive integers

    Now I have updated that

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by singhpriyank (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank You

    But if someone can tell a mathematical formula or O(N) solution it would be great

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    I've done it in O(N), It can be done in math formula, doesn't even have to require fft.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Could you briefly explain?

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you explain more ?

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +6 Vote: I do not like it

    ~~ 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

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

$$$\frac{1}{24}|(S_{12} \cup S_{13} \cup S_{14} \cup S_{23} \cup S_{24} \cup S_{34})^c|$$$

This can be simplified using Inclusion-Exclusion to

$$$\frac{1}{24}(A_0 - 6A_1 + 3A_2 + 8A_3 - 6A_4)$$$

where

  • $$$A_0$$$ is the number of integral solutions to the equation $$$x_1 + x_2 + x_3 + x_4 = n$$$ with $$$x_i \geq 0$$$
  • $$$A_1$$$ is the number of integral solutions to the equation $$$2x_1 + x_2 + x_3 = n$$$ with $$$x_i \geq 0$$$
  • $$$A_2$$$ be the number of integral solutions to the equation $$$2x_1 + 2x_2 = n$$$ with $$$x_i \geq 0$$$
  • $$$A_3$$$ be the number of integral solutions to the equation $$$3x_1 + x_2 = n$$$ with $$$x_i \geq 0$$$
  • $$$A_4$$$ be the number of integral solutions to the equation $$$4x_1 = n$$$ with $$$x_i \geq 0$$$

The above values can be computed in $$$\mathcal{O}(1)$$$ using the formulas

  • $$$A_0 = \binom{n + 3}{3}$$$
  • $$$A_1 = (n + 1 - \bigl\lfloor\frac{n}{2}\bigr\rfloor)(\bigl\lfloor\frac{n}{2}\bigr\rfloor + 1)$$$
  • $$$A_2$$$ is equal $$$\bigl\lfloor\frac{n}{2}\bigr\rfloor + 1$$$ if $$$n$$$ is divisible by $$$2$$$ and is equal to $$$0$$$ otherwise
  • $$$A_3 = \bigl\lfloor\frac{n}{3}\bigr\rfloor + 1$$$
  • $$$A_4$$$ is equal to 1 if $$$n$$$ is divisible by $$$4$$$ and is equal to $$$0$$$ otherwise