数学の命題示しました

主に組合せ論について，読んだ本で出てきたことや，考えたことを書きます．

二乗和の公式の導出

母関数 高校数学

みなさん御存知の通り，
\displaystyle\sum_{k=1}^nk^2=\frac{1}{6}n(n+1)(2n+1)
です．

この式の導出は「 (k+1)^3-k^3=3k^2+3k+1」を k=1から k=nまで足すみたいなやつが有名です．（ググればたぶん一番上に出てきます．）
だけど，二乗和を求めると言われたときに「 (k+1)^3-k^3=3k^2+3k+1」を使う発想に至るのは飛躍が大きい気がして個人的にあまり好きじゃないです．

この記事では，母関数を使った導出方法を紹介します．
数列「 1,2^2,3^2,\ldots,n^2」の母関数は
「 1+2^2q+3^2q^2+\cdots+n^2q^{n-1}」です．
この母関数を計算して q\to 1の極限を取れば，二乗和の公式が得られます．
母関数の世界では，数列「 (a_k)_{k=1}^n」を「 (ka_k)_{k=1}^n」に変えるのは
母関数を qで微分して qをかける操作に対応します．今回は二乗和なのでそれを二回やります．

命題 (二乗和の公式)

\displaystyle\sum_{k=1}^nk^2=\frac{1}{6}n(n+1)(2n+1)

証明

まず，
\displaystyle \sum_{k=0}^nq^k= \frac{1-q^{n+1}}{1-q}
です．
両辺を qで微分します．
\displaystyle \sum_{k=0}^nkq^{k-1}= \frac{nq^{n+1}-(n+1)q^n+1}{(1-q)^2}
両辺に qをかけます．
\displaystyle \sum_{k=0}^nkq^{k}= \frac{nq^{n+2}-(n+1)q^{n+1}+q}{(1-q)^2}

両辺をまた qで微分します．
\displaystyle \sum_{k=0}^n k^2q^{k-1} = \frac{-n^2q^{n+2}+(2n^2+2n-1)q^{n+1}-(n+1)^2q^n+q+1}{(1-q)^3}

極限 q\to 1をとります．左辺は \sum_{k=0}^nk^2になり，右辺はロピタルの定理を使います．（分母と分子を別々に三回微分したやつに q=1を入れます．）
すると，
\displaystyle\sum_{k=1}^nk^2=\frac{1}{6}n(n+1)(2n+1)
を得ます．（証明終わり）

第一種，第二種スターリング数

スターリング数 置換

第一種および第二種スターリング数と呼ばれる数列を定義して，その組合せ論的な意味付けを紹介します．

参考とした本：
Martin Aigner, A course in Enumeration, GTM 238, 2007.

変数 xの昇冪 (x)^{(n)}と降冪 (x)_nを

(x)^{(n)}\triangleq x(x+1)\cdots (x+n-1)=\prod_{i=0}^{n-1}(x+i),
(x)_n\triangleq x(x-1)\cdots(x-n+1)=\prod_{i=0}^{n-1}(x-i),\quad n=1,2,3,\ldots

(x)^{(0)}=(x)_0\triangleq 1
と定義します．
多項式の集合 \{1,x,x^2,x^3,\ldots\}と \{1,(x)_1,(x)_2,(x)_3,\ldots\}はどちらも \mathbb{R}[x]の基底だから，ある係数 s(n,k),t(n,k)\in\mathbb{R}を使って

\displaystyle (x)_n = \sum_{k=0}^n (-1)^{n-k}s(n,k) x^k,
\displaystyle x^n = \sum_{k=0}^n t(n,k) (x)_k,\quad n=0,1,2,\ldots

と書けます．
この展開の係数として出てくる s(n,k)と t(n,k)はそれぞれ第一種，第二種スターリング数と呼ばれていて，組合せ論的な解釈が与えられています．
以下に見るように，第一種スターリング数は置換のサイクル分解と関係し，第二種スターリング数は有限集合の直和分割に関連します．

第一種スターリング数

\mathfrak{S}_nで n文字 \{1,\ldots,n\}の置換の集合を表します．
任意の置換は互いに交差しない (a_1 a_2 \cdots a_r)の形の置換の積として，積の順番を除いて一意的に表すことができます．その積表示のことを置換のサイクル分解といいます．
また，置換\sigma\in\mathfrak{S}_nのサイクル分解に現れる因子の個数を \sigmaのサイクル数といいます．
以下の図はサイクル分解を説明する例です．

f:id:iwalion:20200224170713p:plain
サイクル分解の説明

定理１ \mathfrak{S}_nに含まれるサイクル数 kの置換の個数は，第一種スターリング数 s(n,k)である．

証明
\mathfrak{S}_nに含まれる，サイクル数 kの置換の個数を S(n,k)と書きます．
すると
\displaystyle (x)_n = \sum_{k=0}^n (-1)^{n-k}S(n,k) x^k,\quad n=0,1,2,\ldots
が成り立つことを示します．

証明には以下の①，②を使います．

① S(n,k)は以下の漸化式を満たします．
S(n,k)=S(n-1,k-1)+(n-1)S(n-1,k)\quad n,k\geq 0.
これは， \mathfrak{S}_nに含まれるサイクル数 kの置換を，例えば 1を動かすものと動かさないものに分けることで示せます．
説明：文字 1を動かさない置換の数は， 1を除いた n-1文字の置換で k-1個のサイクルを持つものの数に等しいので S(n-1,k-1)個．
文字 1を動かす置換の数は， 1を除いた n-1文字の置換のうちサイクル数 k-1のものを考え，どこかのサイクルに 1を入れる方法の数なので (n-1)S(n-1,k)通りです．


