Skip to main content
3 of 6
added 461 characters in body
Pat Devlin
  • 2.7k
  • 16
  • 21

Let $S = \{(a_1, \ldots , a_c) \ : \ \sum_i i a_i = n\}$, and for $a \in S$, let $f(a) = 1/\prod_i a_i !$. Then the exact value you want is $n! \sum_{a \in S} f(a)$ [the term $n! f(a)$ counts the number of such decompositions with $a_i$ sets of size $i$].

We can bound this by finding some $f(a) \leq \Delta$, which would give

$$\Delta \leq N / n! \leq |S| \Delta = p_c (n) \Delta$$

where $N$ is the number you want, and $p_c (n)$ is the number of partitions of $n$ into parts of size at most $c$. (Then use Stirling's formula and some useful upper bound on like perhaps $p_c (n) \leq p(n) \sim \frac{1}{4n \sqrt{3}} \exp[\pi \sqrt{2n/3}].$)

Is that good enough? If not, you could get more mileage out of these bounds.

Added:

Or in the case where each set is to have size between $c/2$ and $c$, define the same $S$ as before (except insisting $a_i =0$ for $i<c/2$). Then for $a \in S$, we have $n/c \leq \sum a_i \leq 2n/c$. Thus

$$N \leq \sum_{a \in S} n! / f(a) \leq (n-2n/c)! \sum_{a \in S} n! / [f(a) (n-\sum_i a_i)!] \leq (n-2n/c)! n^{2+c/2}.$$

And we can then combine this with $N \geq n! / (n/c)!$ to get a moderately decent approximation.

Is that close enough?

Pat Devlin
  • 2.7k
  • 16
  • 21