用数字 1～6 及字母 A 组成长度为 n 的字串，规定数字不能相邻，能组成几种不同字串？

wintex

用数字 1～6 及字母 A 组成长度为 n 的字串，规定数字不能相邻，能组成几种不同字串？

lihp2020

1分类   0个数字 1
           1个数字 C(5,1)*6
           2个数字 C(4,2)*6^2
           3个数字 C(3,3)*6^3
2 长度是n是
        0个数字  1 =C(***,0)*6^0
        1个数字  C(n+1-1,1)*6^1
        k个数字  C(n+1-k,k)*6^k
       
        结果就是
        C(n+1-k,k)*6^k   k在 0,[(n+1)/2] 范围求和
        由于约定 m>n  C（n,m）=0  其实 k就可以写成 [0，无穷)

luyuanhong

王守恩

luyuanhong 发表于 2022-5-7 22:59

谢谢陆老师！大胆地，可以这样想吗？
   1, 7, 13, 55, 133, 463, 1261, 4039, 11605, 35839, 105469, 320503, 953317, 2876335, 8596237,
       通项公式：LinearRecurrence[{1, 6}, {0, 1}, 28]

p=1:  1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,2584,4181,6765,10946,17711,
p=2:  1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923,21845, 43691,87381,174763,
p=3:  1, 4, 7, 19,40, 97, 217, 508, 1159, 2683, 6160, 14209, 32689,75316,173383,399331,919480,
p=4:  1, 5, 9, 29, 65, 181, 441, 1165, 2929, 7589, 19305, 49661, 126881,325525,833049,2135149,
p=5:  1, 6, 11, 41,  96, 301,  781,  2286, 6191, 17621, 48576, 136681, 379561, 1062966, 2960771,
p=6:  1, 7, 13, 55, 133, 463, 1261, 4039, 11605, 35839,105469,320503,953317,2876335,8596237,
       通项公式：LinearRecurrence[{1, p}, {0, 1}, 28]