②昇冪について，次の式が成り立ちます．
(x)^{(n)}=(x+n-1)\cdot (x)^{(n-1)}=x\cdot(x)^{(n-1)}+(n-1)\cdot(x)^{(n-1)}


我々は目的の式
\displaystyle (x)_n = \sum_{k=0}^n (-1)^{n-k}S(n,k) x^k
を直接示すのではなく，それと同等な
\displaystyle (x)^{(n)} = \sum_{k=0}^n S(n,k) x^k
を示します．（二つが同等であることは， (-x)^{(n)}=(-1)^n(x)_nからわかります．）
証明は nに関する帰納法でします． n-1のとき成立と仮定します．②から
(x)^{(n)}=x\cdot(x)^{(n-1)}+(n-1)\cdot(x)^{(n-1)}
帰納法の仮定から
\displaystyle (x)^{(n)}=x\sum_{k=0}^{n-1}S(n-1,k)x^k+(n-1)\sum_{k=0}^{n-1}S(n-1,k)x^{k}
\displaystyle =\sum_{k=0}^{n-1}S(n-1,k)x^{k+1}+\sum_{k=0}^{n-1}(n-1)S(n-1,k)x^{k}
\displaystyle =\sum_{k=1}^{n}S(n-1,k-1)x^{k}+\sum_{k=0}^{n-1}(n-1)S(n-1,k)x^{k}
\displaystyle =\sum_{k=0}^{n}\left\{S(n-1,k-1)+(n-1)S(n-1,k)\right\}x^k

但し，最後の行は S(n-1,-1)= 0,\ S(n-1,n)=0を用いました．
①から
\displaystyle (x)^{(n)}=\sum_{k=0}^nS(n,k)x^k．[証明終わり]


第二種スターリング数

集合 Aの冪集合の部分集合 \mathcal{A}が，
１， \mathcal{A}に含まれるどの二つの集合も共通部分を持たない．
２， \bigsqcup_{S\in\mathcal{A}}=A
を満たすとき， \mathcal{A}は Aの分割であるといいます．
例：\displaystyle\left\{\{1,3\},\{2\},\{4,5,6,7\}\right\}は，集合 \{1,2,3,4,5,6,7\}の分割のひとつです．

定理２ 集合 \{1,\ldots,n\}の分割で，要素数が kのものの個数は，第二種スターリング数 t(n,k)である．

証明
集合 \{1,\ldots,n\}の分割で要素数が kのものの個数を T(n,k)と書くことにします．
すると
\displaystyle x^n = \sum_{k=0}^n T(n,k) (x)_k,\quad n=0,1,2,\ldots
が成立することを示します．

そのためにまず，非負整数 n,r=0,1,2,\ldotsについて
\displaystyle r^n = \sum_{k=0}^r T(r,k) (r)_kが成り立つことを示します．
これが示せれば，我々が示したいところの多項式の等式
\displaystyle x^n = \sum_{k=0}^n T(n,k) (x)_k,\quad n=0,1,2,\ldots
も言えます．
説明：左辺と右辺は変数 xの n次多項式であり，それらは無数の点 x=0,1,2,\ldotsで等しいから，多項式として等しいことがわかります．

集合 Aから集合 Bへの写像の集合を {\rm Map}(A,B)，全射の集合を {\rm Surj}(A,B)とかきます．
自然数 nに対し [n]\triangleq\{1,\ldots,n\}と書きます．

まず，
\left|{\rm Map}([n],[r])\right|=r^n,
\left|{\rm Surj}([n],[r])\right|=r!T(n,r)
が成り立ちます．
説明：全射の個数は，集合 \{1,\ldots,n\}を r個の部分集合に分けて，その r個を一列に並べる方法の数なので， r!T(n,r)個です．

次に，集合 {\rm Map}([n],[r])と集合 \displaystyle \bigsqcup_{A\subseteq [r]}{\rm Surj}([n],A)の間には全単射が存在します．
さらに後者の集合は
\displaystyle \bigsqcup_{A\subseteq [r]}{\rm Surj}([n],A)=\bigsqcup_{k=0}^r\bigsqcup_{|A|=k,\ A\subseteq[r]}{\rm Surj}([n],A)
と書けます．
ここから，上の濃度の議論を使えば，
\displaystyle r^n=\sum_{k=0}^r\binom{r}{k}k!T(n,k)=\sum_{k=0}^r\frac{r!k!}{k!(r-k)!}T(n,k)=\sum_{k=0}^rT(n,k)\cdot(r)_k
が成り立ちます．
ここから更に，和を rまでではなく nまでにした
\displaystyle r^n=\sum_{k=0}^nT(n,k)\cdot(r)_k
が成り立ちます．
説明： n\lt rのときは， T(n,r)=0なので成立．また， n\geq k\gt rのときは，和の中の降冪が (r)_k=0となるの成立．
[証明終わり]


今後？とか

第一種スターリング数と第二種スターリング数は似た定義の概念なのに，本で紹介されていた証明方法は二つでけっこう違うものだったのが面白いなって思ってこの記事を書きました．
この記事の続編があるなら，以下のトピックから選んで書こうと思います

  • 第一種，第二種スターリング数には指数型母関数が知られています．
  • q-スターリング数というものがあるらしいです．
  • スターリング数は，格子路による意味付けを持つらしいです．
  • 定義からも分かるように，第一種スターリング数（に (-1)^{n-k}をつけたもの）を並べた行列と，第二種スターリング数を並べた行列は互いの逆行列です．このことを使うと，様々な恒等式が言えます．(所謂，数列の反転公式というやつ)
  • スターリング数をモーメントに持つような直交多項式が研究されていないか探してみます．

