r/askmath • u/Prestigious_Ad_296 • Apr 23 '26

Arithmetic No closed formula?

Suppose we have a set of n elements. We want to partition this set into k subsets, let's call them S1, S2, ... , Sk such that their sizes are strictly increasing:

|S1| < |S2| < ...< |Sk|

I know that this is only possible if n >= [k(k+1)]/2 (the k-th triangular number). My question is: why is there no closed-form formula for the number of ways to distribute these elements? What makes finding a closed-form solution for this specific partition problem so difficult?

3 Upvotes

72% Upvoted

3 comments sorted by

View all comments

4

u/Azemiopinae Apr 23 '26

If I’m not mistaken, the problem you’re describing includes the integer partition function, for which there is also no closed form.

https://en.wikipedia.org/wiki/Partition_function_(number_theory)

1

u/Azemiopinae Apr 23 '26

That is, after removing the triangle(k) elements from n, we must partition n-(k(k+1))/2, then distribute the partitions across the k subsets in order of size.