卡塔兰数计算机模拟

hbghlyj

1. catalancount[n_, numdo_] := Module[{},
2.    (* we have an n x n grid, have n right moves, n up moves *)
3.    (* we will do this numdo times,
4.    record how many stay on main diag or below *)
5.    (* Right is +1, Up is -1, success is all running sums non-
6.    negative *)
7.    steplist = {};
8.    For[j = 1, j <= n, j++,  steplist  = AppendTo[steplist, 1]];
9.    For[j = 1, j <= n, j++,  steplist  = AppendTo[steplist, -1]];
10.    success = 0;
11.    For[i = 1, i <= numdo, i++,
12.     {
13.      orderedstep = RandomSample[steplist, 2 n]; (*
14.      this randomly permutes the 2n steps *)
15.      (* initialize works to 1,
16.      if ever have a negative running sum make works 0,
17.      increment success if end with works = 1 *)
18.      works = 1;
19.      runningsum = 0;
20.      For[j = 1, j <= 2 n, j ++,
21.       {
22.        runningsum = runningsum + orderedstep[[j]];
23.        If[ runningsum < 0,
24.         {
25.          works = 0;
26.          j = 2 n + 5;
27.          }];
28.        }]; (* end of j loop *)
29.      If[works > 0, success = success + 1];
30.      }]; (* end of i loop *)
31.    Print["Number of successes is ",
32.     1.0 (success / numdo) Binomial[2 n, n]];
33.    ];

复制代码

hbghlyj

例如
For[q = 1, q <= 10, q++, catalancount[q, 1000000]]
输出为
Number of successes is 0.999498
Number of successes is 2.00277
Number of successes is 5.00576
Number of successes is 13.9945
Number of successes is 41.9797
Number of successes is 131.017
Number of successes is 427.809
Number of successes is 1432.83
Number of successes is 4827.29
Number of successes is 16841.8
用内置的函数计算前10个卡塔兰数:
CatalanNumber[Range[10]]
输出
{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796}