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 p^\alpha -1 is the same as the number of compositions of the number \alpha .

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

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 {p_1}^{\alpha _1}{p_2}^{\alpha _2} *...* {p_n}^{\alpha_n} - 1 is the same as the number of ways to factor

\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:

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

In this fashion, we see that the number of perfect partitions are the same as the number of ordered factorizations of {\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: 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 n = 1 + 1 + 1 ... + 1. But then each ‘+’ symbol might be replaced by a separator, so that for example 1 + 1 + 1 might be 1 + 1, 1 = 2, 1. So we see that there are always 2^{n-1} different compositions of the number n. So we now know the number of partitions of each number n!

Advertisements