対称関数についての読書ノートを書こうと思います．

現実逃避にStanleyのEnumerative Combinatorics (vol 1)の第7章を読み進める読書ノートを書こうと思います
まだ何も書いていないですが，モチベを高めるためにとりあいずネットに上げておきます．
著作権のことを考えて，論理展開は本を追いますが文章や証明はiwalionが書きます．

texで書くほうがはてなブログに直書きするより書きやすそうなので，pdfにします．
pdfにも書きましたが，以下のような内容にする予定です．

  • 対称関数に関する基本的な事項
  • RSKアルゴリズム
  • Schur関数の二つの定義とその同値性
  • Jacobi-Trudi公式
  • MacMahon公式


drive.google.com

よろしくおねがいします．

cosのn倍角公式〜チェビシェフ多項式の話１

母関数 解析

概要
\cosの n倍角公式 (第一種チェビシェフ多項式)を求める方法を四通り紹介します．

\cos n\theta (n\in\mathbb{Z}_{\geq 0})は以下のように\cos\thetaの多項式として表せます．
\cos 0 = 1,
\cos \theta = \cos\theta,
\cos 2\theta = 2\cos^2\theta-1,
\cos 3\theta = 4\cos^3\theta-3\cos\theta,
\vdots
その具体的な式形を\cosの n倍角公式と呼ぶと思いますが，文脈によっては「第一種チェビシェフ多項式」と呼ぶこともあります．

詳しい解説はWikipediaを見てください．
チェビシェフ多項式 - Wikipedia


この記事では，一般の(n\in\mathbb{Z}_{\geq 0})について\cos n\thetaを\cos\thetaの多項式として表す具体的な式を，趣の異なる四通りの方法で求めてみようと思います．

以下では， \cos n\thetaを\cos\thetaで表す多項式を T_n(\cos\theta)と書くことにします．
つまり，\cos n\theta=T_n(\cos\theta)であり，
T_0(x) = 1,
T_1(x) = x,
T_2(x) = 2x^2-1,
T_3(x) = 4x^3-3x,
\vdots
です．我々が知りたいのは T_n(x)です．

記号の約束

以下では，\lfloor x\rfloorはxを超えない最大の整数を表し， \binom{n}{r}は二項係数 {}_nC_{r}を表すとします．

方法１：ド・モアブルの定理を使う

ド・モアブルの定理
(\cos\theta+i\sin\theta)^n=\cos n\theta+i\sin n\theta
を使います．

命題
多項式 T_n(x)は以下で表される．
T_n(x)=\displaystyle\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}x^{n-2k}(x^2-1)^k．
証明
ド・モアブルの定理
\cos n\theta+i\sin n\theta= (\cos\theta+i\sin\theta)^n
の右辺を展開して実部と虚部に分ける．

(\cos\theta+i\sin\theta)^n=\displaystyle\sum_{k=0}^n\binom{n}{k}\cos^{n-k}\theta(i\sin\theta)^{k}
=\displaystyle\sum_{0\leq k\leq n,\\k{\rm は偶数}}\binom{n}{k}(-1)^{\frac{k}{2}}\cos^{n-k}\theta\sin^k\theta+i\sum_{0\leq k\leq n,\\k{\rm は奇数}}\binom{n}{k}(-1)^{\frac{k-1}{2}}\cos^{n-k}\theta\sin^k\theta

実部を取り出すと，
\cos n\theta=\displaystyle\sum_{0\leq k\leq n,\\k{\rm は偶数}}\binom{n}{k}(-1)^{\frac{k}{2}}\cos^{n-k}\theta\sin^k\theta


和の変数を kから \ell=\frac{k}{2}に変えて，\sin^2\theta=1-\cos^2\thetaを用いると
\cos n\theta=\displaystyle\sum_{0\leq \ell\leq \lfloor\frac{n}{2}\rfloor}\binom{n}{2\ell}(-1)^{\ell}\cos^{n-2\ell}\theta\sin^{2\ell}\theta
=\displaystyle\sum_{0\leq \ell\leq \lfloor\frac{n}{2}\rfloor}\binom{n}{2\ell}(-1)^{\ell}\cos^{n-2\ell}\theta(1-\cos^2\theta)^\ell
=\displaystyle\sum_{0\leq \ell\leq \lfloor\frac{n}{2}\rfloor}\binom{n}{2\ell}\cos^{n-2\ell}\theta(\cos^2\theta-1)^\ell
[証明終わり]

ド・モアブルの定理を使う証明方法は以下のサイトを参考に書きました．
チェビシェフの多項式（cosのn倍角の公式） | 数学の偏差値を上げて合格を目指す

方法２：漸化式を作って解く

T_n(x)が満たすべき漸化式を立てて解きます．

命題 ( T_n(x)が満たす漸化式．)
T_n(x)は以下の漸化式により定まる．
T_0(x)=1,
T_1(x)=x,
T_{n+1}(x)=2xT_n(x)-T_{n-1}(x),\quad(n\geq 1).
証明
加法定理から
\cos(n-1)\theta=\cos n\theta\cos\theta+\sin n\theta\sin\theta,
\cos(n+1)\theta=\cos n\theta\cos\theta-\sin n\theta\sin\theta

である．辺々足すと
\cos(n-1)\theta + \cos(n+1)\theta = 2\cos\theta\cos n\theta
である．
よって， T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)が成立．
T_0(x)=1,\ T_1(x)=xも， T_n(x)の定義より成立．
命題の漸化式を満たす多項式の列は一意に定まることから，それは T_n(x)である．
[証明終わり]

