有多少个符合要求的数码串？

王守恩

一个数码串由  n 个数码组成，数码可以在 0, 1,2, 3, ..., n 里选取(可以重复),

要求:至少有 1 个数码小于 1, 至少有 2 个数码小于 2, 至少有 3 个数码小 3, ...

对某个 n(n=1, 2, 3, ...) 来说，问有多少个符合要求的数码串？

n=1, a(1)=1(0)

n=2, a(2)=3=1(0,0)+2(0,1)

n=3, a(3)=16=1(0,0,0)+3(0,0,1),+3(0,0,2)+3(0,1,1)+6(0,1,2)

northwolves

显然$a(n)=(n+1)^(n-1) $

王守恩

northwolves 发表于 2022-11-19 10:31
显然$a(n)=(n+1)^(n-1) $

谢谢 northwolves!  下面的还可以有吗？我好像卡住了，出不来。

一个数码串由  n 个数码组成，数码可以在 0, 1,2, 3, ..., n 里选取(可以重复),

要求:至少有 1 个数码小于 1, 至少有 2 个数码小于 2, 至少有 3 个数码小 3, ...

对某个 n(n=1, 2, 3, ...) 来说，问有多少个符合要求的数码串？

n=1, a(1)=1=(0)

n=2, a(2)=2=(0,0)+(0,1)

n=3, a(3)=5=(0,0,0)+(0,0,1),+(0,0,2)+(0,1,1)+(0,1,2)

northwolves

王守恩 发表于 2022-11-19 10:57
谢谢 northwolves!  下面的还可以有吗？我好像卡住了，出不来。

一个数码串由  n 个数码组成，数码可 ...

Number of partitions of [n] where the first k elements are marked (0 <= k <= n) and at least k blocks contain their own index.

        1, 2, 5, 14, 45, 164, 667, 2986, 14551, 76498, 430747, 2582448, 16403029, 109918746, 774289169, 5715471606, 44087879137, 354521950932, 2965359744447, 25749723493074, 231719153184019, 2157494726318234, 20753996174222511, 205985762120971168, 2106795754056142537

王守恩

northwolves 发表于 2022-11-19 14:25
Number of partitions of [n] where the first k elements are marked (0

谢谢 northwolves ！

1, 2, 5, 14, 45, 164, 667, 2986, 14551, 76498, 430747, 2582448, 16403029, 109918746, 774289169,
5715471606, 44087879137, 354521950932, 2965359744447, 25749723493074, 231719153184019,
2157494726318234, 20753996174222511, 205985762120971168,....

\(\D\ a(n)=\sum_{j = 0}^n\ b\bigg[ j, n - j\bigg]\)

总算鼓捣出上面的公式,(OEIS—A347420 给出的要比这复杂些)

答案不会有问题，可我还不知道\( b\bigg[j, n - j\bigg]\)是什么意思？

琢磨不透，盼好心网友再指点，感谢不尽！