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!
Leave a comment
Info on how to comment
To make a comment, please send an email using the button below. Your email address won't be shared (unless you include it in the body of your comment). If you don't want your real name to be used next to your comment, please specify the name you would like to use. If you want your name to link to a particular url, include that as well.
bold, italics, and plain text are allowed in
comments. A reasonable subset of markdown is supported, including lists,
links, and fenced code blocks. In addition, math can be formatted using
$(inline math)$ or $$(your display equation)$$.
Please use plaintext email when commenting. See Plaintext Email and Comments on this site for more. Note also that comments are expected to be open, considerate, and respectful.
Comments (2)
2011-04-26 Abhay
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?
2011-05-12 davidlowryduda
@Abhay in comment 1:
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 $ \alpha_1 \alpha_2 \ldots \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.