命題
多項式 T_n(x)は以下で表される．
\displaystyle T_n(x)=\frac{\left(x+\sqrt{x^2-1}\right)^n+\left(x-\sqrt{x^2-1}\right)^n}{2}
証明
上で示した漸化式は行列を使うと以下のように書ける．
\begin{bmatrix}T_{n+1}\\T_{n}\end{bmatrix}=\begin{bmatrix}2x & -1 \\1 & 0 \end{bmatrix}\begin{bmatrix}T_{n}\\T_{n-1}\end{bmatrix}
初期値は T_0=1, T_1=xなので
\begin{bmatrix}T_{n+1}\\T_{n}\end{bmatrix}=\begin{bmatrix}2x & -1 \\1 & 0 \end{bmatrix}^n\begin{bmatrix}x\\1\end{bmatrix}
である．あとはこの行列
A\triangleq\begin{bmatrix}2x & -1 \\1 & 0 \end{bmatrix}
の n乗を求めればよい．行列 Aは，行列
P\triangleq\begin{bmatrix}1 & 1 \\x-\sqrt{x^2-1} & x+\sqrt{x^2-1} \end{bmatrix}
により対角化できて，
P^{-1}AP=\begin{bmatrix}x+\sqrt{x^2-1} & 0 \\0 & x-\sqrt{x^2-1} \end{bmatrix}
より，結局
A^n=\begin{bmatrix}\left(x+\sqrt{x^2-1}\right)^{n+1}-\left(x-\sqrt{x^2-1}\right)^{n+1} & -\left(x+\sqrt{x^2-1}\right)^{n}+\left(x-\sqrt{x^2-1}\right)^{n} \\\left(x-\sqrt{x^2-1}\right)\left(x+\sqrt{x^2-1}\right)^{n}-\left(x+\sqrt{x^2-1}\right)\left(x-\sqrt{x^2-1}\right)^{n} & -\left(x-\sqrt{x^2-1}\right)\left(x+\sqrt{x^2-1}\right)^{n}+\left(x+\sqrt{x^2-1}\right)\left(x-\sqrt{x^2-1}\right)^{n} \end{bmatrix}
となり， T_nが得られる．
[証明終わり]

この方法を解説しているサイトは，探した感じだと
チェビシェフ多項式の計算法
などがありました．

チェビシェフ多項式の母関数

多項式列 \{T_n(x)\}_{n=0}^\inftyの母関数とは，二変数 t,nに関する形式的冪級数
\displaystyle\sum_{n=0}^\infty T_n(x)t^n
のことです．これをチェビシェフ多項式の母関数と呼びましょう．
一般にある数列の性質を知りたいときには，その母関数のきれいな表示が分かると嬉しいことが多いです．
チェビシェフ多項式の母関数のきれいな表示を計算する方法は色々ありますが，ここでは上で求めた漸化式を使ってみます．

命題 (チェビシェフ多項式の母関数)
チェビシェフ多項式の母関数は以下のように表される．
\displaystyle\sum_{n=0}^\infty T_n(x)t^n=\frac{1-tx}{1-2tx+t^2}.
証明
漸化式T_{n+2}=2xT_{n+1}-T_nの両辺に t^{n+2}をかけ， nについて和を取ると
\displaystyle\sum_{n=0}^\infty T_{n+2}t^{n+2}=2tx\sum_{n=0}^{\infty}T_{n+1}t^{n+1}-t^2\sum_{n=0}^\infty T_nt^n.
ここから和の中身を揃え以下のようにする．
\displaystyle\sum_{n=0}^\infty T_{n}t^{n}-T_0-T_1t=2tx\left(\sum_{n=0}^{\infty}T_{n}t^{n}-T_0\right)-t^2\sum_{n=0}^\infty T_nt^n.
初期値は T_0=1, T_1=xなので，
\displaystyle\sum_{n=0}^\infty T_{n}t^{n}-1-tx=2tx\left(\sum_{n=0}^{\infty}T_{n}t^{n}-1\right)-t^2\sum_{n=0}^\infty T_nt^n.

これを \displaystyle\sum_{n=0}^\infty T_{n}t^{n}について解けば主張が得られる．
[証明終わり]

チェビシェフ多項式のきれいな表示を計算する他の方法として
ド・モルガンの定理を使う方法があり，以下のサイトで紹介されています．
チェビシェフの多項式

方法３：母関数を展開する

上で求めた母関数を再び
\displaystyle\frac{1-tx}{1-2tx+t^2}=\sum_{n=0}^\infty (\cdots\cdots)t^{n}
の形に展開することで， T_n(x)を求めます．

命題
多項式 T_n(x)は以下で表される．
\displaystyle T_n(x)=\sum_{\ 0\leq k\leq n\\n\equiv k\ {\rm mod} 2}2^{k-1}(-1)^{(n-k)/2}\left(\binom{(n+k)/2}{(n-k)/2}+\binom{(n+k)/2-1}{(n-k)/2-1}\right)x^k
但し，上記の和は nと偶奇が一致する kだけを足すという意味である．
証明
\displaystyle\frac{1-tx}{1-2tx+t^2}=\frac{1-tx}{1+t^2}\frac{1}{1-\frac{2t}{1+t^2}x}
ここで関係式 \displaystyle \frac{1}{1-r}=\sum_{n=0}^\infty r^nを使うと，
\displaystyle\frac{1-tx}{1+t^2}\frac{1}{1-\frac{2t}{1+t^2}x}=\frac{1-tx}{1+t^2}\sum_{n=0}^\infty\left(\frac{2t}{1+t^2}\right)^nx^n
\displaystyle=\sum_{n=0}^\infty\left(\frac{(2t)^n(1-t^2)}{2(t+t^2)^{n+1}}\right)x^n+\frac{1}{2}

