2025-11-24

バイナリ列に現れるフィボナッチ数

$1$ が連続しないバイナリ列の個数がフィボナッチ数なのは有名な事実である．
参考：The Fibonacci Recurrence and Counting Binary Strings | Michael Levet
また，以前ブログでバイナリ列をある同値関係で割ると同値類の数がフィボナッチ数だというのを扱ったことがある．
参考：バイナリ列に現れるフィボナッチ数 | Mathlog

今回は，「バイナリ列の先頭に，そのバイナリ列に含まれる $0$ の数だけの $1$ がある」という条件を満たすバイナリ列の個数がフィボナッチ数であることを紹介する．

有限長の列 $w$ に対して $|w|_0$ で $w$ に含まれる $0$ の数を表す．
長さ $n$ のバイナリ列の集合を $\mathcal{B}_n$ とかく．

$F_0\triangleq0, F_1\triangleq1, F_{n}\triangleq F_{n-1}+F_{n-2}\ (n\geq 2)$ で定義される数列をフィボナッチ数という．
例えば $F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, F_5=5,\ldots$ である．

集合 $\mathcal{F}_n$ を
$\mathcal{F}_n\triangleq \{w=w_1w_2\cdots w_n\in\mathcal{B}_n\mid w_i=1\ (i=1,\ldots,|w|_0)\}$
と定義する．
例えば
$\mathcal{F}_0=\{\varepsilon\}$
$\mathcal{F}_1=\{1\}$
$\mathcal{F}_2=\{10,11\}$
$\mathcal{F}_3=\{110,101,111\}$
$\mathcal{F}_4=\{1100,1110,1101,1011,1111\}$
である．

定理 $|\mathcal{F}_n|=F_{n+1}\ (n\geq 0)$
証明
$n\geq 2$ のとき下式が成立する．
$\mathcal{F}_n=\mathcal{F}_{n-1}1\sqcup1\mathcal{F}_{n-2}0$ ．

日本語で書くと， $\mathcal{F}_{n}$ の元は， $\mathcal{F}_{n-1}$ の元の末尾に $1$ をつけたものであるか，あるいは
$\mathcal{F}_{n-2}$ の元の先頭に1をつけ末尾に $0$ をつけたものであるかのいずれかである，ということである．
（証明終わり）

2025-11-12

ヤング図形のhook-content公式からhook長公式を出す方法

この記事は組合せ論アドベントカレンダー2024の24日目の記事です．
組合せ論 Advent Calendar 2024 - Adventar

hook長公式はhook-content公式から導出できると色々なところに書いてあるのだが，今までやり方をよく知らなかったので今回勉強してみた．

色々なところというのは，例えば岡田のRIMS講究録（下記url）やProctorのRIMS講究録（下記url）のCorollary1とか．
https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1870-05.pdf
Kyoto University Research Information Repository

本記事の内容にオリジナルな点は全く無く，例えばネットで読めるところでいうと田川の講義録（下記url）や下記ブログの記事（下記url）に本記事の内容はすべて含まれる．
https://web.wakayama-u.ac.jp/~tagawa/lecture/tsukuba2006.pdf
Stanley’s theory of P-partitions and the Hook Formula | Wildon's Weblog

概要

本記事ではヤング図形は「イギリス式」記法で書くことにする．
ヤング図形の「上」とか「右」とか言う場合は，イギリス式で書いたときの上とか右のことである．

ヤング図形の箱の数を $n$ とする．
定義（標準盤）
標準盤とは， $1,\ldots,n$ の数をそれぞれちょうど一回づつ

左から右へ向けて単調増大
上から下に向けて単調増大

となるようにヤング図形に書き入れたものである．
形がヤング図形 $\lambda$ である標準盤の数は普通 $f^\lambda$ とかく．

定義（半標準盤）
要素上限 $m$ の半標準盤とは，ヤング図形の箱に $\{1,\ldots,m\}$ の数字を

左から右へ向けて単調非減少
上から下に向けて狭義単調増大

となるようにヤング図形に書き入れたものである．数字の重複や使わない数字があってもよい．
要素上限が $m$ で形が $\lambda$ の半標準盤の集合は，標準盤ほど一般的な記法ではないがよく ${\rm SSYT}(\lambda;m)$ と書かれる．

ヤング図形を任意に固定したときの標準盤の個数には下記の積公式が知られていてhook長公式，あるいは発見者の名からFrame-Robinson-Thrall hook formula (FRT hook formula)などと呼ばれる．
定理（hook長公式）
ヤング図形の箱の数を $n$ とする．以下が成り立つ．
$\displaystyle f^{\lambda}=\frac{n!}{\prod_{(i,j)\in\lambda}h_{i,j}}$ .

有名すぎる事実だし本稿の本筋ではないので，ここでは改めて上記の $h$ の意味などは書かない．詳しくは以下サイトなどを見てほしい．
https://www.math.aoyama.ac.jp/~kyo/preprint/CPower_textbook_combinatorics_2020.pdf

半標準版のほうにも似たような公式があり，こちらはhook-content公式と呼ばれる．半標準盤の個数が積で書けるのを発見したのはLittlewoodで，Stanleyがそれを現在のhookとcontentを使った形に書き換えたらしい．
定理（hook-content公式）
任意のヤング図形 $\lambda$ と自然数 $m$ に対して以下が成り立つ．
$\displaystyle \sum_{T\in{\rm SSYT}(\lambda;m)}q^{|T|}=q^{\sum_{i}i\lambda_i}\prod_{(i,j)\in\lambda}\frac{1-q^{m+c_{i,j}}}{1-q^{h_{i,j}}}$ .

上記で $|T|$ は半標準盤 $T$ に書き入れられた数字の和を表す．
ここでも上記右辺の和の動く範囲や $c$ の意味は改めて書くことはしない．詳しくは以下サイトを参照のこと．
https://arxiv.org/pdf/math/9807068
重要なこととして上式中の $h$ はhook長公式で出てきた $h$ と同じものである．

hook-content公式からhook長公式が導出できるといろいろな場所に書いてあり，導出の方法を書いてくれている文献もあるのだが，その導出というのが単に式をいじれば出来るものではなく，Stanleyの $P$ -partitionの理論で出てくる補題を使わないといけないものっぽい．
その導出方法をよく理解できていない状態だったので，今回勉強してみたというのが本記事で書きたいことである．

以下では $P$ -partitionの話を必要な補題の証明まで書くが，見なくていい人は飛ばして次の章へ行ってほしい．

$P$ -partitionの話を必要な部分だけ書く

StanleyのEnumerative combinatorics volume 2, second edition (2011)の3章15節あたりに書いてあることをまとめる．Stanley本は以下で無料で見れる．
https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf
半順序集合の定義などは既知とする．以下では $\mathbb{N}_0$ で非負整数の全体を表す．関数 $f\colon X\to Y$ と $g\colon Y\to X$ が与えられているとき $gf$ は関数 $X\ni x\mapsto g(f(x))\in Z$ を表す．

定義（ $w$ -compatible）
関数 $f\colon\{1,\ldots,n\}\to\mathbb{N}_0$ が置換 $w=w_1\cdots w_n\in\mathfrak{S}_n$ に関して $w$ -compatibleであるとは以下の二条件を満たすことである．

任意の $i,j\in\{1,\ldots,n\}\ (i\leq j)$ に対して $f(w_i)\geq f(w_j)$ である．
任意の $i,j\in\{1,\ldots,n\}\ (i\leq j)$ に対して $w_i>w_j$ ならば $f(w_i)> f(w_j)$ である．

定理1（Stanley本の定理1.4.11）
任意の関数 $f\colon\{1,\ldots,n\}\to\mathbb{N}_0$ に対して置換 $w\in\mathfrak{S}_n$ が一意的に存在して $f$ は $w$ -compatibleである．

