python - 给定 n 个数字和 k 个槽。这样对于每个槽，它可以是 0，也可以是小于前一个数字的数字，组合学

Question

我遇到编码问题。给定 n 个数字和 k 个槽。这样对于每个槽，它可以是 0，也可以是小于前一个数字的数字。例如

对于 n=4，k=4

0000, 3000, 3200, 3210 etc.

对于 n=7，k=3

000, 700, 541, 731, 540 etc.

谁能告诉我这里的模式是什么，换句话说，描述可能性数量的公式是什么？

一些说明问题的Python代码(代码本身并不重要，我正在寻找make_encod(n,k)的封闭形式)

from math import factorial
import math

def make_encod(n,k):
    tol=[""]
    for i in range(0,k):
        tol=make_strin_from_tile(0,max(n-i,1),tol)
    print(len(tol))
    print(tol)


def make_strin_from_tile(f,t,all):
    a=[]
    for b in all:
        for i in range(f,t):
            if len(b)==0 or int(b[-1])>i or int(b[-1])==0==i:
                a.append(f"{b}{i}")
    return a
#just some examples
print(make_encod(3,1))
print(make_encod(3,2))
print(make_encod(3,3))
print(make_encod(5,4))

将输出:

> 3
['0', '1', '2']
None
4
['00', '10', '20', '21']
None
4
['000', '100', '200', '210']
None
16
['0000', '1000', '2000', '2100', '3000', '3100', '3200', '3210', '4000', '4100', '4200', '4210', '4300', '4310', '4320', '4321']
None

我正在寻找一个公式来告诉我 make_encod(n,k)) 的答案？一定有比实际经历这个更聪明的事情

Answer 1

如果我正确理解了条件，这个问题就会映射到

What is the number of combinations to pick up to k elements from a set of n distinct numbers

因为你可以通过从有序集合 [ n, n-1, n-2 ... 1] 中划掉除 k 或更少 之外的所有组合，然后填充剩余的任何组合，从而获得所有合法组合带零的槽。

n 组中 k 个或更少的对象的数量为

( n! / n! ) + ( n! / (n-1)! ) + ... + ( n! / (n-k)! ) 
= sum_(i=0)^k (n!)/((n - i)!)

目前我无法说出明确的公式。我可能稍后会回来尝试解决这个问题，但欢迎任何比我更擅长解决算术问题的人这样做。

免责声明:我从来没有用英语做过数学，所以如果我的某些词汇有问题，请原谅