和の中身 \displaystyle\frac{(2t)^n(1-t^2)}{2(t+t^2)^{n+1}}について考える．
関係式 \displaystyle \frac{1}{(1-z)^{m+1}}=\sum_{n=0}^\infty \binom{m+n}{n}z^nを使うと，
\displaystyle\frac{(2t)^n(1-t^2)}{2(t+t^2)^{n+1}}=\frac{(2t)^n(1-t^2)}{2}\sum_{k=0}^\infty \binom{n+k}{k}(-t^2)^k
\displaystyle=\frac{(2t)^n}{2}\left\{\sum_{k=0}^\infty\binom{n+k}{k}(-1)t^{2k}-\sum_{k=0}^\infty\binom{n+k}{k}(-1)t^{2k+1}\right\}
\displaystyle=2^{n-1}\sum_{k=0}^{\infty}\left(\binom{n+k}{k}+\binom{n+k-1}{k-1}\right)(-1)^kt^{2k+n}-\frac{1}{2}\delta_{n,0}

但し， \delta_{n,0}はクロネッカーのデルタ ( i=jのとき \delta_{i,j}=1， i\neq jのとき \delta_{i,j}=0)であり，負の二項係数の値は \displaystyle\binom{r}{-1}= \delta_{r,-1}である．

以上の計算から
\displaystyle\frac{1-tx}{1-2tx+t^2}=\sum_{n=0}^\infty\sum_{k=0}^{\infty}2^{n-1}\left(\binom{n+k}{k}+\binom{n+k-1}{k-1}\right)(-1)^kt^{2k}(tx)^n
が成立することがわかる．

上記の式は
\displaystyle\sum_{n=0}^\infty\sum_{k=0}^{\infty}f(n,k)t^{2k}(tx)^n
という形の和であるが，和の内部変数 n,kをいじることで，この和を
\displaystyle\sum_{n=0}^\infty\sum_{k=0}^{\infty}g(n,k)x^kt^n
という形に書き変えることを考える．

和 \displaystyle\sum_{n=0}^\infty\sum_{k=0}^{\infty}f(n,k)t^{2k}(tx)^n=f(0,0)+f(1,0)tx+f(0,1)t^2+f(2,0)t^2x^2+\cdots
において， t^ix^jの係数を表にしてみた．空欄は 0を意味する．

f:id:iwalion:20191113100942p:plain
t^ix^jの係数

これを見るに，
\displaystyle\sum_{n=0}^\infty\sum_{k=0}^{\infty}f(n,k)t^{2k}(tx)^n=\sum_{n=0}^\infty\sum_{\ 0\leq k\leq n\\n\equiv k\ {\rm mod}2}f\left(k,\frac{n-k}{2}\right)x^kt^n
になりそう．
このことは数学的帰納法で示す必要があるが，省略する．
これを使って上で得た和の内部変数を取り替えれば，

\displaystyle\frac{1-tx}{1-2tx+t^2}=\sum_{n=0}^\infty\sum_{\ 0\leq k\leq n\\n\equiv k\ {\rm mod} 2}2^{k-1}(-1)^{(n-k)/2}\left(\binom{(n+k)/2}{(n-k)/2}+\binom{(n+k)/2-1}{(n-k)/2-1}\right)x^kt^n
を得る．

一方， \displaystyle\sum_{n=0}^\infty T_n(x)t^n=\frac{1-tx}{1-2tx+t^2}
だったので，これらを比較すれば主張を得る．
[証明終わり]

方法４：母関数からチェビシェフの微分方程式を作って解く

この方法は，私の理解があやふやな部分があり，また少々天下り的です．
チェビシェフ多項式の母関数
\displaystyle T(x,t)\triangleq \sum_{n=0}^\infty T_n(x)t^n=\frac{1-tx}{1-2tx+t^2}
から，形式的冪級数
\displaystyle\sum_{n=0}^\infty n^2T_n(x)t^n
がどんな表示を持つかが計算できます．計算には以下の方法を使います．

命題
\displaystyle f(t)=\sum_{n=0}^\infty a_nt^nのとき， \displaystyle\sum_{n=0}^\infty na_nt^n=t\frac{df(t)}{dt}である．
証明
\displaystyle f(t)=\sum_{n=0}^\infty a_nt^n=a_0+a_1t+a_2t^2+a_3t^3+\cdots
である．微分すると
\displaystyle \frac{df(t)}{dt}=a_1+2a_2t+3a_3t^2+\cdots
となる．よって，
\displaystyle t\frac{df(t)}{dt}=a_1t+2a_2t^2+3a_3t^3+\cdots=\sum_{n=0}^\infty na_nt^n.
[証明終わり]

これを何度も使えば，
\displaystyle \sum_{n=0}^\infty n^2a_nt^n=t\frac{d}{dt}\left(t\frac{df(t)}{dt}\right), \sum_{n=0}^\infty n^3a_nt^n=t\frac{d}{dt}\left(t\frac{d}{dt}\left(t\frac{df(t)}{dt}\right)\right)
なども言えます．

チェビシェフ多項式の母関数の場合は，
\displaystyle\sum_{n=0}^\infty n^2T_n(x)t^n=t\frac{\partial}{\partial t}\left(t\frac{\partial T(x,t)}{\partial t}\right)=-\frac{t^5x+2t^4x^2-4t^4-2t^2x^2+4t^2-tx}{(t^2-2tx+1)^3}
となります．