以下では小文字で $p$ と書くと，有限半順序集合 $P$ の濃度 $p=|P|$ を表すと約束する．
有限半順序集合 $P$ に対して $P$ から集合 $\{1,\ldots,p\}$ への全単射を $P$ のラベリングという．
定義（ $P$ -partition）
半順序集合 $P$ と $P$ のラベリング $\omega$ が与えられているとする．
関数 $\sigma\colon P\to \mathbb{N}_0$ が $(P,\omega)$ -partitionであるとは，以下の二条件を満たすことである．

任意の $x,y\in P\ (x\leq y)$ に対して $\sigma(x)\geq\sigma(y)$ である．
任意の $x,y\in P\ (x\leq y)$ に対して $\omega(x)>\omega(y)$ ならば $\sigma(x)>\sigma(y)$ である．

有限半順序集合 $P$ と $P$ のラベリング $\omega$ が与えられたとき， $(P,\omega)$ -partitionの集合を $\mathcal{A}(P,\omega)$ とかく．
また置換 $w\in\mathfrak{S}_{p}$ に対して
$S_w\triangleq\{\sigma\colon P\to\mathbb{N}_0\mid \sigma\omega^{-1}{\rm は}w{\rm -compatible}\}$
と定める．
集合 $S_w$ の母関数 $F_w(x_1,\ldots,x_p)$ を， $P=\{t_1,\ldots,t_p\}$ として
$F_w(x_1,\ldots,x_p)\triangleq\sum_{\sigma\in S_w}x_1^{\sigma(t_1)}\cdots x_p^{\sigma(t_p)}$
と定める．
以下では $\theta(x_i)\triangleq i\ (i=1,\ldots,p)$ とし， $D(w)$ は置換 $w$ の下降点集合つまり
$D(w)=D(w_1\cdots w_n)\triangleq\{i\mid w_i>w_{i+1}\}$
と定める．
定理2（Stanley本の補題3.15.4）
有限半順序集合 $P=\{t_1,\ldots,t_p\}$ と $P$ のラベリング $\omega$ に対して
$\displaystyle\label{eq:Fw}F_{w}(x_1,\ldots,x_p)=\frac{\prod_{j\in D(w)}x_{\theta\omega^{-1}w(1)}\cdots x_{\theta\omega^{-1}w(j)}}{\prod_{i=1}^p(1-x_{\theta\omega^{-1}w(1)}\cdots x_{\theta\omega^{-1}w(i)})}$
が成り立つ．
証明
証明といいつつ，ここでは定理1が成り立つことを確かめる計算の例を与えるだけに留める．
$P=\{t_1,t_2,t_3,t_4\}$ とし，置換 $w=w_1w_2w_3w_4$ において $D(w)=\{1,3\}$ つまり $w_1>w_3$ かつ $w_3>w_4$ であるとする．
このとき母関数 $F_w(x_1,x_2,x_3,x_4)$ は
$\displaystyle \sum_{\sigma(\omega^{-1}w(1))>\sigma(\omega^{-1}w(2))\geq\sigma(\omega^{-1}w(3))>\sigma(\omega^{-1}w(4))\geq 0}x_1^{\sigma(t_1)}\cdots x_p^{\sigma(t_p)}$
（式1とする）である．但し和は
$\sigma(\omega^{-1}w(1))>\sigma(\omega^{-1}w(2))\geq\sigma(\omega^{-1}w(3))>\sigma(\omega^{-1}w(4))\geq 0$
が成り立つような関数 $\sigma\colon P\to\mathbb{N}_0$ 全体にわたってとる．
式 (1)は以下のように式変形して，和の動く範囲にあるstrictな不等号をstrictでない不等号にすることができる．
$\displaystyle=x_{\theta\omega^{-1}w(3)}x_{\theta\omega^{-1}w(2)}x_{\theta\omega^{-1}w(1)}^2\sum_{\sigma(\omega^{-1}w(1))\geq\sigma(\omega^{-1}w(2))\geq\sigma(\omega^{-1}w(3))\geq\sigma(\omega^{-1}w(4))\geq 0}x_1^{\sigma(t_1)}\cdots x_p^{\sigma(t_p)}$
この形にすれば和の部分は計算できて
$\displaystyle\frac{x_{\theta\omega^{-1}w(3)}x_{\theta\omega^{-1}w(2)}x_{\theta\omega^{-1}w(1)}^2}{(1-x_{\theta\omega^{-1}w(1)})(1-x_{\theta\omega^{-1}w(1)}x_{\theta\omega^{-1}w(2)})\cdots(1-x_{\theta\omega^{-1}w(1)}x_{\theta\omega^{-1}w(2)}x_{\theta\omega^{-1}w(3)}x_{\theta\omega^{-1}w(4)})}$
となる．
（証明終わり）

定義（linear extention）
有限半順序集合 $P$ のlinear extentionとは $P$ から集合 $\{1,\ldots,p\}$ への全単射であって任意の $x,y\in P\ (x\lt y)$ に対して $f(x)\lt f(y)$ を満たすものである．
定義（Jordan-Hölder集合）
有限半順序集合 $P$ と $P$ のラベリング $\omega$ に対するJordan-Hölder集合 $\mathcal{L}(P,\omega)$ を
$\mathcal{L}(P,\omega)\triangleq\{\omega(f^{-1}(1))\cdots\omega(f^{-1}(p))\in\mathfrak{S}_{p}\mid f{\rm は}P{\rm のlinear\ extention}\}$
と定義する．

次の定理が， $(P,\omega)$ -partitionの理論において重要らしい．
定理3（Stanley本の補題3.15.3）
有限半順序集合 $P$ と $P$ のラベリング $\omega$ が与えられているとする．
関数 $\sigma\colon P\to\mathbb{N}_0$ が $(P,\omega)$ -partitionであるための必要十分条件はJordan-Hölder集合の元 $w\in\mathcal{L}(P,\omega)$ が一意的に存在して関数 $\sigma\omega^{-1}\colon\{1,\ldots,p\}\to\mathbb{N}_0$ が $w$ -compatibleなことである．
証明
( $\Leftarrow$ )
Jordan-Hölder集合の元 $w\in\mathcal{L}(P,\omega)$ が存在して $\sigma\omega^{-1}$ が $w$ -compatibleであるとする．
置換 $w$ はJordan-Hölder集合の元なので， $P$ のあるlinear extention $f$ を用いて $w=\omega f^{-1}$ とかける．
任意の $x,y\in P\ (x\leq y)$ に対して $\sigma(x)\geq\sigma(y)$ であることを示す．
$f$ はlinear extentionなので $f(x)\leq f(y)$ である．
自然数 $i,j$ を $i\triangleq f(x), j\triangleq f(y)$ と定める．このとき $i\leq j$ である．
関数 $\sigma\omega^{-1}$ は $\omega f^{-1}$ -compatibleなので
$\sigma\omega^{-1}\omega f^{-1}(i)\geq \sigma\omega^{-1}\omega f^{-1}(j)$ である．
つまり $\sigma(x)\geq\sigma(y)$ である．

任意の $x,y\in P\ (x\leq y)$ に対して $\omega(x)\gt\omega(y)$ ならば $\sigma(x)\gt\sigma(y)$ であることを示す．
ここでも $i\triangleq f(x), j\triangleq f(y)$ とする．
$\omega(x)\gt\omega(y)$ より $\omega f^{-1}(i)\gt\omega f^{-1}(j)$ である．
関数 $\sigma \omega^{-1}$ は $\omega f^{-1}$ -compatibleだから
$\sigma\omega^{-1}\omega f^{-1}(i)>\sigma\omega^{-1}\omega f^{-1}(j)$ つまり $\sigma(x)>\sigma(y)$ である．

