Solved: A partition of a positive integer n is a way to

Chapter 4, Problem 4.3.47

(choose chapter or problem)

A partition of a positive integer n is a way to write n as a sum of positive integers where the order of terms in the sum does not matter. For instance, 7 = 3 + 2 + 1 + 1 is a partition of7. Let Pm equal the number of different partitions of m, and let P m,n be the number of different ways to express m as the sum of positive integers not exceeding n. a) Show that Pm,m = Pm. b) Show that the following recursive definition for Pm,n is correct: 1 1 1 Pm,n = Pm,m 1 + Pm,m-l Pm,n-l + Pm-n,n ifm = 1 if n = 1 ifm < n ifm = n > 1 ifm > n > 1. c) Find the number of partitions of 5 and of 6 using this recursive definition.