Pythonで自然数の分割(要素最大値に制限があり・順序を考慮)を求める。

若干研究にも関係する話。

自然数の分割とはどういうものか。
例えばWikipediaの例をそのまま借りると、
4の分割は、
4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1
である。

このとき、普通は順序を考慮しないので 1 + 3 は 3 + 1 に含まれる。
今回、順序を考慮しない分割が欲しいとする。
また、要素の最大値に制限があり、3までとする。
その場合、上の例で言うと「4」は 要素の最大値3を超えているので除外される。

これをPythonで求めたくてググると、
list - Number of ways to partition a number in Python - Stack Overflow
という「順序を考慮する例」が出てきたので、順序を考慮しないように変更してみた。

プログラミングコンテストとかやっていれば、
こういうのスラスラ書けるんだろうなぁ。