突然ですが，これが T(x,t)の xでの一階と二階の偏微分
\displaystyle\frac{\partial T(x,t)}{\partial x}=\sum_{n=0}^\infty\frac{d}{dx}T_n(x)t^n={\frac {-{t}^{3}+t}{ \left( {t}^{2}-2\,tx+1 \right) ^{2}}},
\displaystyle\frac{\partial^2 T(x,t)}{\partial x^2}=\sum_{n=0}^\infty\frac{d^2}{dx^2}T_n(x)t^n={\frac {-4\,{t}^{4}+4\,{t}^{2}}{ \left( {t}^{2}-2\,tx+1 \right) ^{3}}}
の線形結合で書けないかを考えてみることにします．

恒等式
\displaystyle A\frac{\partial T(x,t)}{\partial x}+B\frac{\partial^2 T(x,t)}{\partial x^2}+t\frac{\partial}{\partial t}\left(t\frac{\partial T(x,t)}{\partial t}\right)=0
が成立する条件を考えると， A=-x,\ B=1-x^2であればよいことがわかります．

つまり，
\displaystyle \sum_{n=0}^\infty\left((1-x^2)\frac{d^2T_n(x)}{dx}-x\frac{dT_n(x)}{dx}+n^2T_n(x)\right)=0
が成立して，よって我々が求めたい多項式 T_n(x)は，微分方程式
\displaystyle (1-x^2)\frac{d^2T_n(x)}{dx}-x\frac{dT_n(x)}{dx}+n^2T_n(x)=0
の解であることが分かります．

この微分方程式は「チェビシェフの微分方程式」と呼ばれていてWikipediaもあります．
チェビシェフ方程式 - Wikipedia

これを適切な初期条件のもと解けば T_n(x)が求まるはずなのですが，それはいつか書くことにします．

その他の方法について

チェビシェフ多項式についての話題は他の多くのサイトで扱われているので，本記事で紹介しない方法を扱っているサイトを挙げておきます．

shadowacademy.web.fc2.com

  • 基本対称式を使う方法について

qiita.com

「指の本数限定ジャンケン」で負けにくい手の出し方の研究

プログラミング

2019年9月21日に(あんちべ! 俺がS式だ)@AntiBayesianさんが，次のようなツイートをしました．

引用：(あんちべ! 俺がS式だ)@AntiBayesian

社会性ゼロの人間に結婚式のパーティゲームを任せると「五回じゃんけんして勝利数多い方が勝ち、但し五回で合計13本しか指を使ってはいけない、つまりパーは最大2回しか出せないという『限定じゃんけん』です」とかやって、エンジニアの新郎新婦や友人は喜ぶが親御さんをポカンとさせるとかしてしまう

このツイートで書かれているゲームを「5回13本 - 限定ジャンケン」と呼ぶことにします．
ただし，問題を簡単にするための追加ルールとして n回分の手の出し方をお互い同時に出し合うものとします．
つまり，二人で n回同時にジャンケンして勝利数が多いほうが勝ち．ただし出せる指の本数は一人合計 m\ (0\leq m\leq 5n)本までというゲームを「 n回 m本 - 限定ジャンケン」と呼びます．

このゲームにおいて相手が全ての可能な手の出し方の中からランダムな手を出してくるとした場合に，できるだけ負けにくい出し方をいくつかの n,mについて調べます．
調べる方法は素朴に総当りをしました．

本題に入る前に，まず一般の n,mについて可能な手の出し方の総数について基本的なことを調べておきます．

組合せ論的な議論

以下で「｛👊，✌，✋｝から n回出す」という場合，順番を区別します．
例えば，（👊，✋，✋）と（✋，👊，✋）は違う出し方とします．

命題１
｛👊，✌，✋｝から n回出すときに，指の本数の合計が m本になるような出し方の総数は (1+x^2+x^5)^nにおける x^mの係数である．
例えば，5回13本 - 限定ジャンケンで出せる出し方，つまり（👊，👊，👊，👊，👊）や（✋，👊，✌，✋，👊）などを全部数えると，その数は
(1+x^2+x^5)^5において x^{13}より高次の項を消したあと x=1とした値，つまり152通りあります．

また命題１から次のことも言えます．

命題２
｛👊，✌，✋｝から n回出すときに，指の本数の合計が m本になるような出し方の総数を J(n,m)する．このとき J(n,m)の母関数は以下のように書ける．
\sum_{n\geq 0}\sum_{m_\geq 0} J(n,m)y^nx^m=\frac{1}{1-y(1+x^2+x^5)}

このような性質を調べはしたものの，以下で特に使うことはありません．（検算とかに使いました．）

計算機による総当り

5回13本 - 限定ジャンケンで可能な152通りの手の出し方には強さの非対称性があります．
例えば，出し方（👊，👊，👊，👊，👊）は152通り中45通りの出し方に負けます．
一方で，出し方（✋，👊，✌，✋，👊）は，152通り中50通りの出し方に負けます．
ただし，順番を変えただけの出し方は152通りの中に全て含まれるため，例えば（✋，👊，👊，👊，👊）と（👊，👊，👊，✋，👊）の強さは同じであることに注意しておきます．

そこでいくつかの n,mについて， n回 m本 - 限定ジャンケンで最も負けにくい出し方は何なのかを調べていきます．

以下の結果は， n=5とし，「 m（出せる指の本数の上限）」，「可能な出し方の総数」，「最も負けにくい出し方」，「その出し方に勝てるような出し方の総数」「敗率」を表にしています．
「最も負けにくい出し方」では，上記の理由から順番が違うだけの出し方は省略して一つのみ書いています．
指の本数が0本制限と1本制限の場合など， mが増えても状況が変わらない場合があります．それらは最も小さい mで代表することにします．
「敗率」は，負け数÷可能な出し方の総数で計算します．