( $\Rightarrow$ )
$(P,\omega)$ -分割 $\sigma$ が与えられたとき，関数 $\sigma\omega^{-1}$ が $w$ -compatibleとなるような置換 $w\in\mathfrak{S}_p$ は定理1より一意的に定まる．
この置換 $w$ を，全単射 $f\colon P\to\{1,\ldots,p\}$ を用いて $\omega f^{-1}=w$ つまり $f=w^{-1}\omega$ と書くと関数 $f$ はlinear extentionであることを示せばよい．

関数 $\sigma\omega^{-1}$ は $w$ -compatibleなので以下の1, 2が成り立つ．

$i\leq j\Rightarrow\sigma\omega^{-1}w(i)\geq \sigma\omega^{-1}w(j)$ ,
$i\leq j\land w(i)>w(j)\Rightarrow\sigma\omega^{-1}w(i)>\sigma\omega^{-1}w(j)$ .

$f=w^{-1}\omega$ を用いると

$i\leq j\Rightarrow\sigma f^{-1}(i)\geq \sigma f^{-1}(j)$ ,
$i\leq j\land w(i)>w(j)\Rightarrow\sigma f^{-1}(i)>\sigma f^{-1}(j)$ .

$i=f(y), j=f(x)$ とすると $w(i)=\omega(y), w(j)=\omega(x)$ なので

$f(y)\leq f(x)\Rightarrow\sigma(y)\geq \sigma(x)$ ,
$f(y)\leq f(x)\land \omega(y)>\omega(x)\Rightarrow\sigma(y)>\sigma(x)$ .

それぞれ対偶を取ると以下の通りである．

（式１） $f(x)< f(y)\Leftarrow\sigma(x)> \sigma(y)$ ,
（式２） $f(x)< f(y)\lor \omega(y)\leq \omega(x)\Leftarrow\sigma(x)\geq\sigma(y)$ .

これを用いて $x\lt y\Rightarrow f(x)\lt f(y)$ を示す．
$x\lt y$ とすると $(P,\omega)$ -partitionの定義から $\sigma(x)\geq\sigma(y)$ である．
このとき（式２）より $f(x)\lt f(y)$ または $\omega(y)\lt \omega(x)$ である．
$\omega(y)\lt \omega(x)$ のとき， $(P,\omega)$ -partitionの定義から $\sigma(x)>\sigma(y)$ であり，（式１）より $f(x)\lt f(y)$ である．
（証明終わり）

有限半順序集合 $P=\{t_1,\ldots,t_p\}$ と $P$ のラベリング $\omega$ に対して， $(P,\omega)$ -partitionの母関数
$F_{P,\omega}(x_1\ldots,x_p)$ を
$\displaystyle F_{P,\omega}(x_1\ldots,x_p)\triangleq\sum_{\sigma\in\mathcal{A}(P,\omega)}x_1^{\sigma(t_1)}\cdots x_p^{\sigma(t_p)}$
と定める．

定理4（Stanley本の定理3.15.5）
有限半順序集合 $P=\{t_1,\ldots,t_p\}$ と $P$ のラベリング $\omega$ に対して，
$\displaystyle F_{P,\omega}(x_1,\ldots,x_p)=\sum_{w\in\mathcal{L}(P,\omega)}\frac{\prod_{j\in D(w)}x_{\theta\omega^{-1}w(1)}\cdots x_{\theta\omega^{-1}w(j)}}{\prod_{i=1}^p(1-x_{\theta\omega^{-1}w(1)}\cdots x_{\theta\omega^{-1}w(i)})}$
が成り立つ．
証明
定理3より，
$\displaystyle\mathcal{A}(P,\omega)=\bigsqcup_{w\in\mathcal{L}(P,\omega)}S_w$
が成り立つ．ここから
$\displaystyle F_{P,\omega}=\sum_{w\in\mathcal{L}(P,\omega)}F_w$ がいえる．
あとは定理2を使う．
（証明終わり）

有限半順序集合 $P$ と $P$ のラベリング $\omega$ に対して， $(P,\omega)$ -partitionの特殊化された母関数 $G_{P,\omega}(q)$ を
$\displaystyle G_{P,\omega}(q)\triangleq F_{P,\omega}(q,q,\ldots,q)=\sum_{\sigma\in\mathcal{A}(P,\omega)}q^{|\sigma|}$
と定める．但し $\sigma\colon P\to\mathbb{N}_0$ に対して $|\sigma|\triangleq\sum_{t\in P}\sigma(t)$ と定める．
以下の定理は応用上重要っぽい．

定理5（Stanley本の定理3.15.7）
有限半順序集合 $P$ と $P$ のラベリング $\omega$ に対して，
$\displaystyle G_{P,\omega}(q)=\frac{1}{(q;q)_p}\sum_{w\in\mathcal{L}(P,\omega)}q^{{\rm maj}(w)}$
が成り立つ．
但し $w\in\mathfrak{S}_n$ に対して ${\rm maj}(w)\triangleq\sum_{i\in D(w)}i$ である．

hook-content公式からhook長公式を導出（定理5を使う）

標準盤，半標準盤はそれぞれ，特定の半順序集合のlinear extention, $(P,\omega)$ -parititionとみなすことができる．

例えば画像(a)のヤング図形を形として持つ標準盤は画像(b)のHasse図で表される半順序集合のlinear extentionとみなすことができる．
また，(a)を形として持つ半標準盤は(b)の半順序集合 $P$ およびそのラベリング $\omega$ に関する $(P,\omega)$ -partitionとみなすことができる．

hook-content公式および定理5から，hook長公式を導く．
ヤング図形 $\lambda$ に上述の意味で組 $(P,\omega)$ が対応しているとする．
hook-content公式において $m$ (箱に入れる要素の上限)を $m\to\infty$ とすると以下を得る．
$\displaystyle\sum_{\sigma\in\mathcal{A}(P,\omega)}q^{|\sigma|}=\frac{q^{\sum_ii\lambda_i}}{\prod_{x\in P}(1-h_v)}$ .
定理5から
$\displaystyle\frac{1}{(q;q)_p}\sum_{w\in\mathcal{L}(P,\omega)}q^{{\rm maj}(w)}=\frac{q^{\sum_ii\lambda_i}}{\prod_{x\in P}(1-h_x)}$
つまり
（式３） $\displaystyle\sum_{w\in\mathcal{L}(P,\omega)}q^{{\rm maj}(w)}=\frac{q^{\sum_ii\lambda_i}(q;q)_p}{\prod_{x\in P}(1-h_x)}$
ここで， $\#\mathcal{L}(P,\omega)$ は $P$ のlinear extentionの数なので，（式３）で $q\to 1$ とすればhook長公式
$\displaystyle f^{\lambda}=\frac{n!}{\prod_{x\in P}h_x}$
が得られる．
（証明終わり）

上記の（式３）は，hook長公式の $q$ -類似と呼ばれるものである．

2025-08-08

一般化されたWorpitzkyの定理

$b_0,b_1,b_2\ldots$ を不定元とし ${\bf b}\triangleq(b_0,b_1,b_2,\ldots)$ とする．
一般化されたEulerian numberを
$\genfrac{\langle}{\rangle}{0pt}{0}{n}{k}_{{\bf b}}\triangleq(n-k+b_{n-1})\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k-1}_{{\bf b}}+(k+1-b_{n-1})\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k}_{{\bf b}}$ ,
$\genfrac{\langle}{\rangle}{0pt}{0}{0}{k}_{{\bf b}}\triangleq\delta_{k,0}$
により定義する．

例えば $\genfrac{\langle}{\rangle}{0pt}{0}{n}{k}_{{\bf b}}$ の値は $n,k$ が小さい時以下の通りである．

	k=0	k=1	k=2	k=3
