2013 Mathcounts State Prep: Partition Questions

#24 2001 Mathcounts Sate Sprint Round: The number 4 can be written as a sum of one or more natural numbers in exactly five ways: 4, 3+1, 2 + 1 + 1, 2 +2 and 1 + 1 + 1 + 1; and so 4 is said to have five partitions. What is the number of partitions for the number 7?

#2: Extra: Try partition the number 5 and the number 8. 

Solution: 

#24: You can solve this problem using the same technique as counting coins:

Counting coins questions

7     6    5    4    3    2    1

1                                           1 way

       1                                    1 way

             1                 1           2 ways ( 5 + 2 or 5 + 1 + 1)

                   1    1                  1 way

                   1           1           2 ways ( 4 + 2 + 1 or 4 + 1 + 1 + 1)

                         2     0   1      1 ways

                         1     2           3 ways ( 3 + 2 + 2, 3 + 2 + 1 + 1 and 3 + 1 + 1 + 1 + 1)

                                3           4 ways (2 + 2 + 2 + 1, 2 + 2 + 3 ones, 2 + 5 ones and 7 ones.)

Total 15 ways.

The partitions of 5 are listed below (There are 7 ways total.):

5   4   3   2   1

1                           1 way

     1                      1 way

          1    1           2 ways  (3 + 2 and 3 + 1 + 1)

                2           3 ways  (2 + 2 + 1, 2 + 1 + 1 + 1 and 1 + 1 + 1 + 1 + 1)

There are 22 ways to partition the number 8.