実験結果（ n=5）
m 可能な出し方の総数 最も負けにくい出し方 負け数 敗率
0 1 👊，👊，👊，👊，👊 0 0
2 6 👊，👊，👊，👊，👊 0 0
4 16 👊，👊，👊，👊，👊 0 0
5 21 👊，👊，👊，👊，✋ 1 0.047619
6 31 👊，👊，👊，👊，✋ 1 0.0322581
7 51 👊，👊，👊，👊，👊
👊，👊，👊，👊，✋		 5 0.0980392
8 56 👊，👊，👊，👊，👊
👊，👊，👊，👊，✋		 5 0.0892857
9 86 👊，👊，👊，👊，👊 5 0.0581395
10 97 👊，👊，👊，👊，👊
👊，👊，👊，✋，✋		 15 0.154639
11 117 👊，👊，👊，👊，👊 15 0.128205
12 147 👊，👊，👊，👊，✋
👊，👊，👊，✋，✋		 33 0.22449
13 152 👊，👊，👊，👊，✋ 33 0.217105
14 182 👊，👊，👊，👊，👊
👊，👊，👊，👊，✋		 45 0.247253
15 192 👊，👊，👊，👊，👊
👊，👊，👊，👊，✋		 55 0.286458
16 202 👊，👊，👊，👊，👊 55 0.272277
17 222 👊，👊，👊，👊，👊 75 0.337838
19 232 👊，👊，👊，👊，👊
👊，👊，👊，👊，✌
👊，👊，👊，👊，✋
👊，👊，👊，✋，✋		 85 0.366379
20 237 👊，👊，👊，👊，👊
👊，👊，👊，👊，✌
👊，👊，👊，👊，✋
👊，👊，👊，✋，✋		 90 0.379747
22 242 👊，👊，👊，👊，👊
👊，👊，👊，👊，✌
👊，👊，👊，👊，✋
👊，👊，👊，✌，✌
👊，👊，👊，✌，✋
👊，👊，👊，✋，✋
👊，👊，✌，✋，✋
👊，👊，✋，✋，✋
👊，✋，✋，✋，✋
 95 0.392562
25 243 任意の出し方 96 0.395062

思ったこととか

結局，5回13本 - 限定ジャンケンでは👊を４回，✋を１回出しとけばいいと思います．
指の本数の上限を設定するということは，✋が出しにくくなるということなので， 👊が強い環境になっていました．
この記事は，実験してみたというだけなんですが，ここから何かさらに理論的なことを調べれたらいいなと思ってます．

この限定ジャンケンの変種として，「両プレイヤーの出せる指の本数の合計に上限が設定されたジャンケン」はどうでしょうか．

有限を数えるときも無限を経由できる場合があるという話

母関数

高校数学における場合の数や数列で練習を積んだおかげで、皆さんは有限個の何かを足し合わせることには慣れていると思います。
ところで、有限和を計算する場合はふつう有限の世界だけでの計算をする気がします。
有限のものを数える場合に、「有限＝無限ー無限」の形にすることで無限の世界を経由できるんじゃないかなって思って少し考えてみました。

等比数列の和

まず等比数列の和を考えてみます。高校で習うように
1+x+x^2+\cdots +x^{n-1}=\frac{1-x^{n}}{1-x}・・・（１）
です。
この式の証明は例えば、 f(x)=1+x+\cdots + x^{n-1}とおいて、両辺に xをかけて
xf(x)=x+\cdots + x^{n-1}+x^{n}とし、 f(x)との差を考えると
(1-x)f(x)=1-x^{n}となる、としてできます。
また、 |x|<1なら、 n\to\inftyの極限を取ると幾何級数
1+x+x^2+\cdots = \frac{1}{1-x}になるのでした。

ここで一旦上述の流れを忘れて、 \frac{1}{1-x}というのは、無限級数
1+x+x^2+\cdots=\sum_{i=0}^{\infty}x^iを表す記号だと思うことにします。
冒頭の（１）式を眺めると、右辺は
\frac{1-x^{n}}{1-x}=\frac{1}{1-x}-\frac{x^{n}}{1-x}=\sum_{i=0}^{\infty}x^i-x^{n}\sum_{i=0}^{\infty}x^{i}
とかけます。最初の部分は
\sum_{i=0}^{\infty}x^i=1+x+x^2+\cdotsであり、残りの部分は
x^{n}\sum_{i=0}^{\infty}x^i=x^{n}(1+x+x^2+\cdots)=x^{n}+x^{n+1}+\cdotsなので、その差は
\sum_{i=0}^{\infty}x^i-x^{n}\sum_{i=0}^{\infty}x^{i}=1+x+\cdots+x^{n-1}
になります。
これは、（１）式の別視点からの説明になってるんじゃんないかな、って思います。

組合せ的なものを使った説明　「無限を経由」の意味

上の話を言い換えるために次のような問題を考えてみます。

問題
0から n-1までの番号が書かれた箱があり、そのうちの一つの箱に玉を入れます。
すべての入れ方について x^{箱の番号}を足し合わせてください。
記号が分かる人向けに書くと、 \sum_{i\in\{0,\ldots,n-1\}}x^iを簡単な形にしてくれという問題のつもりです。
例えば n=4だと、
○□□□→ x^0=1
□○□□→ x^1
□□○□→ x^2
□□□○→ x^3
の四通りなので、答えは 1+x+x^2+x^3=\frac{1-x^{4}}{1-x}です。
このように、すべての場合にわたって何かを足し合わせた式を母関数というらしいです。

