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].

Expected approach

• DP on partitions: f(n, k) = f(n-1, k-1) + f(n-k, k) — either some group has size exactly 1 (remove it), or every group has size >= 2 (subtract 1 from each of the k groups). Base cases f(0,0)=1, f(n,0)=0, f(n,k)=0 for n<k. O(nk) time, O(nk) (or rolling O(n)) space. Recursion + memoization is equally accepted.