n=0	$1$	0	0	0
n=1	$1-b_0$	$b_0$	0	0
n=2	$(1-b_0)(1-b_1)$	$-2b_0b_1+b_0+b_1+1$	$b_0b_1$	0
n=3	$(1-b_0)(1-b_1)(1-b_2)$	$3b_0b_1b_2-2b_0b_1$ $-2b_0b_2-2b_1b_2+4$	$-3b_0b_1b_2+b_0b_1$ $+b_0b_2+b_1b_2+b_0+b_1+b_2+1$	$b_0b_1b_2$

この一般化されたEulerian numberについて以下の一般化されたWorpitzkyの定理が成り立つ．

定理（一般化されたWorpitzkyの定理）
任意の非負整数 $n$ に対して以下が成り立つ．
$\displaystyle(x+b_0)(x+b_1)\cdots(x+b_{n-1})=\sum_{k=0}^n\genfrac{\langle}{\rangle}{0pt}{0}{n}{k}_{{\bf b}}\binom{x+k}{n}.$

証明
$n$ に関する帰納法による．
$\displaystyle\sum_{k=0}^n\genfrac{\langle}{\rangle}{0pt}{0}{n}{k}_{{\bf b}}\binom{x+k}{n}$
定義の漸化式を使うと
$\displaystyle=\sum_{k=1}^n(n-k+b_n)\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k-1}_{{\bf b}}\binom{x+k}{n}+\sum_{k=0}^{n-1}(k+1-b_n)\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k}_{{\bf b}}\binom{x+k}{n}$
$\displaystyle=\sum_{k=0}^{n-1}(n-k-1+b_n)\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k}_{{\bf b}}\binom{x+k+1}{n}+\sum_{k=0}^{n-1}(k+1-b_n)\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k}_{{\bf b}}\binom{x+k}{n}$
$\displaystyle=\sum_{k=0}^{n-1}\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k}_{{\bf b}}\frac{(x+k)_{n-1}}{n!}\left((n-k-1+b_n)(x+k+1)+(k+1-b_n)(x+k-n+1)\right)$
$\displaystyle=(x+b_{n-1})\sum_{k=0}^{n-1}\genfrac{\langle}{\rangle}{0pt}{0}{n-1}{k}\binom{x+k}{n-1}$
帰納法の仮定から
$\displaystyle=(x+b_0)(x+b_1)\cdots(x+b_{n-1}).$
（証明終わり）

${\bf b}=(0,0,0,\ldots)$ と特殊化すると，普通のWorpitzkyの定理に戻る．
系（普通のWorpitzkyの定理）
任意の非負整数 $n$ に対して以下が成り立つ．
$\displaystyle x^{n}=\sum_{k=0}^n\genfrac{\langle}{\rangle}{0pt}{0}{n}{k}_{{\bf 0}}\binom{x+k}{n}.$

2025-07-27

231-回避順列をDyck路に写すKnuthの全単射は順序同型である

大きさ $n$ の231-回避順列を $\sigma=\sigma_Ln\sigma_R$ と書いたとき，Knuthの全単射は $f(\sigma)\triangleq f(\sigma_L'){\mathsf U}f(\sigma_R'){\mathsf D}$ および $f(\varepsilon)\triangleq\varepsilon$ により帰納的に定義される．但し $\sigma_L',\sigma_R'$ はそれぞれ，語 $\sigma_L, \sigma_R$ のreduced form [1]である．

Knuthの全単射は，単に231-回避順列の集合 $\mathfrak{S}_n(231)$ からDyck路の集合 $\mathcal{D}_n$ への全単射であるだけでなく，集合 $\mathfrak{S}_n(231)$ にBruhat順序から誘導される順序を入れ，集合 $\mathcal{D}_n$ に「パスが上にある方が大きい」順序を入れると，その意味での順序同型になっている．

本稿ではこのことを示してみる．

イラスト

(左) $\mathfrak{S}_4(231)$ のHasse図．(右) $\mathcal{D}_4$ のHasse図 ([4]より引用)

$\mathfrak{S}_4(231)$ のHasse図と $\mathcal{D}_4$ のHasse図が同じ形になっている様子．

証明の方針

Knuthの全単射 $f$ を，231-回避順列からLukasiewicz路への全単射 $h$ と，Lukasiewicz路からDyck路への全単射 $d$ に $f=d\circ h$ と分解する．この分解はKrattenthaler [8]による．

Lukasiewicz路にも適切に順序構造を定め， $h$ が231-回避順列からLukasiewicz路への順序同型であり， $d$ がLukasiewicz路からDyck路への順序同型なことを示す．

以上により， $f=d\circ h$ が順序同型なことが示される．

定義

231-回避樹列 ( $\mathfrak{S}_n(231)$ )

231-回避順列の定義は [1], [2], [3]などを参照のこと．
サイズ $n$ の231-回避順列の集合を $\mathfrak{S}_n(231)$ とかく．

Dyck word ( $\mathcal{D}_n$ ), Subexcedent ( ${\rm SE}_n$ ), Lukasiewicz word ( $\mathcal{L}_n$ )

定義（Dyck word）
サイズ $n$ のDyck wordはアルファベット $\{ {\mathsf U}, {\mathsf D}\}$ からなる長さ $2n$ の語 $d=(d_1,\ldots,d_{2n})$ であって，

文字 ${\mathsf U},{\mathsf D}$ がそれぞれ $n$ 回現れる．
部分列 $(d_1,\ldots,d_k)$ に含まれる ${\mathsf D}$ の数は， ${\mathsf U}$ の数以下である．

を満たすものである．
サイズ $n$ のDyck wordの集合を $\mathcal{D}_n$ とかく．

定義（subexcedent）
サイズ $n$ のsubexcedentとは，アルファベット $\{0,\ldots,n-1\}$ よりなる長さ $n$ の語 $x=(x_1,\ldots,x_n)$ であって，すべての $i\ (1\leq i\leq n)$ に対して $x_i\lt i$ を満たすものである．
サイズ $n$ のSubexcedentの集合を ${\rm SE}_n$ とかく．

定義（Lukasiewicz word）
サイズ $n$ のLukasiewicz wordとは，サイズ $n$ のSubexcedentであって，すべての $i\ (1\leq i\lt n)$ に対して $x_{i+1}\leq x_{i}+1$ を満たすものである．
サイズ $n$ のLukasiewicz wordの集合を $\mathcal{L}_n$ とかく．

Lehmer code ( $h$ )

定義（Lehmer code）
与えられたサイズ $n$ の置換 $\sigma$ に対して $h_i\triangleq\#\{j\mid j\lt i\land \sigma(i)\gt\sigma(j)\}\ (1\leq i\leq n)$ と定め，
$h(\sigma)\triangleq(h_1,\ldots,h_n)$ と定める．
これにより定まる全単射 $h\colon\mathfrak{S}_n\to{\rm SE}_n$ をLehmer codeという [7]．

順序

定義（被覆の記号）
半順序集合 $P$ の元 $x,y$ について， $y$ が $x$ を被覆するとき， $x\lessdot y$ とかく．

定義（対称群のBruhat順序）[11]
置換 $\sigma,\tau$ に対して $\sigma\lessdot\tau$ とは，ある $i,j\ (1\leq i\lt j\leq n)$ に対して
$\tau=\sigma\cdot(i\ j)$ であり，かつ ${\rm inv}(\tau)={\rm inv}(\sigma)+1$ となることである．
この被覆関係により定まる $\mathfrak{S}_n$ の順序を (strong) Bruhat順序という．

対称群のBruhat順序の定義は以下のように言い換えることもできる．
定義（対称群のBruhat順序）
置換 $\sigma,\tau$ に対して $\sigma\lessdot\tau$ とは，ある $i,j\ (1\leq i\lt j\leq n)$ に対して
$\tau=\sigma\cdot(i\ j)$ であり，かつ $i\lt k\lt j\land \sigma(i)\lt\sigma(k)\lt\sigma(j)$ なる $k$ が存在しないことである．

定義（置換の順序）
置換の集合 $\mathfrak{S}_n$ にはBruhat順序を入れる．231-回避順列の集合 $\mathfrak{S}_n(231)$ には，Bruhat順序から誘導される順序を入れる．
誘導される順序 (induced order)の意味については [5]を見よ．

SubexcedentとLukasiewicz wordの順序
SubexcedentとLukasiewicz wordには $\{0,\ldots,n-1\}^n$ の直積順序から誘導される順序を入れる．
つまり，Subexcedent $p,q\in{\rm SE}_n$ に対して，被覆 $p\lessdot q$ を，ある $j\ (1\leq j\leq n)$ が存在して $q=p+e_j$ となることだと定める．但し $e_j\triangleq(\delta_{i,j})_{i=1}^n$ とする．Lukasiewicz wordに対しても同じである．

Dyck wordの順序
Dyck word $v,w\in\mathcal{D}_n$ に対して， $v\lessdot w$ とは，
$v$ に含まれる $\mathsf{DU}$ という部分列を $\mathsf{UD}$ に変えると $w$ が得られることである．
集合 $\mathcal{D}_n$ には，この被覆関係により定まる順序を入れる．
別の言い方をすると， $v\leq w$ とは，Dyck路 $v$ がDyck路 $w$ より完全に下にあるということである．
この順序はDyck路のdominance order [6]と呼ばれる．

$h$ と $d$ の全単射性

命題
Lehmer code $h$ は， $\mathfrak{S}_n(231)$ から $\mathcal{L}_n$ への全単射である．
証明
Krattenthaler [8]を見ればわかる．（証明終わり）

命題
Lukasiewicz word $p=(p_1,\ldots,p_n)$ に対して ${\mathsf U},{\mathsf D}$ からなる語 $d(p)$ を
$d(p)\triangleq ({\mathsf{U}{\mathsf D}^{p_1-p_2+1}})({\mathsf{U}{\mathsf D}^{p_2-p_3+1}})\cdots({\mathsf{U}{\mathsf D}^{p_n-p_{n+1}+1}})$
と定める．但し $p_{n+1}\triangleq 0$ とする．
すると， $d\colon\mathcal{L}_n\to\{{\mathsf U},{\mathsf D}\}^\ast$ は $\mathcal{L}_n$ から $\mathcal{D}_n$ への全単射である．
証明
Krattenthaler [8]でもわかるし，あるいはStanleyのCatalan numbers [9]とかに書いてある．（証明終わり）

本題

命題
$d\circ h\colon \mathfrak{S}_n(231)\to\mathcal{D}_n$ は順序同型である．

証明

以下のことを示す必要がある．

$h\colon\mathfrak{S}_n(231)\to\mathcal{L}_n$ は順序同型である．
$d\colon\mathcal{L}_n\to\mathcal{D}_n$ は順序同型である．

一般に，有限半順序集合 $P,Q$ の間の全単射 $f$ が順序同型であることを示すためには，任意の $x,y\in P$ に対して $x\lessdot y \iff f(x)\lessdot f(y)$ を示せばよい [10]．

まず， $h\colon\mathfrak{S}_n(231)\to\mathcal{L}_n$ が順序同型なことを示す．
補題1
231-回避順列 $\sigma,\tau$ は $\sigma\lessdot\tau$ かつ $\tau=\sigma\cdot(i\ j)\ (i\lt j)$ であるとする．このとき，

$k\lt i$ ならば $\sigma(k)\lt \sigma(i)$ または $\sigma(j)\lt \sigma(k)$ である．
$i\lt k\lt j$ ならば， $\sigma(k)\lt \sigma(i)$ である．

証明
1. について． $k\lt i$ かつ $\sigma(i)\lt\sigma(k)\lt\sigma(j)$ となる $k$ が存在すると， $\tau$ において $\tau(j)\lt\tau(k)\lt\tau(i)$ となり231のパターンができてしまうため．
2. について． $i\lt k\lt j$ とする． $\sigma(i)\lt\sigma(k)\lt\sigma(j)$ にはならないことは，対称群のBruhat順序の定義からわかる．また， $\sigma(j)\lt\sigma(k)$ にはならないことが $\tau$ が231-回避順列となるために必要である．よって， $\sigma(k)\lt\sigma(i)$ でなければならない．（証明終わり）

補題2
任意の置換 $\sigma, \tau\in\mathfrak{S}_n(231)$ に対して， $\sigma\lessdot\tau$ ならば $h(\sigma)\lessdot h(\tau)$ である．
証明
$\tau=\sigma\cdot(i\ j)\ (i\lt j)$ であるとして， $h_k(\tau)=h_k(\sigma)+\delta_{k,j}$ であることを示す．
$k\lt i$ および $j\lt k$ のとき $h_k(\sigma)=h_k(\tau)$ であることは， $\tau=\sigma\cdot(i\ j)$ であることからわかる．
$i\lt k\lt j$ のとき $h_k(\sigma)=h_k(\tau)$ であることは，補題1の2からわかる．
$k=i$ のとき $h_i(\sigma)=h_i(\tau)$ であることは，補題1の1からわかる．
$k=j$ のとき $h_j(\tau)=h_j(\sigma)+1$ であることは，補題1の1および補題1の2からわかる．（証明終わり）

補題3
任意のSubexcedent $p,q\in{\rm SE}_n$ に対して， $p\lessdot q$ ならば $h^{-1}(p)\lessdot h^{-1}(q)$ である．
(注：この補題は，Lukasiewicz wordにかぎらず任意のSubexcedentに対して成り立つ．)
証明
$h$ の逆写像の作り方は [7]に書かれているのでそれを使う．引用すると，Subexcedent $p\in{\rm SE}_n$ が与えられたとして，以下のように $\sigma=h^{-1}(p)$ を作る．まず $\sigma(n)\triangleq n-p_n$ とする． $\sigma(k+1)$ まで定めたとして， $\sigma(k)$ を集合 $\{1,\ldots,n\}\setminus\{\sigma(n),\sigma(n-1),\ldots,\sigma(k+1)\}$ において $p_k$ 番目に大きい要素とする (一番大きい要素は $0$ 番目とする)．以上により，置換 $h^{-1}(p)$ が定まる．
またLehmer code $h$ の基本的な性質として，置換の転倒数 ${\rm inv}$ に関して ${\rm inv}(\sigma)={\rm tot}(h(\sigma))$ が成り立つ．但し ${\rm tot}$ は，Subexcedentの要素の和である．
いま $q=p+e_j$ とする． ${\rm inv}(h^{-1}(q))={\rm inv}(h^{-1}(p))+1$ なので，示す必要があるのは $h^{-1}(q)=h^{-1}(p)\cdot(i'\ j')$ となる $i',j'$ が存在することである．
自然数 $j'$ については， $j'\triangleq j$ とする．自然数 $r$ を $(h^{-1}(p))(j)$ より小さく， $\{(h^{-1}(p))(j+1),\ldots,(h^{-1}(p))(n)\}$ に含まれない最大の数とし， $i'\triangleq (h^{-1}(p))^{-1}(r)$ とする．
この $(i',j')$ によって $h^{-1}(q)=h^{-1}(p)\cdot(i'\ j')$ となる．（証明終わり）

補題2, 3より $h\colon\mathfrak{S}_n(231)\to\mathcal{L}_n$ は順序同型である．
次に $d\colon\mathcal{L}_n\to\mathcal{D}_n$ が順序同型なことを示す．

補題4
任意のLukasiewicz word $p,q$ に対して $p\lessdot q$ ならば $d(p)\lessdot d(q)$ である．
証明
$q=p+e_j$ とする．このとき，
$d(p)=\cdots(\mathsf{U}\mathsf{D}^{p_{j-1}-p_j+1})(\mathsf{U}\mathsf{D}^{p_{j}-p_{j+1}+1})\cdots$
$=\cdots(\mathsf{U}\mathsf{D}^{p_{j-1}-p_j}\mathsf{D}\mathsf{U}\mathsf{D}^{p_{j}-p_{j+1}+1})\cdots$
$\lessdot\cdots(\mathsf{U}\mathsf{D}^{p_{j-1}-p_j}\mathsf{U}\mathsf{D}\mathsf{D}^{p_{j}-p_{j+1}+1})\cdots$
$=\cdots(\mathsf{U}\mathsf{D}^{p_{j-1}-p_j})(\mathsf{U}\mathsf{D}^{p_{j}-p_{j+1}+2})\cdots=d(q)$
（証明終わり）

補題5
任意のDyck word $v,w$ に対して $v\lessdot w$ ならば $d^{-1}(v)\lessdot d^{-1}(w)$ である．
証明
$v=(\mathsf{U}\mathsf{D}^{p^{(v)}_{1}-p^{(v)}_2+1})\cdots(\mathsf{U}\mathsf{D}^{p^{(v)}_{n}-p^{(v)}_{n+1}+1}),$
$w=(\mathsf{U}\mathsf{D}^{p^{(w)}_{1}-p^{(w)}_2+1})\cdots(\mathsf{U}\mathsf{D}^{p^{(w)}_{n}-p^{(w)}_{n+1}+1})$
となる $p^{(v)}_1,\ldots,p^{(v)}_n,p^{(w)}_1,\ldots,p^{(w)}_n$ が一意的に存在する．
いま $v$ に含まれる前から $j$ 番目 $\mathsf{U}$ について $\mathsf{DU}$ を $\mathsf{UD}$ に変えて $w$ ができるとする．
すると $p_j^{(w)}=p_j^{(v)}+\delta_{i,j}\ (i=1,\ldots,n)$ が成り立つ．
（証明終わり）

補題4, 5より， $d\colon\mathcal{L}_n\to\mathcal{D}_n$ は順序同型である．
（証明終わり）

参考文献

[1]
link.springer.com

[2]
en.wikipedia.org

[3]
combinatorics-fun.vercel.app

[4]
J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion. thesis at York University, 2008.
https://garsia.math.yorku.ca/~zabrocki/papers/DPfinal.pdf

[5]
en.wikipedia.org

[6]
A. Sapounakis, I. Tasoulas, P. Tsikouras, On the dominance partial ordering of Dyck paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.
https://cs.uwaterloo.ca/journals/JIS/VOL9/Tsikouras/tsikouras67.pdf

[7]
D. Foata, G.-H. Han, The $q$ -series in combinatorics: permutation statistics (Preliminary version), 2011.
https://irma.math.unistra.fr/~guoniu/papers/p56lectnotes2.pdf

[8]
pdf.sciencedirectassets.com

[9]
https://www.amazon.co.jp/Catalan-Numbers-Richard-P-Stanley/dp/1107075092www.cambridge.org

[10]
www.cambridge.org

[11]
StanleyのEnumerative Combinatoricsの3章の練習問題にBruhat順序の定義がある．
Amazon | Enumerative Combinatorics (Cambridge Studies in Advanced Mathematics, Series Number 49) | Stanley, Richard P. | Pure Mathematics

2025-07-10

Vandermondeに似た行列式

命題
任意の自然数 $m,n\ (m\leq n)$ に対して
$\displaystyle\det\left(\sum_{k=0}^{m-1}\alpha_kX_i^kY_j^{m-1-k}\right)_{i,j=1}^n=\alpha_0\alpha_1\cdots\alpha_{n-1}\prod_{1\leq i\lt j\leq n}(X_j-X_i)(Y_j-Y_i)\delta_{m,n}$
が成り立つ．
但し $\delta_{i,j}$ はクロネッカーのデルタである．

証明
$X_i=X_j\ (i\neq j)$ あるいは $Y_i=Y_j\ (i\neq j)$ とすると行列式が消えるので．左辺は
$\displaystyle\prod_{1\leq i\lt j\leq n}(X_j-X_i)(Y_i-Y_j)$
で割り切れる．

左辺は $n(m-1)$ 次の同次式なので， $m\lt n$ ならば，割り切れるためには ${\rm 左辺}=0$ である．
$m=n$ のとき，左辺は $c$ をある定数として
$c\times\displaystyle\prod_{1\leq i\lt j\leq n}(X_j-X_i)(Y_i-Y_j)$
という形をしている．両辺の
$(X_1Y_n)^{n-1}(X_2Y_{n-1})^{n-2}\cdots(X_{n-1}Y_2)^1$
の係数を比較すれば， $c=\alpha_0\alpha_1\cdots\alpha_{n-1}$ がわかる．
（証明終わり）

2025-05-20

(不動点の数-1)は対称群の既約指標

表現論置換

本記事で出てくる線形空間の係数体は $\mathbb{C}$ とする．
置換 $\pi\in\mathfrak{S}_n$ に対して $\pi$ の不動点の数を ${\rm fix}(\pi)$ とかく．

最近読んでいる表現論の本B. E. Sagan, The symmetric groupの1.9章に
$\chi^\perp(\pi)\triangleq{\rm fix}(\pi)-1$
で定義される関数 $\chi^\perp\colon\mathfrak{S}_n\to\mathbb{C}$ は $\mathfrak{S}_n$ の既約指標だと書いてあった．

1.9章では $\chi^\perp$ が指標であることの証明は書いてあるが，既約であることの証明は書いていない．
復習も兼ねてここで証明してみる．

指標なこと

まずは $\chi^\perp$ が対称群の指標であることを証明する．
命題
$n\geq 2$ のとき，上で定義した関数 $\chi^{\perp}$ は対称群 $\mathfrak{S}_n$ の指標である．
証明 (以下はSaganの1.9章に書いてある．)
線形空間 $\mathbb{C}\{{\bf 1},\ldots,{\bf n}\}\triangleq\{c_1{\bf 1}+\cdots+c_n{\bf n}\mid c_i\in \mathbb{C}\}$ 上の
対称群 $\mathfrak{S}_n$ 表現を
$\pi\cdot(c_1{\bf 1}+\cdots+c_n{\bf n})\triangleq c_1{\bf \pi(1)}+\cdots+c_n{\bf \pi(n)},\quad \forall \pi\in\mathfrak{S}_n$
と定める．
すると， $\mathbb{C}\{{\bf 1}+\cdots+{\bf n}\}\triangleq\{c({\bf 1}+\cdots+{\bf n})\mid c\in\mathbb{C}\}$ は部分表現である．

$\mathbb{C}\{{\bf 1},\ldots,{\bf n}\}$ の内積を $\langle{\bf i},{\bf j}\rangle\triangleq\delta_{i,j}\ (i,j\in \{1,\ldots,n\})$ と線形性により定める．
この内積は $\mathfrak{S}_n$ -不変，つまり $\langle\pi\cdot{\bf i},\pi\cdot{\bf j}\rangle=\langle{\bf i},{\bf j}\rangle\ (\pi\in\mathfrak{S}_n)$ である．
一般に $G$ を群とすると， $G$ -不変内積に関する部分表現の直交補空間は，再び部分表現になるのであった．(Saganの本の定理1.5.2)

