A partition of a positive integer n is a way to write n as

Chapter 5, Problem 47E

(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 of 7 . Let \(P_{m}\) 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 \(P_{m-m}=P_{m}\)

b) Show that the following recursive definition for \(P_{m, n}\) is correct:

\(P_{m, n}= \begin{cases}1 & \text { if } m=1 \\ 1 & \text { if } n=1 \\ P_{m, m} & \text { if } m<n \\ 1+P_{m, m-1} & \text { if } m=n>1 \\ P_{m, n-1}+P_{m-n, n} & \text { if } m>n>1\end{cases}\)

c) Find the number of partitions of 5 and of 6 using this recursive definition.

Consider an inductive definition of a version ofAckermann's function. This function was named after WilhelmAckermann, a German mathematician who was a student of the great mathematician David Hilbert. Ackermann's function plays an important role in the theory of recursive functions and in the study of the complexity of certain algorithms involving set unions. (There are several different variants of this function. All are called Ackermann's function and have similar properties even though their values do not always agree.)

\(A(m, n)= \begin{cases}2 n & \text { if } m=0 \\ 0 & \text { if } m \geq 1 \text { and } n=0 \\ 2 & \text { if } m \geq 1 \text { and } n=1 \\ A(m-1, A(m, n-1)) & \text { if } m \geq 1 \text { and } n \geq 2\end{cases}\)

Equation Transcription:

Text Transcription:

n

n

P_m

m

P_m,n

m

n

P_m, m  P_m

P_m, n =

P_{m, n}= \begin{cases}1 & \text { if } m=1 \\ 1 & \text { if } n=1 \\ P_{m, m} & \text { if } m<n \\ 1+P_{m, m-1} & \text { if } m=n>1 \\ P_{m, n-1}+P_{m-n, n} & \text { if } m>n>1\end{cases}