カタラン数について
カタラン数C(n)に関して
一般にはn×nの格子路に対して
(0,0)から(n,n)までを(0,0)､(n,n)を結ぶ対角線より上方へははみ出さない部分で
行ける経路の数を与えるものと紹介される例をよく見る。
そこで正方形の格子路をあらため、n×mでの長方形の格子路を考え
x軸方向へはn,y軸方向へはmとし
(0,0),(n,m)を結ぶ対角線を引き、この直線より上方へは立ち入らずに
(0,0)から格子点を通過しながら(n,m)地点に辿り着けるカタラン路が何通りあるかを
考えることにする。
この求めたい総数をC(n,m)と記して式を構成しようと頑張ってみたのだが、意外とnによって
構造が異なってしまうのでまだ一つの式で表すものに辿り着けていません。
どなたか、関心を寄せられましたら是非
C(3,m)とC(4,m)
に対して、どんな式（もしくはプログラムで算出できるコード等）
を発見されるのかお示し願えれば有難いです。
私の解釈が間違っていなければ
C(3,m)はm=0～100に対して
1,1,2,5,5,7,12,12,15,22,
22,26,35,35,40,51,51,57,70,70,
77,92,92,100,117,117,126,145,145,155,
176,176,187,210,210,222,247,247,260,287,
287,301,330,330,345,376,376,392,425,425,
442,477,477,495,532,532,551,590,590,610,
651,651,672,715,715,737,782,782,805,852,
852,876,925,925,950,1001,1001,1027,1080,1080,
1107,1162,1162,1190,1247,1247,1276,1335,1335,1365,
1426,1426,1457,1520,1520,1552,1617,1617,1650,1717,
1717
C(4,m)はm=0～100に対して
1,1,3,5,14,14,23,30,55,55,
76,91,140,140,178,204,285,285,345,385,
506,506,593,650,819,819,938,1015,1240,1240,
1396,1496,1785,1785,1983,2109,2470,2470,2715,2870,
3311,3311,3608,3795,4324,4324,4678,4900,5525,5525,
5941,6201,6930,6930,7413,7714,8555,8555,9110,9455,
10416,10416,11048,11440,12529,12529,13243,13685,14910,14910,
15711,16206,17575,17575,18468,19019,20540,20540,21530,22140,
23821,23821,24913,25585,27434,27434,28633,29370,31395,31395,
32706,33511,35720,35720,37148,38024,40425,40425,41975,42925,
45526
のようになり、この値から式を作ると
C(3,m)=[(m+3)/3]^2+[(m+1)/3][(m+4)/3]/2
C(4,m)=[(m+4)/4](4[(m+4)/4]^2-1)/3+[(m+1)/4][(m+5)/4]^2/2+[(m+2)/4][(m+6)/4](5[(m+2)/4]+1)/6
という式で表されそうです。
投稿ありがとうございます。
自分ではこの求めるべき経路数を一つずつ作図しながら求めていたものですから
mが100までのデータは考えられもしませんでした。
nが3の時の数の並びの変化の状態から
k=m\3 (mを3で割ったときの商をk)
L=3*k+1
として置けば、通常の3×mの格子路での全経路数S=(3+m)!/(3!*m!)に対する比率が
m%3の値に依存していることが起こりそうだと思われた。
つまり
m%3==0 ==>C(3,m)=S/L
m%3==1 ==>C(3,m)=S/(L+3)
m%3==2 ==>C(3,m)=S/(L+4)
これに従いプログラムを組んで並べて行き、m=20 位までぐらいを確認していました。
（なにせ手作業で図を描いてやっと経路数を見つけていたものですから）
これで上手く行きそうだと思ってしまったので
n=4も
k=m\4 (mを4で割ったときの商をk)
L=4*k+1
として置けば、通常の4×mの格子路での全経路数S=(4+m)!/(4!*m!)に対する比率が
m%4の値に依存していることが起こりそうだと思われた。
つまり
m%4==0 ==>C(4,m)=S/L
m%4==1 ==>C(4,m)=S/(L+4)
m%4==2 ==>C(4,m)=S/(L+5)
m%4==3 ==>C(4,m)=S/(L+6)
ところがどっこい実際に起こる経路数が
m%4==2 の場合分数の値を返してきて反映してくれない。
何とかSの値は利用したかったので、実際に起こる経路数と一致させるための調整が
m%4==2 ==>C(4,m)=(S-k*(k+1)*(4*k+5)/6)/(L+4)
へ辿り着きました。
Sから除くパターンの部分がなぜかA016061に繋がっているのが不思議でした。
これを元にプログラムを組んでやはりm=20辺り位までしか確認していませんでした。
それでらすかるさんの値と比較しm=98==2(mod 4)
でも一致できていたので安心しました。
しかしこれを一つの式で表せられるなんて思ってもいませんでした。
感じとしてはnが素数である時は、例の規則で行けそうですが、nが合成数になると
途端に厄介になりそうです。
今n=6に挑戦していますが、図を描いて正解数を求めるしか手がないので
らすかるさん、前もってその配列数をm=100までを教えて貰えませんか？
C(6,m)ならm=0～100に対して
1,1,4,12,23,42,132,132,227,377,
525,728,1428,1428,2010,2803,3504,4389,7084,7084,
9097,11654,13793,16380,23751,23751,28931,35246,40356,46376,
62832,62832,73950,87143,97584,109668,141778,141778,162883,187453,
206591,228459,285384,285384,322046,364124,396510,433160,527085,527085,
586638,654240,705789,763686,910252,910252,1002037,1105317,1183487,1270752,
1489488,1489488,1625096,1776599,1890570,2017169,2331924,2331924,2525439,2740354,
2901207,3079140,3518515,3518515,3786757,4083170,4304066,4547556,5145336,5145336,
5508104,5907251,6203610,6529292,7324878,7324878,7805193,8331713,8721393,9148503,
10187344,10187344,10811692,11493880,11997356,12547920,13881945,13881945,14680520,15550580,
16191123
のようになると思います。
（追記）
https://manabitimes.jp/math/962
↑ここの「書き込み方式」に従ってプログラミングすると簡単ですよ。
対角線を越える点をカウントしないようにするだけですから、
・(幅+1)×(長さ以上)の配列を作る(幅は3,4,6など、100まで出すなら「長さ以上」は101以上)
・配列全体を0にして(0,0)要素だけ1にする
・y=0～(長さ)まで以下の処理を行う
・x=0～(幅)まで以下の処理を行う（ただしy=0のときのみx=1から）
・(長さ)×x＞(幅)×yのときxのループを抜ける（対角線を越える格子点）
・配列の(x-1,y)要素と(x,y-1)要素の和を(x,y)要素の値とする（ただしx-1やy-1が負のとき0）
これで最終的に(幅,長さ)要素に格納された値が答えです。
ヒントをもらったのでPARIのソフトで挑戦してみました。
配列がmatrixの道具しかなく、成分は[1,1]から取ってあるので
微妙に取り方をずらしながら組んでみました。
F(n,m)={M=matrix(n+1,m+1,i,j,if(j==1,1,i==1&&j>1,0))};\
for(x=2,n+1,for(y=2,m+1,if(m*(x-1)<n*(y-1),next,\
M[x,y]=M[x-1,y]+M[x,y-1])));M
これより
gp > F(6,10)
%813 =
[1 0 0 0 0 0 0 0 0 0 0]
[1 1 0 0 0 0 0 0 0 0 0]
[1 2 2 2 0 0 0 0 0 0 0]
[1 3 5 7 7 7 0 0 0 0 0]
[1 4 9 16 23 30 30 0 0 0 0]
[1 5 14 30 53 83 113 113 113 0 0]
[1 6 20 50 103 186 299 412 525 525 525]
gp > F(6,18)
%818 =
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 2 3 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0]
[1 3 6 10 14 18 22 22 22 22 0 0 0 0 0 0 0 0 0]
[1 4 10 20 34 52 74 96 118 140 140 140 140 0 0 0 0 0 0]
[1 5 15 35 69 121 195 291 409 549 689 829 969 969 969 969 0 0 0]
[1 6 21 56 125 246 441 732 1141 1690 2379 3208 4177 5146 6115 7084 7084 7084 7084]
あの手作業が夢のようです。
またnが素数の場合は予想が当たるか確認してみた。
n=7でやってみると
F7(m)={k=m\7;L=7*k+1;S=(7+m)!/(m!*7!);}\
if(m%7==0,print(m";"S/L),m%7==1,print(m";"S/(L+7)),\
m%7==2,print(m";"S/(L+8)),m%7==3,print(m";"S/(L+9)),\
m%7==4,print(m";"S/(L+10)),m%7==5,print(m";"S/(L+11)),\
m%7==6,print(m";"S/(L+12)))
と組んで走らせると
gp > for(m=1,50,F7(m))
1;1
2;4
3;12
4;30
5;66
6;132
7;429
8;429
9;715
10;1144
11;1768
12;2652
13;3876
14;7752
15;7752
16;10659
17;14421
18;19228
19;25300
20;32890
21;53820
22;53820
23;67860
24;84825
25;105183
26;129456
27;158224
28;231880
29;231880
30;278256
31;332112
32;394383
33;466089
34;548340
35;749398
36;749398
37;870922
38;1008436
39;1163580
40;1338117
41;1533939
42;1997688
43;1997688
44;2270100
45;2572780
46;2908360
47;3279640
48;3689595
49;4638348
50;4638348
一方
G(n,m)={M=matrix(n+1,m+1,i,j,if(j==1,1,i==1&&j>1,0))};\
for(x=2,n+1,for(y=2,m+1,if(m*(x-1)<n*(y-1),next,\
M[x,y]=M[x-1,y]+M[x,y-1])));M[n+1,m+1]
から
gp > for(m=1,50,print(m";"G(7,m)))
1;1
2;4
3;12
4;30
5;66
6;132
7;429
8;429
9;715
10;1144
11;1768
12;2652
13;3876
14;7752
15;7752
16;10659
17;14421
18;19228
19;25300
20;32890
21;53820
22;53820
23;67860
24;84825
25;105183
26;129456
27;158224
28;231880
29;231880
30;278256
31;332112
32;394383
33;466089
34;548340
35;749398
36;749398
37;870922
38;1008436
39;1163580
40;1338117
41;1533939
42;1997688
43;1997688
44;2270100
45;2572780
46;2908360
47;3279640
48;3689595
49;4638348
50;4638348
予想大当たり！！！
しかしn=6の場合はS=(6+m)!/(6!*m!)
の数値から導くのは困難でした。（未だに解決できずです。）
