数字重复不超过k次的n位自然数有多少个？

Question

用数字 0123456789 构成的 n 位自然数，同一个数字最多可以使用 k 次，这样的自然数有多少个？

这是个排列问题。
8位数以内，可以简单枚举，验证所有排列，统计出结果；
50位数以内，可以通过编程，枚举各种组合，并计算这些组合的排列数，也可以较快获取答案。

但是，如果 n 非常大，比如 n > 100，编程计算的效率就会大大降低，甚至无法快速得出结果。

有没有直接的数学公式用于解决这个问题？

附几个编程计算（算法经过暴力试算验证，n<15）的结果，供参考。
n = 3，k = 2，sum = 891；
n = 5，k = 3，sum = 89586；
n = 7，k = 2，sum = 6735960；
n = 7，k = 5，sum = 8999424；
n = 12，k = 3，sum = 676277910000；
n = 12，k = 7，sum = 899969278230；
n = 20，k = 6，sum = 87854227537752932256；
n = 20，k = 15，sum = 89999999999706287916；
n = 50，k = 5，sum = 44208412655479319001657875464053429213265920；
n = 50，k = 25，sum = 89999999999903263796855035287011129723445086257116；
n = 50，k = 50，sum = 90000000000000000000000000000000000000000000000000；
n = 100，k = 30，sum = 8999999455766537139925815663912466168371880602271949761777640859936611152005697831429106355805635456。

上述例子，加粗的为特例，可以直接通过数学方法计算结果；
最后一个是枚举组合+计算排列，枚举了3068977个组合，耗时5分钟；
n < 30 时，计算耗时在 0.1 秒以内；
n < 50 时，计算耗时在 1 秒以内。

求直接计算的数学方法，或者更快的算法。

Answer 1

这是求有限数字构成的全排列数量的问题。

用数学方法，可以使用生成函数求解。

设生成函数为：

F(x) = (1 + x + x^2 + ... + x^k)^n

其中，n 为数字个数，k 为同一数字使用次数限制。

系数对应的数字，即为答案。

但是，这样的生成函数可能会很大，难以直接求解。

如果 n 很大，而 k 比较小，可以使用拉格朗日反演等方法求解。

如果 n 很小，而 k 比较大，可以使用组合数学的方法求解。

但是，如果 n 和 k 都很大，建议使用数值计算方法，比如多项式乘法、矩阵乘法等。

总之没有直接的数学公式，需要根据实际情况，选择合适的方法解决。