[Math] Partitions Into at Least Two Distinct Parts

algorithmsdiscrete mathematicsinteger-partitions

I am looking for a formula/algorithm to give me the distinct (I might be using this term wrong) partitions of number N if it meets the following conditions:

all I need is the number of partitions that meet these requirements, not the partitions themselves; the acceptable partitions need to have no duplicate numbers, for instance N = 5,
(2,3)
(1,4)
would be the only acceptable/valid answer so it would return 2 (2 valid options) and have 2 or more values. For instance N = 1 would return 0, because (1) does not have two numbers equal or greater to 1.

N will be between 3 and 200 and be an integer. I made an "algorithm" in Python that yields to results below which are correct, but takes 1-2 weeks to complete from 3-200 because I am gathering all the partitions, then removing all the partitions that don't fit my criteria. I know there is a formula here and a list of correct outputs here but I do not understand the formula or if this works for my purpose.

The formula noted is:

sum(k>=0, x^((k^2+k)/2) / prod(j=1..k, 1-x^j)) – 1/(1-x)

I have found countless recursion methods to list all partitions, but non that utilize this formula (above). Is it possible to use an existing formula to find the number of partitions without having to loop through each one? If so, where would I start in converting it to a more readable/usable function (in something like Python, Java, C++, or another common programming language)? Any help is much appreciated, I have done fairly extensive research (to the best of my ability) and have found allot of close answers, such as getting district partitions of N,K where K is the set returned, but nothing that executes fast enough to be used in the real world. Below are a few test cases.

N = 9; 7

N = 44; 1815

N = 200; 487067745

and a few short ones expanded (bold text meet my requirements)

N = 3;

(1,2)

(3)

(1,1,1)

N = 5;

(1,4)

(2,3)

(1,1,1,1,1)

(1,1,1,2)

(1,2,2)

(1,1,3)

Note that though my test case doesn't show it, a valid set could be something like: (1,2,3,4) if N = 10

Best Answer

To complete the conversation, here is a rather concise java program to generate the sequence up to $a(200)$

import java.lang.Math;

public class PartitionCounter
{
  public static void main(String[] args)

  {

    int F[] = new int[201];

    F[0]=1;

    F[1]=1;

    for(int n=2; n<201; n++){


      for(int k=200; k>n-1; k--){

        F[k] = F[k]+F[k-n];

      }

    }

    System.out.print("[");
    for(int k=0; k<200; k++){
        System.out.print((F[k]-1) + ", ");
    }
    System.out.print("]");
  }
}

What is going on mathematically is again, we are approaching via generating functions. In this case, the generating function is:

$$\frac{1}{x-1}+\prod\limits_{k=1}^\infty (1+x^k)$$

For our purposes however, we do not need infinitely many terms, we only need the first $201$ terms of the polynomial, so the following will suffice

$$(1+x)(1+x^2)(1+x^3)\cdots (1+x^{199})(1+x^{200}) - (1+x+x^2+\dots+x^{200})$$

The coefficient of $x^n$ in the expansion of the above corresponds to the number of partitions of $n$ matching your requirements (all parts distinct and at least two parts). To see why this is, recognize that if we were to avoid adding anything together, there will be a term associated with each sequence of choosing $x^i$ vs $1$ in the product such that the powers add up to $n$.

For example, one of the contributions to the coefficient of $x^5$ comes from the sequence of choices (in red) as $(\color{red}{1}+x)(1+\color{red}{x^2})(1+\color{red}{x^3})(\color{red}{1}+x^4)\cdots$ corresponding to the partition (2,3). This is just like the "foil" method for computing $(a+b)(c+d)$ except taken to the extreme having used "infinitely many" (though only finitely many matter) parenthetical expressions being multiplied.

The code above quite literally computes the coefficients of $x^k$ in the expansion of $(1+x)(1+x^2)(1+x^3)\cdots (1+x^{200})$ and stores them in an integer array for each partial product. It only bothers to remember the coefficients for those terms up to the power $x^{200}$ because anything of higher power is irrelevant. We finally recognize that if we have a polynomial, $f(x)$ and we multiply by $(1+x^k)$, the coefficient of $x^n$ in $(1+x^k)f(x)$ will be the coefficient of $x^n$ in $f(x)$ plus the coefficient of $x^{n-k}$ in $f(x)$. The above code will update the values of $F[n]$ from back to front so as to avoid having the newly modified values disrupting further calculations without the need to create a temporary array.

Finally, we subtract one from the above because you are interested only in those partitions which have at least two parts. (this is also where the $\frac{1}{x-1}$ comes into play in the generating function, as the expansion of $\frac{1}{x-1}$ is $-1-x-x^2-x^3-x^4-\dots$)

The output for the first two hundred and one terms in the sequence is then: (note: starts at $n=0$ instead of $n=3$)

[0, 0, 0, 1, 1, 2, 3, 4, 5, 7, 9, 11, 14, 17, 21, 26, 31, 37, 45, 53, 63, 75, 88, 103, 121, 141, 164, 191, 221, 255, 295, 339, 389, 447, 511, 584, 667, 759, 863, 981, 1112, 1259, 1425, 1609, 1815, 2047, 2303, 2589, 2909, 3263, 3657, 4096, 4581, 5119, 5717, 6377, 7107, 7916, 8807, 9791, 10879, 12075, 13393, 14847, 16443, 18199, 20131, 22249, 24575, 27129, 29926, 32991, 36351, 40025, 44045, 48445, 53249, 58498, 64233, 70487, 77311, 84755, 92863, 101697, 111321, 121791, 133183, 145577, 159045, 173681, 189585, 206847, 225584, 245919, 267967, 291873, 317787, 345855, 376255, 409173, 444792, 483329, 525015, 570077, 618783, 671417, 728259, 789639, 855905, 927405, 1004543, 1087743, 1177437, 1274117, 1378303, 1490527, 1611387, 1741520, 1881577, 2032289, 2194431, 2368799, 2556283, 2757825, 2974399, 3207085, 3457026, 3725409, 4013543, 4322815, 4654669, 5010687, 5392549, 5802007, 6240973, 6711479, 7215643, 7755775, 8334325, 8953855, 9617149, 10327155, 11086967, 11899933, 12769601, 13699698, 14694243, 15757501, 16893951, 18108417, 19406015, 20792119, 22272511, 23853317, 25540981, 27342420, 29264959, 31316313, 33504745, 35839007, 38328319, 40982539, 43812109, 46828031, 50042055, 53466623, 57114843, 61000703, 65139007, 69545357, 74236383, 79229675, 84543781, 90198445, 96214549, 102614113, 109420548, 116658615, 124354421, 132535701, 141231779, 150473567, 160293887, 170727423, 181810743, 193582641, 206084095, 219358314, 233451097, 248410815, 264288461, 281138047, 299016607, 317984255, 338104629, 359444903, 382075867, 406072421, 431513601, 458482687, ]

Related Question