よって， $\mathbb{C}\{{\bf 1}+\cdots+{\bf n}\}$ の直交補空間 $\mathbb{C}\{{\bf 1}+\cdots+{\bf n}\}^{\perp}$ は $n\geq 2$ のとき部分表現であり，
表現 $\mathbb{C}\{{\bf 1},\ldots,{\bf n}\}$ は
$\mathbb{C}\{{\bf 1},\ldots,{\bf n}\}=\mathbb{C}\{{\bf 1}+\cdots+{\bf n}\}\oplus\mathbb{C}\{{\bf 1}+\cdots+{\bf n}\}^{\perp}$
と二つの表現の直和に分解される．
表現 $\mathbb{C}\{{\bf 1},\ldots,{\bf n}\}, \mathbb{C}\{{\bf 1}+\cdots+{\bf n}\}, \mathbb{C}\{{\bf 1}+\cdots+{\bf n}\}^{\perp}$ の指標を
それぞれ
$\chi, \chi^{(1)}, \chi^\perp$
とかくと，
$\chi(\pi)={\rm fix}(\pi)$ ,
$\chi^{(1)}(\pi)=1$
なので $\chi^{\perp}(\pi)={\rm fix}(\pi)-1$ である．（証明終わり．）

既約なこと

有限群 $G$ 上の複素数値関数 $\chi,\psi\colon\mathfrak{S}_n\to\mathbb{C}$ に対して
$\displaystyle\langle\chi,\psi\rangle\triangleq\frac{1}{|G|}\sum_{g\in G}\chi(g)\overline{\psi(g)}$
とかく．（上で定義した内積とはまた違うので注意．）
指標 $\chi$ が $\langle\chi,\chi\rangle=1$ を満たすならば， $\chi$ は既約なのであった．
（このことは例えばSaganの定理1.9.4に書いてある．）

これを使って， $\chi^\perp$ が既約なことを証明する．
まずあとで使う補題を示す．

