正n角形の3頂点を結んで作れる合同でない三角形の数

数Aの場合の数の問題で，
「正7角形の頂点を3つ結んで作れる互いに合同でない三角形は何種類ですか」
みたいなのがあります．

これが正 $n$ 角形だとどうなるか調べてみます．

参考
大阪府立高津高等学校の久世さんとバセダさんが，2010年に同じ研究をしていました．
正ｎ角形の頂点を結んでできる三角形の合同類の個数は？
ポスター並びに口頭発表要旨
上記研究では互いに合同でない三角形の個数を分割数で表すところまでは同じですが，そこから具体的に数えていく方法が本記事とは違うみたいです．

本記事の結論は以下の二つです．
定理１
正 $n$ 角形の3頂点を結んでできる互いに合同でない三角形の数を $\Delta(n)$ とする．
その母関数は以下で表される．
$\sum_{n\geq 0}\Delta(n)q^n = \frac{q^3}{(1-q)(1-q^2)(1-q^3)}$

定理２
正 $n$ 角形の $3$ 頂点を結んでできる互いに合同でない三角形の数を $\Delta(n)$ とする．
自然数 $n$ が非負整数 $k$ を用いて
$n-3=6k$ と表せるとき， $\Delta(n)=3k^2+3k+1$ ，
$n-3=6k+i\ (i=1,\ldots,5)$ と表せるとき， $\Delta(n)=(k+1)(3k+i)$ ．

定理１の証明
正 $n$ 角形 $A_1A_2\cdots A_n$ の $3$ 頂点 $\{A_i,A_j,A_k\}\ (i\lt j\lt k)$ を結んでできる三角形全体の集合を考え，合同関係による商を考える．
各同値類には以下の二条件を満たす三角形が唯一存在するため，それを代表元とする．

$A_i = A_1$
$A_iA_j \leq A_jA_k\leq A_kA_i$

各代表元は $A_1A_jA_k$ という形をしていて，
自然数 $x,y,z$ を $x\triangleq j-1,\ y\triangleq k-j,\ z\triangleq n-k+1$
と定めれば， $x+y+z=n,\ 1\leq x\leq y\leq z$ である．
また逆にそのような自然数 $x,y,z\in\mathbb{N}$ の全体は，完全代表系と一対一対応している．

よって正 $n$ 角形の3頂点を結んでできる互いに合同でない三角形の数 $\Delta(n)$ は，
自然数 $n$ の長さ3の分割 $\lambda=(\lambda_1,\lambda_2,\lambda_3)\vdash n$ の数に等しい．
ヤング図形の転置を考えることで，それはさらに
自然数 $n-3$ の分割で，各要素の大きさが $3$ 以下であるものの数
$\#\{\lambda=(\lambda_1,\ldots,\lambda_r)\vdash (n-3)\mid \lambda_i\leq 3\ (i=1,\ldots,r)\}$
にひとしい．
よって $\Delta(n)$ の母関数は $\sum_{n-3\geq 0}\Delta(n)q^{n-3}=\frac{1}{(1-q)(1-q^2)(1-q^3)}$ と表せる．（証明終）

補足
長さ $3$ の分割の母関数は，ヤング図形の転置を考えることなく母関数
$\sum_{1\leq x\leq y\leq z}q^{x+y+z}$ の直接計算によっても導くことができる．
その際は，MacMahonのΩ解析と呼ばれるテクニックが用いられる．

定理２の証明
自然数 $n-3$ の分割で，各要素の大きさが $3$ 以下であるものの数
$\#\{\lambda=(\lambda_1,\ldots,\lambda_r)\vdash (n-3)\mid \lambda_i\leq 3\ (i=1,\ldots,r)\}$
をがんばって求める．
求め方は，以前書いた以下の記事で使った素朴な方法と殆ど同じである．
iwalion.hatenablog.com
まず，分割に $3$ が何個含まれるかで場合分けし，さらに $2$ がいくつ含まれるかを考えてゆく．
例えば，非負整数 $k$ を使って $n-3=6k$ と表せるとき，
$3$ を $2i$ 回使うなら，残り $6k-6i$ を $1と2$ の和で表す方法は $3(k-i)+1$ 通り，
$3$ を $2i+1$ 回使うなら，残り $6k-6i-3$ を $1と2$ の和で表す方法は $3(k-i)-1$ 通り，
以上から全部で
$\sum_{i=0}^k\{3(k-i)+1\}+\sum_{i=0}^{k-1}\{3(k-i)-1\}=3k^2+3k+1$ 通り．