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 Answer 1

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$
2
  • $\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
    Commented Feb 11, 2017 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$ Commented Feb 14, 2017 at 7:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .