这样的n位数有几个？

王守恩 发表于 2021-8-26 06:09:02

由数码 1, 2, 3 组成的自然数，要求：不能有3个2连在一起，不能有2个3连在一起。这样的n位数有几个？
a(1)=3
a(2)=8
a(3)=21
a(4)=55
a(5)=145
a(6)=381
a(7)=1002
a(8)=2635
a(9)=6929
这些数据(手工算的)，有问题吗？

aimisiyou 发表于 2021-8-26 07:04:18

ＤＰ动态规划可以解决。

aimisiyou 发表于 2021-8-26 10:46:26

本帖最后由 aimisiyou 于 2021-8-26 10:51 编辑

EXCEL列表很好求。

chyanog 发表于 2021-8-26 11:40:10

eqn={a+3a+3a+a-a==0, a==3, a==8, a==21, a==55};
RecurrenceTable
RSolve,n]
1 3
2 8
3 21
4 55
5 145
6 381
7 1002
8 2635
9 6929
10 18221
11 47915
12 126000
13 331337
14 871303
15 2291229
16 6025149
17 15844082
18 41664519
19 109563441
20 288114393
21 757642355
22 1992340376
23 5239174061
24 13777236647
25 36229422313
26 95270994813
27 250530145754
28 658808633779
29 1732441477793
30 4555728811205
31 11980009291675
32 31503328792448
33 82842984578881
34 217848727642455
35 572867677048117
36 1506446142504573
37 3961438341155170
38 10417228527455695
39 27393749655483041
40 72036196403820209
41 189430569293791587
42 498137635999157032
43 1309931682747475461
44 3444672495030141527
45 9058311020563830593
46 23820261189895838589
47 62639143419425230410
48 164719532545834379483
49 433156057394361417073
50 1139052346480036085341
51 2995318259720048705419
52 7876663003889075592144
53 20712930879883691381497
54 54467927017191100359527
55 143232026928229449985869
56 376651263623342900801085
57 990464056339488243218770
58 2604581855011396395939159
59 6849159841828119277984593
60 18010948839504116096259465
61 47362637986362151361249491
62 124547545885370253879920824
63 327517466204797175530432285
64 861258966659498507350202695
65 2264816640916362946942511513
66 5955693485394620249464337277
67 15661437774327001787872912186
68 41184227119919449884443661251
69 108300437540000678943397921153
70 284793125708134654209811978741
71 748908557462222042481209638139
72 1969373474326547491825282999072
73 5178778961377618260841745770865
74 13618418182452061517971035661239
75 35811784047026780818453331609189
76 94172748952842367646716958904573
77 247642134602656512916831806486722
78 651214151784716019830313713689247
79 1712470586498239442339413341472321
80 4503212194613199408227566860904801
81 11841908544064722307653579832876227
82 31140171039183754879184834153696840
83 81888003841715759469167687576512245
84 215337454786074390437910496397136247
85 566263887972837655790621641420639729
86 1489080434895391860391041027495282045
87 3915772467013843758545805128525122218
88 10297142890404606697528703631670023787
89 27077965484105151210129863741151876305
90 71205791991255894438744431049232596365
91 187246889581799011920265938296223418859
92 492395304898286755564417526299046860656
93 1294831315101556625851578498076566782633
94 3404963690533069822744373322911610217543
95 8953890440114398978912627334334674566269
96 23545670761916565080264900323598252427453
97 61917064468960528111087480793413673561522
98 162820711765586490111364437090124064760231
99 428162807898332168664334207775494517293425
100 1125921807363889788411954861749705984686137

mathe 发表于 2021-8-26 12:05:32

$\begin{bmatrix}1&1&0&1\end{bmatrix}
\begin{bmatrix}1&1&0&1\\
1&0&1&1\\
1&0&0&1\\
1&1&0&0
\end{bmatrix}^{n-1}
\begin{bmatrix}1\\1\\1\\1\end{bmatrix}$

mathe 发表于 2021-8-26 12:51:49

还可以写成和$u v^n$最接近的整数，其中u=1.152336014398158704564692591769565013208963817361889285965796552026372232190682833612396887282658993, v=2.629658126754534521161160112551052359293464130648116202335311523860560549252210311367997060312088641

hujunhua 发表于 2021-8-26 15:14:07

好恐怖啊，所有的回复我都看不懂呃。脑子生锈了么？

wayne 发表于 2021-8-26 16:45:59

