让我们挑选$m$元素来自$\{1,\dotsc,n\}$，让我们称这些为$a_1 < a_2 < \dotsc , a_m$. 显然，这些定义了一个严格的递增函数$f$从$\{1,\dotsc,m\} \to \{1,\dotsc,n\}$通过规则$f(i) = a_i$. 此外，在上述集合上定义的任何严格递增函数都是这种形式。

因此正好有${n \choose m}$严格递增函数。另一方面，总共有$n^m$这两个集合之间的函数映射。假设“随机”的 OP 意味着对$n^m$上面的函数，那么选择严格递增函数的概率为：

$$\frac{{n \choose m}}{n^m}$$

例如，对于$n >> m$，斯特林近似的应用，表明 RHS 是$\approx \frac{1}{m!}$.

让$S(n,m)$是子数组的数量$1 \leqslant k_1 < k_2 < \cdots < k_m \leqslant n$包含$m$整数值增加并由值 1 和$n$. 这个二元函数对所有整数都有很好的定义$1 \leqslant m \leqslant n$，给出值的三角数组。用一个简单的组合论证$^\dagger$我们可以建立以下定义这个二元函数的递归方程：

$$S(n+1,m) = S(n,m) + S(n,m-1) \quad \quad \quad \quad S(n,1) = n.$$

求解这个递归方程可以得到明确的公式：

$$S(n,m) = {n \choose m} = \frac{n!}{m!(n-m)!}.$$

（还有其他的组合参数也可以引导您得出这个结果。例如，选择递增函数等同于选择$m$共域中的值，然后按升序排列。）现在，为了得到结果，我们需要明确如何选择该域和共域上的“随机函数”。最简单的规范是说每个可能的映射以相等的概率被选择，这意味着有$n^m$等概率函数。因此，感兴趣的概率是：

$$\mathbb{P}(\text{Increasing Function}) = \frac{n!}{m!(n-m)! \cdot n^m}.$$

对大的采用一阶斯特林近似$n$给$\mathbb{P}(\text{Increasing Function}) \approx 1/m!$，这是一个非常粗略的估计，适用于$n$大大大于$m$. 所以基本上，我们看到，一旦这个问题的共域很大，随机得到一个递增序列的概率就很小；这符合直觉。

---

$^\dagger$如果$m=1$那么我们在映射中只有一个值，并且每个映射到任何$n$地方给出了一个增加的地图。因此我们有$S(n,1)=n$对所有人$n \in \mathbb{N}$. 此外，子数组的数量$S(n+1,m)$包括值出现在第一个的所有子数组$n$地方（有$S(n,m)$其中）以及最后一个值出现在最后一个位置并且其余值出现在此之前的所有子数组（有$S(n,m-1)$这些）。