Programmieraufgabe: Partitionen

Definition

eine Partition einer natürlichen Zahl n ist eine Liste von positiven natürlichen Zahlen [x1, ..., xk] mit x1 + ... + xk = n und x1 >= ... >= xk.

Beispiel

partitions :: Int -> [ Partition ]
partitions 5 = [Partition [5],Partition [4,1],Partition [3,2],
                Partition [3,1,1],Partition [2,2,1],
		Partition [2,1,1,1],Partition [1,1,1,1,1]]

Programm

Die Liste aller Partitionen einer Zahl bestimmen wir mit diesem Programm.

Aufgabe

Schreibe eine Funktion u_partitions, die die Liste aller Partitionen bestimmt, die nur aus ungeraden Zahlen bestehen. - Beispiel:

u_partitions 5 =
[Partition [5],Partition [3,1,1],Partition [1,1,1,1,1]]

Schreibe eine Funktion f_partitions, die die Liste aller Partitionen bestimmt, die streng monoton fallend sind. - Beispiel:

f_partitions 5 =
[Partition [5],Partition [4,1],Partition [3,2]]

Finde einen Zusammenhang zwischen length (u_partitions n) und length (f_partitions n) und beweise diesen.