直接考虑一般情况，我们的目标是要构建一个递推的规则，使得符合要求的$n-1$位数能够顺滑的通过递推关系变换到符合要求的$n$位数.
于是，我们发现可以根据末尾数字的特点总结到符合要求的数只有四种互斥状态。末位为$1$的，末二位为$12$或者$32$的，末二位为$22$的，末位为$3$的，我们分别记录为$S_1,S_2,S_3,S_4$这四个状态。
那么，$S_i$状态到$S_j$状态之间是否可以成功切换，根据计数的加法原理，我们将能切换的记为$1$，不能切换的记为$0$。比如$S_1 -> S_2$是$1$,$S_1 -> S_3$就是$0$.
接下来，全部笼而统之，我们记录$V_n$向量为分别是$S_1,S_2,S_3,S_4$这四种状态的$n$位数的个数构成的四元向量, 例如$V_1={1,1,0,1}$
于是可以得到$V_{n-1}$迁移到$V_n$的迁移矩阵$A=\left(
\begin{array}{cccc}
1 & 1 & 0 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 \\
\end{array}
\right)$,$V_{n}=V_{n-1}*A$，所以，立得,$V_n=V_1*A^{n-1}$ , 最终要计算$n$位数的所有情况，所以对$V_n$的所有分量求和，再乘以一个列向量${1,1,1,1}^{T}$
继续下去，计算矩阵的特征值，舍去模长小于1的特征根的成分，得到$a_n=$,【】是取圆整
其中$283 u^4-283 u^3-55 u^2+7 u-1 =0, u=1.1523360143981587045646925917695650132089638173619,$
$-1 - 3 v - 3 v^2 - v^3 + v^4 =0 ,v=2.6296581267545345211611601125510523592934641306481$,
=================
至于chyanog在#4的解答，也是同样的原理，只是不是矩阵形式，而是线性递推方程的形式。
矩阵的形式的优点不仅仅是过程非常清晰，还可以二分法计算幂，计算出了$A^n$的结果后，只需要平方就可以得到$A^{2n}$的结果，是$O(\log n)$的时间复杂度，计算效率更高，
而线性地推方程的难度比较大，而且计算过程是乌龟走路，老老实实的从最小的case开始慢慢线性累加，是$O(n)$的时间复杂度。

wayne 发表于 2021-8-26 18:36:07

chyanog 发表于 2021-8-26 11:40
chyanog的递推公式我知道怎么回事了。$a = a+3a+3a+a$
`a(n)`个符合要求的数可划分为四种，末位为 1 的有$f_1(n)$个，末二位为12或者32的有$f_2(n)$个，末二位为22的有$f_{22}(n)$个，末位为 3 的有$f_3(n)$个.
那么$a(n) =f_1(n)+f_2(n)+f_{22}(n)+f_3(n)$,
$ f_1(n) = f_1(n-1)+f_2(n-1)+f_{22}(n-1)+f_3(n-1)=a(n-1) $
$ f_2(n) = f_1(n-1)+f_3(n-1)=a(n-2)+f_3(n-1)$
$ f_{22}(n) =f_1(n-2)+f_3(n-2) =f_2(n-1)=a(n-3)+f_3(n-2)$
$f_3(n)=f_1(n-1)+f_2(n-1)+f_{22}(n-1)=a(n-1)-f_3(n-1)$
四式相加得$a(n)=2a(n-1)+a(n-2)+a(n-3)+f_3(n-2)$
上式前推得$a(n-1)=2a(n-2)+a(n-3)+a(n-4)+f_3(n-3)$
上两式相加，将 $f_3(n-2)+f_3(n-3)=a(n-3)$代入整理即得$$a(n)=a(n-1)+3a(n-2)+3a(n-3)+a(n-4)$$

王守恩 发表于 2021-8-27 15:04:00

本帖最后由王守恩于 2021-8-28 05:58 编辑

wayne 发表于 2021-8-26 16:45
hujunhua老大竟然说全部看不懂，不知真伪，哈哈哈，惊了我一吃，是钓鱼贴我也认了，甘愿被钓，顺便大家检验 ...

谢谢各位网友！斗胆求教，岂敢造次。因为这些数字串在OEIS好像找不到，我才求助的。

由数码 1, 2, 3, 4 组成的自然数，要求：不能有4个2连在一起，不能有3个3连在一起，不能有2个4连在一起。这样的n位数有几个？
a(1)=4
a(2)=15
a(3)=56
a(4)=208
a(5)=774
a(6)=2879
a(7)=10710
....
这些数据(手工算的)，有问题吗？

页: [1] 2 3

数学研发论坛's Archiver

这样的n位数有几个？