[Math] Number of partitions for N without repetition

integer-partitions

I'm trying to figure out a formula that returns the number of strict partitions (no duplicate values) of n.

For example:

5 would yield 3: 5, 4+1, 3+2

I only need the number of unique partitions, not the partitions themselves.

I did come across this article: http://oeis.org/A000009 that has a reference to a table of outputs: http://oeis.org/A000009/b000009.txt that has exactly what I need, however I do not understand the referenced generating formula which is:

prod(m>=1, 1+x^m)

From that it appears that if my input is 5, I would never receive 3 as a result since that value is increasing exponentially.

I also found this reference http://mathworld.wolfram.com/PartitionFunctionQ.html which, as shown in figure 19, uses a partition function and a binomial coefficient but I don't want to set a specific value for the distinct parts.

I hope I explained this well and I apologize for any ignorance when it comes to these formulas, it's been a while since I've dealt with anything like this so some clarification would be much appreciated!

Best Answer

The table at OEIS says that $q(5)=3$, as you have computed. So everything is fine. The generating function is not the function $q(n)$ itself.

So there is no easy "explicit formula" for $q(n)$, but one can coompute it using the generating function, see here.

Related Solutions

[Math] Number of ways to add up to a number without repetition (order does not matter)

@jenny :I do not a see a formula in your post that you expect to generalize.

We are counting partitions of $x$ with $y$ parts and the largest part not exceeding $z$.

One way is to use recursive formulation as pointed out by @Kevin Carlson.
Another quick way on a computer is to use the generating function: $$\sum_{\text{over }y\text{-element subsets of }[z-1]}\left( \prod_{\text{over elements of a y-element subset}}\frac{1}{1-n^s} \right)$$and then look at the coefficient of $n^{x-y}$ where $[z-1]=\{1,2,\dots, z-1\}$

[Math] Partitions Into at Least Two Distinct Parts

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, ]

Best Answer

Related Solutions

[Math] Number of ways to add up to a number without repetition (order does not matter)

[Math] Partitions Into at Least Two Distinct Parts

Related Question