f(n,k) = (k+1)(f(n-1,k-1) + f(n-1,k))
您想要的是它们的总和（从零到n-1），以下代码是用c#编写的（仅针对简单情况进行了测试），实际上我们只计算可能的方法数量而不是生成所有方法。
class EqualInequalPermutation
{
public int OrderingsNumber(int n)
{
int[][] f = new int[n+1][];
for (int i = 0; i < n+1; i++)
{
f[i] = new int[n];
for (int j = 0; j < n; j++)
f[i][j] = 0;
}
f[1][0] = 1;
int factorial = 1;
for (int i = 1; i <= n; i++)
{
f[i][0] = 1;
factorial *= i;
f[i][i - 1] = factorial;
for (int k = 1; k < n; k++)
{
f[i][k] = (k + 1) * (f[i - 1][k - 1] + f[i - 1][k]);
}
}
int answer = 0;
for (int i = 0; i < n; i++)
{
answer += f[n][i];
}
return answer;
}
}
我发现整数序列在线百科全书是解决这类问题的好资源。你已经提供了足够的信息来得到答案。显然，对于零个数字的退化情况，只有一种排序方式可能。同样，对于一个数字，只有一种排序方式存在。对于两个数字，你说有三种排序方式，而对于三个整数，则有十三种。搜索1,1,3,13，第一个弹出的匹配项是这个，“n个竞争者在比赛中排名的方式数量，允许平局的可能性。”从那里开始，你将看到这个序列中的前二十个或更多结果，以及人们在序列上贡献的内容。其中包括Mathematica中的递归解决方案（在此进行了重新格式化和扩展以进行澄清）：
f[0] = 1
f[1] = 1
f[n_] := f[n] = Sum[ Binomial[n,k] * f[n-k], {k,1,n}] (* memoizes the values *)
如果您喜欢，您可以轻松地在其他语言中实现它。
希望这有所帮助，并且您将来会发现OEIS很有用！
由于我偶然遇到了这个问题，但在搜索结果中找不到简单的Python实现。 为了以后参考，在下面提供了Python版本的简单实现。
虽然我们可以在这里获得更全面的数学证明。 以下代码将简单地遵循@Saeed Amiri提供的公式：
f(n,k) = (k+1)(f(n-1,k-1) + f(n-1,k))
def bell_number(num: int) -> int:
dp = [[0] * num for _ in range(num)]
dp[0][0] = 1
for n in range(1, num):
for k in range(num):
dp[n][k] = (k+1) * (dp[n-1][k-1] + dp[n-1][k])
return sum(dp[-1])
//This is the C++ version of the Same Code
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
dp[1][0] = 1;
int f = 1;
for(int i = 1; i <= n; ++i) {
dp[i][0] = 1;
f = f * i;
dp[i][i - 1] = f;
for(int j = 1; j <= n; ++j)
dp[i][j] = (j + 1) * (dp[i - 1][j - 1] + dp[i - 1][j]);
}
int ans = 0;
for(int i = 0; i < n; ++i)
ans += dp[n][i];
cout<<ans;
return 0;
}
我认为，通过动态规划来解决这个问题就像用机枪杀蚂蚁一样。
你应该使用组合数学，因为它不应该那么困难。
当没有相等时，它是 n!（排列），然后你必须计算组合（所有相等的 n 元组），所以对于 3 来说：
3! + 2*(3 over 2) + (3 over 3) = 13
static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Missing argument - the number of items");
return;
}
int n;
if (!int.TryParse(args[0], out n))
{
Console.WriteLine("Could not parse number of items");
return;
}
if (n < 0)
{
Console.WriteLine("Number of items must not be negative");
return;
}
var count = GetOrderings(n);
Console.WriteLine("Total: {0}", count);
}
private static int GetOrderings(int n)
{
var items = Enumerable.Range(0, n).Select(i => (char)('a' + i)).ToList();
// Produce distinct orderings of the input items
return GetOrderings(new List<char>(), items);
}
private static int GetOrderings(List<char> current, List<char> items)
{
// If we have a complete permutation in current, produce the possible arrangements of signs between them
if (items.Count == 0) return GetSigns(new List<char>(), current, 0);
var result = 0;
for (var i = 0; i < items.Count; i++)
{
// nextCurrent = current + i'th element of items
var nextCurrent = new List<char>(current) { items[i] };
// nextItems = items excluding the i'th element
var nextItems = new List<char>(items.Where((c, n) => n != i));
result += GetOrderings(nextCurrent, nextItems);
}
return result;
}
private static int GetSigns(List<char> signs, List<char> items, int n)
{
if (signs.Count >= items.Count - 1)
{
// Once we have sufficient signs, write out the items interleaved with them
var str = string.Empty;
for (var i = 0; i < items.Count; i++)
{
if (i > 0) str += signs[i - 1];
str += items[i];
}
Console.WriteLine(str);
return 1;
}
var result = GetSigns(new List<char>(signs) { '<' }, items, n + 1);
// To prevent duplicate orderings, only allow "=" between two items if they are in lexicographic order
// (i.e. allow "a = b" but not "b = a")
if (items[n] >= items[n + 1]) return result;
return result + GetSigns(new List<char>(signs) { '=' }, items, n + 1);
}
示例输出（当n = 3时）：
a<b<c a<b=c a=b<c a=b=c a<c<b a=c<b b<a<c b<a=c b<c<a b=c<a c<a<b c<a=b c<b<a 总计：13