我正在尝试解决 TopCoder 上的问题。基本上我需要的是以下算法：
令 S = [1, 2, ..., n] 是一个序列。让 m 小于 n。
1) 找到大小为 m 的 S 的所有子序列（这很容易 - n^m）。
2) 找到大小为 m 的 S 的所有子序列，其中元素处于非递减顺序。
3) 找出大小为 m 的 S 的所有子序列，其中元素不允许重复（这也很容易 - (n!)/((nm)!）。
4) 找出大小为 m 的 S 的所有子序列，其中元素处于非递减顺序且不允许重复。
仍在尝试寻找第 2 部分和第 4 部分的公式。我们将不胜感激。
提前致谢。
编辑：
原始问题：
https://docs.google.com/document/d/1X1VK8Vq2DlqMbZpXHGLoWv9ULfRLVoLtMTRRU5nh5qs/edit?usp=sharing
要解决 4)，请注意没有重复“非减少”意味着“增加”。将由不重复元素m构建的所有长度序列的集合划分为由出现在子序列中的元素集合定义的等价类。S在每个等价类中，只有一个递增序列（按 排序的元素<）。每个等价类的大小是元素的排列数。因此 4)-序列的数量是(n!)/((n-m)! * m!) = n \choose m.
ad 2)，将序列建模为S. 这可以写成一个(s_i, k_i), i=1..n; s_i \in S, k_i \in IN, \foreach p,q in {1..n}, p!=q: s_p != s_q长度对的序列n。“非递减”意味着通过根据递增排列元素给出的序列的唯一允许排序s_i。因此唯一的自由度是出现次数，它必须服从求和到 m: 的约束sum_{i=1..n} k_i = m。
这个问题等同于具有（特定）限制和计算格路径的分区。我认为IN^n满足此条件的 n 元组数量没有封闭公式。
但是，有一个标准算法可以枚举所有可能性，例如。这里