## 19 Mar 2013

### Products of Integer Compositions: Lower Secondary Mathematics Competition Question

The partition of a natural number is a way of writing the number as the sum of positive integers. For example, (1+2) is a partition of 3. If the order of the numbers in the sum is important we call this a composition; if we only include unique sums then that is strictly a partition.

So, the number 3 can be composed into 4 sums: 3, 1+2, 2+1 and 1+1+1. However, the unique partitions of number 3 are just 3, 2+1 and 1+1+1. Note that the partition with parts 2 and 1 could be written in one of two ways; the convention is to order such sums with the highest numbers first. Although this is not vitally important, it is good practice so that it is easier to see that you have not missed out on any partitions - and that you haven't duplicated any.

Now, let us go back to the compositions of 3 and we shall replace the summation sign with a multiplication sign. We therefore get the following list:
3
2x1=2
1x2=2
1x1x1=1
The sum of these products is 3+2+2+1=8.

Now, repeat the above process for numbers 5 and 6. That is, list all the integer compositions of 5, replace the summation signs with multiplication signs, and finally add together all these products. Then do the same for number 6.

You now have three sums of the products of the compositions of 3, 5 and 6. What do you think this total will be for the numbers 4 and 7?

What do you think this total will be for the number 15?