这样的n位数有几个？

王守恩

由数码 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

ＤＰ动态规划可以解决。

aimisiyou

EXCEL列表很好求。

chyanog

1. eqn={a[n-4]+3a[n-3]+3a[n-2]+a[n-1]-a[n]==0, a[1]==3, a[2]==8, a[3]==21, a[4]==55};
   
2. RecurrenceTable[eqn,a,{n,100}]
   
3. RSolve[eqn,a[n],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

\(\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

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

hujunhua

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

wayne

直接考虑一般情况，我们的目标是要构建一个递推的规则，使得符合要求的$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=[u*v^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

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

chyanog的递推公式我知道怎么回事了。$a[n] = a[n-4]+3a[n-3]+3a[n-2]+a[n-1]$
`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)$$

王守恩

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
....
这些数据(手工算的)，有问题吗？