この問題を考える際に、上のように直接考えてもいいですが、以下のように「無限を経由して」考えることもできます。
まず、箱が n個のときの求める和を f(n)としておきます。
箱の数が無限大だとした場合の、 x^{箱の番号}の和を二通りの方法で表します。
第一の表し方：
箱０に入れる場合、箱１に入れる場合、・・・と無限に続くので x^{箱の番号}の和は
1+x+x^2+\cdots=\frac{1}{1-x}です。

第二の表し方：
玉がどこに入るかで二つに場合分けします。
玉が 0から n-1までの箱に入る場合、和は f(n)です。
玉が n以降の箱に入る場合、和は
x^{n}+x^{n+1}+x^{n+2}+\cdots=x^n(1+x+x^2+\cdots)=\frac{x^n}{1-x}です。
だから、箱の数が無限大だとした場合の、 x^{箱の番号}の和は
f(n)+\frac{x^n}{1-x}
です。

以上から \frac{1}{1-x}=f(n)+\frac{x^n}{1-x}であり、 f(n)=\frac{1-x^n}{1-x}です。

もうすこし複雑な問題

以下の問題を考えます。

問題
0から n-1までの番号が書かれた箱があり、そこに赤い玉と青い玉を入れます。ただし、

  • 同じ箱には玉は一つしか入りません。
  • 赤い玉は青い玉より小さい番号の箱に入れます。

すべての入れ方について x^{赤玉の入ってる箱番号}y^{青玉の入ってる箱番号}を足し合わせてください。

例えば n=4だと、
赤青□□→ x^0y^1
赤□青□→ x^0y^2
赤□□青→ x^0y^3
□赤青□→ x^1y^2
□赤□青→ x^1y^3
□□赤青→ x^2y^3
の６通りを考えれば良いので、求める式は
y+y^2+y^3+xy^2+xy^3+x^2y^3です。

まず普通の数え方で解いてみます。青玉が入る場所は 1から n-1であり、
赤玉が入りうる場所は 0から青玉の入る場所までなので、和は
\sum_{i=1}^{n-1}\sum_{j=0}^{i-1}x^jy^iです。
これを計算すると、
\sum_{i=1}^{n-1}\sum_{j=0}^{i-1}x^jy^i=\sum_{i=1}^{n-1}y^i\sum_{j=0}^{i-1}x^j
=\sum_{i=1}^{n-1}y^i\frac{1-x^i}{1-x}=\frac{1}{1-x}\sum_{i=1}^{n-1}y^i-\frac{1}{1-x}\sum_{i=1}^{n-1}(xy)^i
=\frac{1}{1-x}\left(\sum_{i=0}^{n-1}y^i-1\right)-\frac{1}{1-x}\left(\sum_{i=0}^{n-1}(xy)^i-1\right)
=\frac{1-y^n}{(1-x)(1-y)}-\frac{1-(xy)^n}{(1-x)(1-xy)}

です。
は？って感じに見えますけど、例えば n=4とかして実際計算してみると、ちゃんと
y+y^2+y^3+xy^2+xy^3+x^2y^3になります。


次に、無限を経由してやってみようと思います。
次のような、 (i,j)成分に x^iy^jが書いてある表を考えてみます。

例えば n=5の場合に計算すべきものは、上の表において色がつけてある部分の和です。
この和を f(n)としておきます。


以下の緑色がつけられた部分（右側に無限に続いている）の和を二通りの方法で表してみようと思います。

１つ目の方法：
表において傾き１の線上に乗っている部分を纏めて計算します。
y(1+xy+\cdots+x^{n-2}y^{n-2})+y^2(1+xy+\cdots+x^{n-2}y^{n-2})+y^3(1+xy+\cdots+x^{n-2}y^{n-2})+\cdots
=y(1+y+y^2+\cdots)(1+xy+\cdots+x^{n-2}y^{n-2})
=\frac{y(1-x^{n-1}y^{n-1})}{(1-y)(1-xy)}

２つ目の方法：
部分を二つに分けます。一つは和が f(n)になる、最初の絵で示した薄い肌色の部分。
もう一つは以下の部分です。

つまり図でいうと以下のような感じに分けます。

f(x)以外の部分の和は
y^{n}(1+x+\cdots+x^{n-2})+y^{n+1}(1+x+\cdots+x^{n-2})+y^{n+2}(1+x+\cdots+x^{n-2})+\cdots
=y^n(1+y+y^2+\cdots)(1+x+\cdots+x^{n-2})=y^n\frac{1}{1-y}\frac{1-x^{n-1}}{1-x}
よって、全体の和は
f(n)+\frac{y^n(1-x^{n-1})}{(1-y)(1-x)}
です。

以上から
f(n)=\frac{y(1-x^{n-1}y^{n-1})}{(1-y)(1-xy)}-\frac{y^n(1-x^{n-1})}{(1-y)(1-x)}
がわかります。

上で普通に求めた f(n)と見た目は違いますが、計算すると一緒です。
逆に言えば、今やった計算は
\frac{1-y^n}{(1-x)(1-y)}-\frac{1-(xy)^n}{(1-x)(1-xy)}=\frac{y(1-x^{n-1}y^{n-1})}{(1-y)(1-xy)}-\frac{y^n(1-x^{n-1})}{(1-y)(1-x)}
の証明になっています。
これを証明して何の意味があるのかは、知りません。

結局無限を経由することに何の利点があるのか

記事を書いてはみたものの、これが説明できないことが、今けっこう辛いところです。
有限和を直接は計算しにくいけど、無限ー無限の形にできて無限のほうは比較的簡単に求められるような例を今探しています。