用 n 个在 0～n 中的数码组成字串，小于 k 的数码至少要有 k 个, 这样的字串有几个？

王守恩

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

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

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

王守恩

一个数码串由  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)

王守恩

一个数码串由  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)

王守恩

一个数码串由  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)

{1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 2357947691, 61917364224,
1792160394037, 56693912375296, 1946195068359375, 72057594037927936, 2862423051509815793,
121439531096594251776, 5480386857784802185939,

\(a(n)=(n+1)^{n-1}\)

王守恩

一个数码串由  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)

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

有高人在2022年搞了个通项公式，具体见OEIS—A347420        。

琢磨许久，还是不会，盼好心网友指点一二，感谢不尽！

lihp2020

OEIS 都收录 了 应该 下面有解释说明三

王守恩

lihp2020 发表于 2022-11-22 12:12
OEIS 都收录 了 应该 下面有解释说明三

谢谢 lihp2020 的鼓励！

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

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

很不容易鼓捣出上面的公式,(OEIS—A347420 比这要复杂些)

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

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

王守恩

注意其中细腻的差别。OEIS 中的通项公式可没有这样简单的。

A347420   \(\displaystyle\ a(n)=\sum_{j = 0}^n\ b\bigg[ n - j,j\bigg]\)
{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,, .....

A347420   \(\displaystyle\ a(n)=\sum_{j = 0}^n\ b\bigg[ j, n - j\bigg]\)
{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, ......

A005490   \(\displaystyle\ a(n)=\sum_{j = 0}^{n-1}\ b\bigg[ n - j,j\bigg]\)
{0, 1, 4, 13, 44, 163, 666, 2985, 14550, 76497, 430746, 2582447, 16403028, 109918745, 774289168,
5715471605, 44087879136, 354521950931,2965359744446, 25749723493073, 231719153184018,
2157494726318233, 20753996174222510, 205985762120971167, 2106795754056142536, ......

A005490   \(\displaystyle\ a(n)=\sum_{j = 1}^{n}\ b\bigg[ j,n - j\bigg]\)
{0, 1, 4, 13, 44, 163, 666, 2985, 14550, 76497, 430746, 2582447, 16403028, 109918745, 774289168,
5715471605, 44087879136, 354521950931,2965359744446, 25749723493073, 231719153184018,
2157494726318233, 20753996174222510, 205985762120971167, 2106795754056142536, ......

A350589   \(\displaystyle\ a(n)=\sum_{j = 1}^{n}\ b\bigg[ n - j,j\bigg]\)
{0, 1, 3, 9,  30, 112,  464,  2109, 10411, 55351, 314772,  1903878, 12189432, 82274309, 583389847,
4332513061, 33607736990, 271657081128,2283282938288, 19916981288017, 179994994948647,
1682624910161483, 16247280435775188, 161833756265886822, 1660836884761337248,  ......

A350589   \(\displaystyle\ a(n)=\sum_{j = 0}^{n-1}\ b\bigg[ j, n - j,j\bigg]\)
{0, 1, 3, 9,  30, 112,  464,  2109, 10411, 55351, 314772,  1903878, 12189432, 82274309, 583389847,
4332513061, 33607736990, 271657081128,2283282938288, 19916981288017, 179994994948647,
1682624910161483, 16247280435775188, 161833756265886822, 1660836884761337248,  ......