In continuation of my previous post on perfect partitions, I seek to extend the previous result to all numbers, not just one less than a prime power.

Previously, we had:

The number of perfect partitions of the number is the same as the number of compositions of the number .

Today, we will find a relation for the number of perfect partitions of any positive integer $latex n $. The first thing we note is that every number n can be written uniquely as:

$latex n = {p_1}^{\alpha _1}{p_2}^{\alpha _2} *…* {p_n}^{\alpha_n} – 1$ , where each of the p are distinct primes.

Parallel to the last result, we can see that the number of perfect partitions of the number $latex {p_1}^{\alpha _1}{p_2}^{\alpha _2} *…* {p_n}^{\alpha_n} – 1$ is the same as the number of ways to factor

$latex \dfrac{x^{{p_1}^{\alpha _1}{p_2}^{\alpha _2} *…* {p_n}^{\alpha_n} – 1} – 1}{x – 1} $.

This can immediately be proved by extending the previous post: still use finite geometric series and the positivity of the terms to show that each exponent can be reached in exactly one way. The different factors would again be of the form:

$latex \dfrac{1 – x^\gamma}{1-x^\delta} $ where $latex \delta | \gamma $.

In this fashion, we see that the number of perfect partitions are the same as the number of ordered factorizations of $latex {\alpha _1}{\alpha _2} *…* {\alpha_n}$. But we haven’t really considered this yet. How many ordered factorizations are there? This is unfortunately beyond the scope of this post, but Sloane’s has that sequence here, and there is a Dirichlet generating function: $latex f(s) = \dfrac{1}{2 – \zeta(s)}$.

As an aside that made more sense in the original post, I consider the number of compositions of a number. How many compositions are there for a number n?

I hadn’t seen this before, but upon consideration I see that it is a very simple exercise that one might encounter. Imagine we are thinking of the number of compositions of n. Then $latex n = 1 + 1 + 1 … + 1$. But then each ‘+’ symbol might be replaced by a separator, so that for example $latex 1 + 1 + 1$ might be $latex 1 + 1, 1 = 2, 1$. So we see that there are always $latex 2^{n-1} $ different compositions of the number n. So we now know the number of partitions of each number n!

Pingback: An interesting (slow) factoring algorithm « mixedmath

If I understood your post correctly. Suppose I wish to find perfect partitions of 95, so i can write:

95 = [ (2^5) * 3 ] -1

here, n = 95, p1 = 2, a1 = 5, p2 = 3, a2 = 1

multiplying compositions of a1 and a2 i get, (2^4) * (2^0) = 16

so perfect_partition(95) = 16 according to this post while answer is 112 OEIS link

If you can explain what am i missing?

@Abhay:

This is a very good point! In looking over my (original) post, I see that I misspoke. In particular, the conclusion at the end is not that the number of perfect partitions is the same as the number of compositions, but instead as the number of ordered factorizations of $latex alpha_1 alpha_2 … alpha_n$. I think that I misspoke because when we only consider a prime power, there is no difference. I have updated the post – thank you.