当前位置：文江博客话题详情

计算特定数字出现超过 n 次的数字组合

发布于 2025-01-13 01:31:41 字数 122 浏览 2 评论 0原文

当特定数字出现超过 n 次时，我们如何计算数字组合？例如：在 4 位数字 1112 中，1 出现 3 次。 1211、1121、2111、1111 也是这样的数字。基本上 1 多于 2 倍（3,4 倍）计算这种排列的公式是什么

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

橘和柠 2025-01-20 01:31:41

假设 f(n, k) 是 n 位数字的计数，其中特定数字重复 k 次，其中 k <= n。

我们可以首先考虑所有没有指定数字的 nk 位数字，然后考虑插入该数字的所有方法。

有 9^(nk) 个数字为 nk 的数字没有指定的数字。这包括带有前导零的数字（如果不允许，请评论）。

现在，对于其中的每一个，我们可以通过多少种方式插入指定数字的 k 个副本？

答案是n！ / (k! * (nk)!)，即n个事物的排列数除以非指定数字（我们不想在它们之间进行排列）的排列数和排列数指定数字（同上）。

所以 f(n,k) = 9^(nk) * n！ / (k! * (nk)!)

现在，您要求的是 n 位数字的计数，其中特定数字重复 k 次或更多次，其中 k <= n。我们称之为 g(n,k)。

g(n,k) = sum(f(n,i)) for i in {k, k+1, ..., n}

示例代码 (Ruby)：（事实是阶乘）

def f(n,k)
  return 9**(n-k)*fact(n) / (fact(k)*fact(n-k))
end

def g(n,k)
  ans = 0
  k.upto(n) do |i|
    ans += f(n,i)
  end
  return ans
end

示例输出：

g(5,0) = 100,000 (as expected, all possible 5 digit numbers = 10**5)
g(5,1) =  40,951 (as expected, 10**5 - 9**5)
g(5,2) =   8,146
g(5,3) =     856
g(5,4) =      46
g(5,5) =       1

Let's say f(n, k) is the count of n digit numbers where a specific digit is repeated k times, for k <= n.

We can start by considering all n-k digit numbers that don't have the specified digit, then all ways of inserting that digit.

There are 9^(n-k) numbers with n-k digits that don't have the specified digit. This includes numbers with leading zeroes (comment if these are disallowed).

Now, for each of these, in how many ways can we insert k copies of the specified digit?

The answer is n! / (k! * (n-k)!), which is the number of permutations of n things, divided by the number of permutations of the non-specified digit (which we don't want to permute among themselves) and the number of permutations of the specified digit (ditto).

So f(n,k) = 9^(n-k) * n! / (k! * (n-k)!)

Now, what you asked for is the count of n digit numbers where a specific digit is repeated k OR MORE times, for k <= n. Let's call this g(n,k).

g(n,k) = sum(f(n,i)) for i in {k, k+1, ..., n}

Sample Code (Ruby): (fact is factorial)

def f(n,k)
  return 9**(n-k)*fact(n) / (fact(k)*fact(n-k))
end

def g(n,k)
  ans = 0
  k.upto(n) do |i|
    ans += f(n,i)
  end
  return ans
end

Sample output:

g(5,0) = 100,000 (as expected, all possible 5 digit numbers = 10**5)
g(5,1) =  40,951 (as expected, 10**5 - 9**5)
g(5,2) =   8,146
g(5,3) =     856
g(5,4) =      46
g(5,5) =       1

回复收藏 0 原文

~没有更多了~