補題
以下が成り立つ．
(1) $\displaystyle\sum_{\pi\in\mathfrak{S}_n}{\rm fix}(\pi)=n!\quad(n\geq 1),$
(2) $\displaystyle\sum_{\pi\in\mathfrak{S}_n}\left({\rm fix}(\pi)\right)^2=2(n!)\quad(n\geq 2).$
証明
命題 $P$ に対して $\delta(P)$ を
$\displaystyle\delta(P)\triangleq\left\{\begin{array}{ll}1,\quad &P{\rm が真},\\0,&P{\rm が偽}\end{array}\right.$
とかく．
(1)
$\displaystyle\sum_{\pi\in\mathfrak{S}_n}{\rm fix}(\pi)=\sum_{\pi\in\mathfrak{S}_n}\sum_{i=1}^n\delta\left(\pi(i)=i\right)=\sum_{i=1}^n\sum_{\pi\in\mathfrak{S}_n}\delta\left(\pi(i)=i\right)=\sum_{i=1}^n(n-1)!=n!.$
(2)
$\displaystyle\sum_{\pi\in\mathfrak{S}_n}\left({\rm fix}(\pi)\right)^2=\sum_{i,j=1}^n\sum_{\pi\in\mathfrak{S}_n}\delta\left(\pi(i)=i\right)\delta\left(\pi(j)=j\right)$
$\displaystyle=\sum_{i=1}^n\sum_{\pi\in\mathfrak{S}_n}\delta\left(\pi(i)=i\right)+\sum_{1\leq i,j\leq n, i\neq j}\sum_{\pi\in\mathfrak{S}_n}\delta\left(\pi(i)=i\right)\delta\left(\pi(j)=j\right)$
$=n!+(n^2-n)(n-2)!=2(n!)$
（証明終わり．）

ちなみに，上の(1)はIMOの問題で出てたらしい．Art of Problem Solving
(2)は例えば
combinatorics - Fixed points of permutation groups - Mathematics Stack Exchange
に書いてある．

これを使って， $\chi^{\perp}$ が既約なことを示す．

命題
$n\geq 2$ のとき， $\chi^\perp(\pi)\triangleq{\rm fix}(\pi)-1$ は $\mathfrak{S}_n$ の既約指標である．
証明
$\displaystyle\langle\chi^\perp,\chi^\perp\rangle=\frac{1}{n!}\sum_{\pi\in\mathfrak{S}_n}\left(\chi^\perp(\pi)\right)^2$
$\displaystyle=\frac{1}{n!}\sum_{\pi\in\mathfrak{S}_n}\left({\rm fix}(\pi)-1\right)^2$
$\displaystyle=\frac{1}{n!}\left(\sum_{\pi\in\mathfrak{S}_n}\left({\rm fix}(\pi)\right)^2-2\sum_{\pi\in\mathfrak{S}_n}{\rm fix}(\pi)+\sum_{\pi\in\mathfrak{S}_n}1\right)$
$\displaystyle=\frac{1}{n!}\left(2(n!)-2(n!)+n!\right)=1$ （証明終わり．）

2025-01-28

一般化色付きLaguerre historyについて

全単射的証明母関数

この記事は組合せ論アドベントカレンダー2024の19日目です．
組合せ論 Advent Calendar 2024 - Adventar

微分方程式の初期値問題
$y'=f(y),\ y(0)=0$ （ $f$ は非負整数係数の形式的冪級数）の級数解の係数は，historyと呼ばれる組合せ論的オブジェクトの個数である．
本稿では，この話題について調べたことをまとめてみる．

背景を少し説明

例えば微分方程式の初期値問題 $y'=1+y^2,\ y(0)=0$ の解は
$\displaystyle y=t+\frac{1}{3}t^3+\frac{2}{15}t^5+\frac{17}{315}t^7+\frac{62}{2835}t^9+\cdots$
$\displaystyle\ =\frac{1}{1}t+\frac{2}{3!}t^3+\frac{16}{5!}t^5+\frac{272}{7!}t^7+\frac{7936}{9!}t^9+\cdots$
と書くことができ，これは数列 $(0,1,0,2,0,16,0,272,0,7936,\ldots)$ の指数型母関数である．

御存知の通りDyck路はステップ $(1,1)$ と $(1,-1)$ を通って $x$ 軸から出発して $x$ 軸へ戻って来る上半平面上のパスなのだが，
長さ $n$ の各Dyck路について，その各ステップにおける（高さ+1）をかけ合わせて足すと，先程の数列 $(1,0,2,0,16,0,272,\ldots)$ が現れることが知られている．（下図）
これは本記事で述べることの一つの例である．

また，微分方程式 $y'=1+2y+y^2,\ y(0)=0$ に対応するオブジェクトはViennotによりLaguerre historyという名前がつけられており [1]，
この記事の名前の由来になっている．

以下では，一般の微分方程式の初期値問題
$\displaystyle \frac{dy}{dt}=\sum_{i=0}^{\infty}c_iy^{i},\quad y(0)=0$
に対して，その級数解の係数がオブジェクトの個数となるような，パスっぽいオブジェクトを与える．

定義など

定義 (Łukasiewicz路)
長さ $n$ のŁukasiewicz路とは，ベクトル $(1,i)\ (i=-1,0,1,\ldots)$ を並べた長さ $n$ の列
$P=(p_1,p_2,\ldots,p_n)\quad p_i\in\{(1,k)\mid k=-1,0,1,2,\ldots\}$ で，

各部分和 $p_1+\cdots+p_k$ の $y$ 座標が非負（ $k=1,\ldots,n$ ）
総和 $p_1+\cdots+p_n$ の $y$ 座標が $0$

を満たすものである．

注：要するに，上がるときはいくら上がってもいいけど，下がるときは１づつしか下がれないパスである．

定義 (色付きŁukasiewicz路)
非負整数の列 ${\bf c}=(c_0,c_1,c_2,\ldots)$ が与えられたとき，長さ $n$ の ${\bf c}$ -色付きŁukasiewicz路とは，
長さ $n$ のŁukasiewicz路 $P=(p_1,p_2,\ldots,p_n)$ と， $P$ のステップから自然数への写像 ${\rm col}\colon\{1,2,\ldots,n\}\to\mathbb{N}$ の組であって，
$i=1,\ldots,n$ について「 $p_i = (1,k)$ ならば， $1\leq {\rm col}(i)\leq c_{k+1}$ 」を満たすものである．

注１：要するに，ステップ $(1,-1)$ が現れるたびに $c_0$ 色の中から一色を選んで塗る，ステップ $(1,0)$ が現れるたびに $c_1$ 色の中から一色を選んで塗る,...と決めて，Łukasiewiczの各ステップに色を塗ったものが ${\bf c}$ -色付きŁukasiewicz路である．
注２： ${\bf c}=(1,1,\ldots)$ のとき， $(1,1,\ldots)$ -色付きŁukasiewicz路は単なるŁukasiewicz路とみなすことができる．
注３：列 ${\bf c}$ において例えば $c_i=0$ と選ぶと， ${\bf c}$ -色付きŁukasiewicz路では，ステップ $(1,i-1)$ は使えないということである．

長さ $11$ の $(2,1,1,2,0,0,\ldots)$ -色付きŁukasiewicz路の例．ステップ $(1,-1)$ と $(1,2)$ は二色のうち一色で塗られている．

長さ $n$ のŁukasiewicz路 $P=(p_1,\ldots,p_n)$ の高さ列 ${\rm ht}(P)=({\rm ht}_0,\ldots,{\rm ht}_{n})$ を以下のように定義する．

${\rm ht}_0\triangleq 0$ とする．
$p_i=(1,k)$ とかくとき， ${\rm ht}_i\triangleq {\rm ht}_{i-1}+k$ とする． $(i=1,\ldots,n)$

定義(history)
長さ $n$ のŁukasiewicz路 $P$ に対して高さ列を ${\rm ht}(P)=({\rm ht}_0,\ldots,{\rm ht}_n)$ とする．
$P$ のhistoryとは，長さ $n+1$ の非負整数の列 $h=(h_0,\ldots,h_n)$ であって，
$h_i\leq {\rm ht}_i\ (i=0,\ldots,n)$ を満たすものである．

定義(色付きŁukasiewicz路のhistory)
長さ $n$ の ${\bf c}$ -色付きŁukasiewicz路のhistoryとは，
長さ $n$ の ${\bf c}$ -色付きŁukasiewicz路 $(P,{\rm col})$ と， $P$ のhistory $h$ の組 $(P,{\rm col},h)$ である．

長さ $11$ の $(2,1,1,2,0,0,\ldots)$ -色付きŁukasiewicz路のhistoryの例

長さ $n$ の ${\bf c}$ -色付きŁukasiewicz路のhistoryの集合を $\mathcal{H}_n({\bf c})$ とかく．

定理

定理１
$(c_0,c_1,c_2,\ldots)$ は非負整数列とする．常微分方程式の初期値問題
$\displaystyle \frac{dy}{dt}=\sum_{i=0}^{\infty}c_iy^{i},\quad y(0)=0$
の形式的冪級数による解を
$\displaystyle y(t)=\sum_{n=0}^\infty \frac{b_n}{n!}t^n$
とする．すると，
$b_{n+1}=c_{0}(\#\mathcal{H}_n(c_0,c_1,c_2,\ldots))$
である．

証明

以下の二段階で証明する．

微分方程式の解の係数が，colored increasing treeと呼ばれるオブジェクトの個数であることを示す．
colored increasing treeとhistoryの間に全単射を構成する．

ステップ１：微分方程式→木

まず，colored increasing treeを定義する必要がある．

定義 (increasing tree)
increasing treeとは，平面的（つまり子の間に順序のある）根付き木 $T$ と，その節点集合 $V(T)$ のラベル付け $\pi\colon v(T)\to \{1,2,\ldots,|V(T)|\}$ (全単射)の組 $(T,\pi)$ であって，節点 $u$ が節点 $v$ の子孫ならば， $\pi(u)\leq \pi(v)$ となるものである．

注：要するに，下に行くほどラベルが大きくなる根付き木である．

定義 (colored tree)
非負整数の列 ${\bf c}=(c_0,c_1,c_2,\ldots)$ が与えられたとき ${\bf c}$ -colored treeとは，
根付き木 $T$ と，節点集合から自然数の集合への写像 ${\rm col}\colon V(T)\to\mathbb{N}$ の組 $(T,{\rm col})$ であって，
各節点 $v\in V(T)$ に対して， $v$ の子供が $k$ 個ならば $1\leq {\rm col}(v)\leq c_k$ を満たすものである．

注：要するに，それぞれの葉を $c_0$ 色の中から一色を選んで塗り，子の数1の節点を $c_1$ 色の中から一色を選んで塗り,...という方法で節点に色を塗った根付き木である．

定義 (colored increasing tree)
非負整数の列 ${\bf c}$ に対して，組 $(T,{\rm col},\pi)$
但し $(T, {\rm col})$ は ${\bf c}$ -colored treeで， $(T,\pi)$ はincreasing treeであるものを
${\bf c}$ -colored increasing treeという．

節点数 $8$ の $(2,2,1,1,0,0,\ldots)$ -colored increasing treeの例．子の数 $0,1$ の節点は二色のうち一色で塗られている．

節点数 $n$ の ${\bf c}$ -colored increasing treeの集合を $\mathcal{T}_n({\bf c})$ とかく．
以下が知られている．

定理２
$(c_0,c_1,c_2,\ldots)$ は非負整数列とする．常微分方程式の初期値問題
$\displaystyle \frac{dy}{dt}=\sum_{i=0}^{\infty}c_iy^{i},\quad y(0)=0$
の形式的冪級数による解を
$\displaystyle y(t)=\sum_{n=0}^\infty \frac{b_n}{n!}t^n$
とする．すると，
$b_{n}=\#\mathcal{T}_n(c_0,c_1,c_2,\ldots)$
である．

定理２の証明は色んな場所に書いてあるし，かつ書くと長くなるので省略する．[2,3,4]
combinatorial speciesという概念を使うと示すことができる．

ステップ２：木→history

残る課題は， $c_{0}(\#\mathcal{H}_n(c_0,c_1,c_2,\ldots))= \#\mathcal{T}_{n+1}(c_0,c_1,c_2,\ldots)$ を示すことである．
全単射 $\{1,\ldots,c_{0}\}\times\mathcal{H}_n(c_0,c_1,c_2,\ldots)\to \mathcal{T}_{n+1}(c_0,c_1,c_2,\ldots)$ を構成する．

全単射は以下のアルゴリズムにより与えられる．
このアルゴリズムの ${\bf c}=(1,2,1,0,0,\ldots)$ の場合は[1]で与えられており，以下はそれを少し変えただけである．

アルゴリズム
入力：長さ $n$ の ${\bf c}$ -色付きŁukasiewicz路のhistory $(P=(p_1,\ldots,p_n), {\rm col}, h)$ ，自然数 $a\in\{1,\ldots,c_0\}$
出力：節点数 $n+1$ の ${\bf c}$ -colored increasing tree

$T:=($ "芽"という節点のみを持つ節点数 $1$ の根付き木 $)$ ;
for $i$ from $1$ to $n$ do
　　 $(x,y) := p_i$ ;
　　木 $T$ をpreorderでなぞり， $h_{i-1}$ 番目 (0番目から数え始める)に出会った芽を，「 $y+1$ 個の"芽"を子として持ち， $i$ というラベルがつけられた， ${\rm col}(i)$ 色の節点」に置き換える．
end for;
木 $T$ に唯一存在する芽を， $i+1$ というラベルがつけられた $a$ 色の節点に置き換える;
木 $T$ を出力する．