數(shù)據(jù)結(jié)構(gòu)中n個(gè)數(shù)據(jù)依次入棧，出棧順序有多少種？誰(shuí)能幫忙證明下？n個(gè)數(shù)據(jù)依次入棧，出棧順序種數(shù)的遞推公式如下：F(n)=∑(F(n-1-k)*Fk)其中k從0到n-1已知F0=1，F(xiàn)1=F0*F0=1F

數(shù)據(jù)結(jié)構(gòu)中n個(gè)數(shù)據(jù)依次入棧，出棧順序有多少種？誰(shuí)能幫忙證明下？

n個(gè)數(shù)據(jù)依次入棧，出棧順序種數(shù)的遞推公式如下：F(n)=∑(F(n-1-k)*Fk)其中k從0到n-1已知F0=1，F(xiàn)1=F0*F0=1F2=F1*F0 F0*F1=2F3=F2*F0 F1*F1 F0*F2=5……證明的話(huà)，對(duì)于n個(gè)數(shù)據(jù)，我只看第一個(gè)數(shù)據(jù)的出入棧順序：第一個(gè)數(shù)據(jù)入棧到出棧之間可以包含0，1，2…n-1個(gè)數(shù)據(jù)的出入棧，相應(yīng)的，第一個(gè)數(shù)據(jù)出棧之后，還有n-1，n-2…2，1，0個(gè)數(shù)據(jù)需要出入棧根據(jù)組合數(shù)學(xué)里面的乘法原理，需要把第一個(gè)數(shù)據(jù)出棧前后的種數(shù)相乘根據(jù)加法原理，需要把第一個(gè)數(shù)據(jù)出入棧的n種方式全加起來(lái)于是就得到了那個(gè)遞推公式，不過(guò)，要找出一個(gè)直接計(jì)算Fn的公式似乎不太好辦。