Math 521 #150: Number partitions (3-powers)

If n is a positive integer, a 3-partition of n is a list of powers of 3, arranged in order from greatest to least, whose sum is n.

How many different 3-partitions of 29 are there?

Please have a good try.

Please give it a try before looking at the answer and explanation.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

A math problem will be solved and discussed on every TUESDAY. These problems are suitable for math enthusiasts, it helps in learning and sharpening skills in math Olympiad skill too.

Check it out and share to anyone who may like it. Please comment if you have any idea to improve the videos, or any alternative solutions to the problems.

Have fun and enjoy the problem solving!

[riadsouissi]

I love these counting problems.

My approach is this :

n=29=a0+3*a1+9a2+27a3
Consider the generating function f(x) = sum q(n)x^n where q(n) is the number of 3 partitions of n.

Before this, we'll simplify the problem a bit by counting the cases where a3=1 separately 29 = 27+1+1. This is only one case. Now we'll counts the number of 3 partitions where a3=0

f(x) = sum x^a0 * (x^3)^a1 * (x^9)^a2 . The sum is over all a0, a1, a2. Since these a(i) are independant, we can separate the sum into a product of 3 infinite sums. Then f(x) = 1/(1-x) * 1/(1-x^3) * 1/(1-x^9).

Now we need to manipulate the numerator in order to simplify the denominator.

=

The numerator simplifies into x^14 + x^13 + x^12 + 2 x^11 + 2 x^10 + 2 x^9 + 3 x^8 + 3 x^7 + 3 x^6 + 2 x^5 + 2 x^4 + 2 x^3 + x^2 + x + 1

While the denominator is 1/2 of the second derivative of a geometric sum of x^9 = 1 + 3 x^9 + 6 x^18 + 10 x^27 + terms whose powers are two high to be useful.

We want to multiply both series and only retain factors of x^29 = 10*1+6*2=22

So total count is 22 + 1 (from previous case were a3=1) = 23.

A bit lengthy approach but can be used to come up with a closed formula for any n if we limit power terms to 1, 3, 9, 27