随机行走问题-组合数学

markfang2050

从 A 到 B 距离为 2019 ，每一步可随机走距离 1、3 或 5，从 A 到 B 共有几种走法？

mathe

各种随机行走问题都很类似
也就是这个定义了递推数列$a(n)=a(n-1)+a(n-3)+a(n-5)$而且$a(0)=1,a(-1)=a(-2)=a(-3)=a(-4)=0$,现在要求f(2019)
可参考https://bbs.emath.ac.cn/forum.ph ... 2858&fromuid=20
而本题中特征多项式为$f(x)=x^5-x^4-x^2-1$,其中只有一个绝对值大于1的实数根1.5701473121960543629106654351371265539...
我们不妨记$g(x)=x^5+x^3+x-1$,它的五个根为$r_1,r_2,r_3,r_4,r_5$,我们于是可以设$a(n)=\sum_{h=1}^5 s_h r_h^{-n}$
根据前面初始值，我们要求
\(\begin{pmatrix}r_1^0&r_2^0&r_3^0&r_4^0&r_5^0\\
r_1^1&r_2^1&r_3^1&r_4^1&r_5^1\\
r_1^2&r_2^2&r_3^2&r_4^2&r_5^2\\
r_1^3&r_2^3&r_3^3&r_4^3&r_5^3\\
r_1^4&r_2^4&r_3^4&r_4^4&r_5^4\end{pmatrix}
\begin{pmatrix}s_1\\s_2\\s_3\\s_4\\s_5\end{pmatrix}=\begin{pmatrix}1\\0\\0\\0\\0\end{pmatrix}\)
相当于求左边矩阵逆矩阵的第一列。
然后类似链接中方法
定义$g_k(x)=\sum_{h=1}^5 \frac{r_h^k g(x)}{(x-r_h)g'(r_h)}-x^k$
可以知道$g_k(0)$在k=0时为1，在$1\le k\le 4$时为0。
也就是$s_k=-\frac{g(0)}{r_kg'(r_k)}={44 r_k^4 + 38 r_k^3 + 60 r_k^2 + 72 r_k + 123}/407$
于是$a(n) = \sum_{k=1}^5 {(44 r_k^4 + 38 r_k^3 + 60 r_k^2 + 72 r_k + 123)r_k^{-n}}/407$,其中$r_k$是方程$x^5+x^3+x-1=0$的五个根
可以有近视$a(n)~=0.51658132372415288866267360665702792385*0.63688291680184484849006828045032413658^{-n}$

markfang2050

给出行走路径具体方案与方法

wayne

1. LinearRecurrence[{1, 0, 1, 0, 1}, {1, 1, 2, 3, 5}, 2019]

复制代码

答案是$2.073989246436550*10^395$：

1. 207398924643654960478809907852549422038687444642321211412375542327087571909137869607137717979975555362916498315724979701792543811518693033965848114941697909399053885916034215998038242947818365729040242434342060948811460517895997885283031278241333319027320504745796543369117794056604029150800454135371305233854814535169674975512625797533552986787997438319559459528666728171930448577081570255296050

复制代码

markfang2050

wayne 发表于 2019-3-25 00:27
答案是$2.073989246436550*10^395$：

可以给出具体的行走方案吗

markfang2050

python3.6程序
# coding = UTF-8
#题目：一栋楼有N阶楼梯，兔子每次可以跳1、3或5阶，问一共有多少种走法？
#对应1，2，3阶楼梯的方法数#比如n=5，1+1+1+1+1=1+3+1=1+1+3=3+1+1=5=5，共有5种不同的方法
#n=4，1+1+1+1=1+3=3+1=4，共有3种不同的方法
#n=3，1+1+1=3=3，共有2种不同的方法
#n=2，1+1=2，共有1种不同的方法
#n=1，1=1，共有1种不同的方法
#递归法

def climbStairs1(stairs):
    '''
    :param stairs:the  numbers of stair
    :return:
    '''
    if isinstance(stairs,int) and stairs > 0:
        basic_num = {0:1,1:1,2:1,3:2,4:3,5:5}
        if stairs in basic_num.keys():
            return basic_num[stairs]
        else:
            return climbStairs1(stairs-1)  + climbStairs1(stairs-3)+ climbStairs1(stairs-5)
    else:
        print( 'the num of stair is wrong')
        return False

#递推法
def climbStairs2(stairs):
    '''递推实现
    :param stairs:  the amount of stair
    :return:
    '''
   
    if isinstance(stairs,int) and stairs > 0:
         h1=1#对应1，2，3, 4, 5阶楼梯的方法数
         h2=1
         h3=2
         h4=3
         h5=5
         n=5
         basic_num = {1:1,2:1,3:2,4:3,5:5}
         if stairs in basic_num.keys():
            return basic_num[stairs]
         else:
            for i in range(stairs-n):
            
               temp =h1
               h1 = h2
               h2 = h3
               h3 =h4
               h4=h5
               h5 =temp+h2+h4
               
            return h5
    else:
        print ('the num of stair is wrong')
        return False


for j in range(1,20):   
print ('递归法求得爬%d阶楼梯的方法数%d'%(j,climbStairs1(j)))#12阶楼梯
print ('递推法求得爬%d阶楼梯的方法数%d'%(j,climbStairs2(j)))
========
递归法求得爬1阶楼梯的方法数1
递推法求得爬1阶楼梯的方法数1
递归法求得爬2阶楼梯的方法数1
递推法求得爬2阶楼梯的方法数1
递归法求得爬3阶楼梯的方法数2
递推法求得爬3阶楼梯的方法数2
递归法求得爬4阶楼梯的方法数3
递推法求得爬4阶楼梯的方法数3
递归法求得爬5阶楼梯的方法数5
递推法求得爬5阶楼梯的方法数5
递归法求得爬6阶楼梯的方法数8
递推法求得爬6阶楼梯的方法数8
递归法求得爬7阶楼梯的方法数12
递推法求得爬7阶楼梯的方法数12
递归法求得爬8阶楼梯的方法数19
递推法求得爬8阶楼梯的方法数19
递归法求得爬9阶楼梯的方法数30
递推法求得爬9阶楼梯的方法数30
递归法求得爬10阶楼梯的方法数47
递推法求得爬10阶楼梯的方法数47
递归法求得爬11阶楼梯的方法数74
递推法求得爬11阶楼梯的方法数74
递归法求得爬12阶楼梯的方法数116
递推法求得爬12阶楼梯的方法数116
递归法求得爬13阶楼梯的方法数182
递推法求得爬13阶楼梯的方法数182
递归法求得爬14阶楼梯的方法数286
递推法求得爬14阶楼梯的方法数286
递归法求得爬15阶楼梯的方法数449
递推法求得爬15阶楼梯的方法数449
递归法求得爬16阶楼梯的方法数705
递推法求得爬16阶楼梯的方法数705
递归法求得爬17阶楼梯的方法数1107
递推法求得爬17阶楼梯的方法数1107
递归法求得爬18阶楼梯的方法数1738
递推法求得爬18阶楼梯的方法数1738
递归法求得爬19阶楼梯的方法数2729
递推法求得爬19阶楼梯的方法数2729