Split Members into Non-Decreasing Groups

Problem Count the ways to split n members into exactly k groups whose sizes are non-decreasing: size(i) >= size(i-1), every group non-empty.

Input / Output

• Input: integers n, k.
• Output: number of valid size sequences.

Constraints

• Order within a sequence is fixed (sizes sorted), so this is integer partition counting: partitions of n into exactly k parts. n, k up to a few hundred → O(n*k) DP.

Example

• n = 8, k = 4 → 5: [1,1,1,5], [1,1,2,4], [1,1,3,3], [1,2,2,3], [2,2,2,2].