n元集各部分至少含k个元素的s划分的计数、阶与上下界咨询

Great question! This is a well-studied variation of Stirling numbers of the second kind, often referred to as restricted Stirling numbers of the second kind (restricted to subsets of size at least k). Let’s break down the key results and bounds you’re asking about:

Basic Definition & Key Transformation #

We typically denote this count as $S(n, s, k)$—it represents the number of ways to partition an n-element set into s non-empty subsets, where each subset contains at least k elements.

A critical simplification ties this directly to standard Stirling numbers of the second kind ($S(n, s)$): if each subset must have at least k elements, we can first allocate $k-1$ elements to each of the s subsets, leaving $m = n - s(k-1)$ elements to distribute into s non-empty subsets (each now needing at least 1 more element). This gives us the identity:
$$
S(n, s, k) =
\begin{cases}
S(m, s) & \text{if } m = n - s(k-1) \geq s \quad (\text{i.e., } n \geq sk), \
0 & \text{otherwise}.
\end{cases}
$$
When $k=1$, this reduces exactly to the standard Stirling number $S(n, s)$, which makes intuitive sense.

Asymptotic Equivalents (Order of Magnitude) #

Using the transformation above, we can leverage known asymptotic results for standard Stirling numbers to get equivalents for $S(n, s, k)$:

1. Fixed s and k, n → ∞:
   For standard Stirling numbers, when s is fixed and n grows large, $S(n, s) \sim \frac{s^n}{s!}$. Substituting $m = n - s(k-1)$, we get:
   $$
   S(n, s, k) \sim \frac{s^{n - s(k-1)}}{s!} = \frac{s^n}{s! \cdot s^{s(k-1)}}.
   $$
   This is the dominant term as n becomes very large.

2. Growing s and n (with $n \geq sk$):
   If both n and s grow such that $\frac{s}{n} \to \lambda$ (where $\lambda \leq \frac{1}{k}$, since each subset needs at least k elements), we can use the entropy-based asymptotic for standard Stirling numbers. For $S(m, s)$ where $m = n - s(k-1)$, the logarithmic asymptotic is:
   $$
   \log S(n, s, k) = \log S(m, s) = m H\left(\frac{s}{m}\right) - \frac{1}{2}\log\left(\frac{m}{2\pi s(m-s)}\right) + o(1),
   $$
   where $H(p) = -p\log p - (1-p)\log(1-p)$ is the binary entropy function. Substitute $m = n - s(k-1)$ to get the result in terms of n, s, k.

Upper and Lower Bounds #

Again, we can adapt bounds for standard Stirling numbers to $S(n, s, k)$:

Lower Bounds #

• A simple lower bound comes from the first term of the inclusion-exclusion formula for standard Stirling numbers, applied to $S(m, s)$:
  $$
  S(n, s, k) = S(m, s) \geq \frac{s^m}{s!} - \frac{s(s-1)^m}{s!},
  $$
  where $m = n - s(k-1)$. For large n, the first term dominates.
• For a combinatorially motivated lower bound: the number of ways to partition n elements into s subsets each of size at least k is at least the number of ways to split sk elements into s k-element subsets:
  $$
  S(n, s, k) \geq \frac{n!}{s! \cdot (k!)^s}.
  $$

Upper Bounds #

• Using the upper bound for standard Stirling numbers ($S(m, s) \leq \frac{s^m}{s!}$), we get:
  $$
  S(n, s, k) \leq \frac{s^{n - s(k-1)}}{s!}.
  $$
• A tighter combinatorial upper bound comes from counting ordered partitions (where subset order matters) and dividing by $s!$ (to account for unordered subsets). For ordered partitions, we first choose k elements for each subset, then assign the remaining $n-sk$ elements to any subset:
  $$
  S(n, s, k) \leq \frac{n! \cdot s^{n - sk}}{s! \cdot (k!)^s}.
  $$

Additional Context #

These restricted Stirling numbers appear in combinatorial enumeration problems where you need to enforce minimum subset sizes—you’ll find references to them in texts like Concrete Mathematics or specialized combinatorics papers focused on partition enumeration.

内容的提问来源于stack exchange，提问作者user2130010