3
$\begingroup$

Given positive integers $n$ and $c$, with $n>c$, is there a good way to estimate the number of ways to partition the set $\{1,\dots,n\}$ into ordered subsets, with each subset having at most $c$ elements? By "ordered subsets", I mean that the ordering within each subset matters, but we don't care about the order in which the subsets are presented to us, e.g. the partitions $\{1,2,3\},\{4,5,6\}$ and $\{3,2,1\},\{4,5,6\}$ are distinct, but $\{1,2,3\},\{4,5,6\}$ and $\{4,5,6\},\{1,2,3\}$ are the same. How about if we only consider partitions into subsets whose sizes are all between $c/2$ and $c$?

As an aside, in my actual problem, I am interested in the asymptotic behavior as $n\to\infty$ with $c=a\sqrt{n}$, with $a$ a constant.

$\endgroup$
1
$\begingroup$

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)! (2+c/2)^n.$$

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

Is that close enough?

Second edit:

Or in the above setting, we can use $|S| \leq (n/c) p_{c} (2n/c)$ and then follow as in the first idea.

Third edit:

Let $g(n,c)$ denote the number of decompositions into sets of size at most $c$. Then we have the exponential generating function:

$$G_c (z) = \sum_{n} \frac{g(n,c)}{n!} z^n = \prod_{k=1}^{c} \sum_{j=0} ^{\infty} \frac{z^{jk}}{j!} = \prod_{k=1}^{c} e^{z^k} = e^{z (z^c -1)/(z-1)}.$$

Thus, we are trying to estimate $G_c ^{(n)} (0)$. (Just a thought)

$\endgroup$
  • $\begingroup$ See the bottom of page 9 of this pdf for how to estimate the coefficients of the exponential power series given in the third edit. It seems like those techniques would work here. math.upenn.edu/~pemantle/papers/twenty.pdf $\endgroup$ – Pat Devlin Feb 11 '17 at 20:11
  • 1
    $\begingroup$ For constant c these methods apply directly and are even implemented in computer algebra. For c growing like sqrt(n), you usually have to justify separately that the integral is indeed concentrated where you expect it to be. $\endgroup$ – Bruno Salvy Feb 14 '17 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.