令和5年6月のGAIさんのコメントに対する返信：
>ＧＡＩ さんからのコメントです。（令和５年６月６日付け）
> カタラン数C(n)に関して、一般には、n×n の格子路に対して、(0,0)から(n,n)までを(0,0)､(n,n)
>を結ぶ対角線より上方へははみ出さない部分で行ける経路の数を与えるものと紹介される例
>をよく見る。
> そこで、正方形の格子路を改め、n×mでの長方形の格子路を考え、x 軸方向へは、ｎ、y
>軸方向へは、ｍとし、(0,0)、(n,m)を結ぶ対角線を引き、この直線より上方へは立ち入らずに
>(0,0)から格子点を通過しながら(n,m)地点に辿り着けるカタラン路が何通りあるかを考えるこ
>とにする。
> この求めたい総数を、C(n,m) と記して、式を構成しようと頑張ってみたのだが、意外とｎに
>よって構造が異なってしまうので、まだ、一つの式で表すものに辿り着けていません。
以下のページに、C(n,m) の値を計算する式の導出法が詳しく書かれています．
https://www.jstor.org/stable/41139633?seq=1
「 Grossman's formula」と呼ばれているようです。
要約すると、C(n,m)は次式で計算できるとのことです。
n,mの最大公約数をd，n=d*n', m=d*m' とおくと、
C(n,m)
=C(d*n',d*m')
=[x^d]exp(∑[j=1～d]binomial(j*(n'+m'),j*n')*(x^j)/(j*(n'+m'))).
上記ページの論文の結果を使い，C(6,m)を計算しました。
C(6,m)=C(m)とおいて，m=0～100に対するC(m)の値を maxima で計算したものが以下です。
(%i2) C(m):=if mod(m,6)=0 then binomial(m+6,6)/(m+1) else
if mod(m,6)=1 or mod(m,6)=5 then binomial(m+6,6)/(m+6) else
if mod(m,6)=2 then ((m+2)*(m+4)*(8*m^3+77*m^2+214*m+160))/5760 else
if mod(m,6)=3 then ((m+3)*(27*m^4+364*m^3+1698*m^2+3186*m+2025))/19440 else
((m+2)*(m+4)*(8*m^3+77*m^2+214*m+160))/5760$
makelist(C(m),m,0,100);
(%o2) [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]
紹介して頂いた貴重な論文を拝見させて頂きました。
目が回る様な論理の展開で一つの式で表現するためには
大変な考察が必要なことが実感できました。
一般にO(0,0),P(n,m)の2点を結ぶ直線の下方(直線上を含む)の領域
だけを通過する格子路でOからPまでの最短路の総数G(n,m)を求める
プログラムをらすかるさんのアイデアをお借りして以前作成していた
のを思い出しました。
以下がそのプログラム(PARI/GPでのコード)と結果になります。
なお\記号は複数行に渡る記述のための繋ぎのためのものです。
gp > 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(n=2,9,print1(n"=>");for(m=1,30,print1(G(n,m)","));print)
2=>1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,
3=>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,
4=>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,
5=>1,3,7,14,42,42,66,99,143,273,273,364,476,612,969,969,1197,1463,1771,2530,
2530,2990,3510,4095,5481,5481,6293,7192,8184,10472,
6=>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,
7=>1,4,12,30,66,132,429,429,715,1144,1768,2652,3876,7752,7752,10659,14421,
19228,25300,32890,53820,53820,67860,84825,105183,129456,158224,231880,231880,
278256,
8=>1,5,15,55,99,227,429,1430,1430,2529,3978,7229,9690,14985,21318,43263,43263,
61600,82225,121637,148005,199238,254475,420732,420732,543806,672452,900239,
1043460,1307742,
9=>1,5,22,55,143,377,715,1430,4862,4862,8398,15090,22610,35530,58040,81719,
120175,246675,246675,345345,500449,650325,876525,1220135,1542684,2017356,
3362260,3362260,4289780,5630306,
6=>の場合がat氏の出力と一致すると思います。
