数学の命題示しました

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

対称群から「固定点1個以下の対合の集合」✕「self-reverse-complementな置換の集合」への全単射

置換 全単射的証明

置換 \sigma\in\mathfrak{S}_n に対して，そのreverse \sigma^{\mathsf r} とは \sigma^{\mathsf r}(i)\triangleq\sigma(n+1-i) で定義される置換であり，そのcomplement \sigma^{\mathsf c} とは \sigma^{\mathsf c}(i)\triangleq n+1-\sigma(i) で定義される置換である．置換 \sigma が \sigma=\sigma^{\mathsf{rc}} を満たすとき，self-reverse-complementであるという．置換 \sigma が \sigma^2=\mathrm{id} を満たすとき対合であるという．但し \mathrm{id} は恒等置換を表す．数 i\in\{1,\ldots,n\} が \sigma(i)=i を満たすとき， i は \sigma の固定点であるという．置換 \sigma の固定点の数を \mathrm{fix}(\sigma) とかく．

対称群 \mathfrak{S}_n の部分集合で，固定点1個以下の対合の集合を \mathcal{M}_n\triangleq\{\sigma\in\mathfrak{S}_n\mid\sigma^2=\mathrm{id},\ \mathrm{fix}(\sigma)\leq1\} とし，self-reverse-complementな置換の集合を B_n\triangleq\{\sigma\in\mathfrak{S}_n\mid\sigma^{\mathsf{rc}}=\sigma\} とかく．本稿では，全単射 \mathfrak{S}_n\to\mathcal{M}_n\times B_n を構成する．全単射はまず代数的に構成し，同じ全単射を組合せ論的にも構成する．

全単射の代数的構成

群の一般論を使って全単射を構成する．群 G を考える．元 x\in G に対して C(x)\triangleq\{g^{-1}xg\mid g\in G\} を x の共役類という．元 x,y\in G に対して T(x,y)\triangleq\{g\in G\mid g^{-1}xg=y\} と定める．特に T(x,x) は x の中心化群と呼ばれ， G の部分群となる．

命題1

G を有限群とし， x\in G とする．全単射 G\to C(x)\times T(x,x) が構成される．

構成． 各 y\in C(x) に対して定義から T(x,y)\neq\emptyset である．各 y\in C(x) に対して T(x,y) から元を一つ選び，それを \alpha_y とかく．写像 G\ni g\mapsto(g^{-1}xg,g\alpha_{g^{-1}xg}^{-1})\in C(x)\times T(x,x) は全単射である．

まずwell-definedなことを確かめる． z=g^{-1}xg とかく． (g\alpha_z^{-1})^{-1}x(g\alpha_z^{-1})=\alpha_zg^{-1}xg\alpha_z^{-1}=\alpha_zz\alpha_z^{-1}=x なので g\alpha_z^{-1}\in T(x,x) ．よってこの写像はwell-definedである．写像 C(x)\times T(x,x)\ni(y,h)\mapsto h\alpha_y\in G が逆写像となるから，全単射である．（構成終わり）

命題1の全単射の構成では各 y\in C(x) に対して \alpha_y\in T(x,y) を選ぶ部分に恣意性があるため，命題1で構成した全単射は一意的に定まるわけではない．

系2

全単射 \Phi\colon\mathfrak{S}_n\to\mathcal{M}_n\times B_n が構成される．

構成． 命題1における群 G を対称群 \mathfrak{S}_n とし，元 x\in G を x=\mathrm{id}^{\mathsf r}\in\mathfrak{S}_n とする．以降 w_0\triangleq\mathrm{id}^{\mathsf r} とかく． y\in C(w_0) に対して \alpha_y\triangleq\min T(w_0,y) と選ぶことにする．但し \min は，置換をワード表記したときの辞書式順序での最小を意味する．すると，命題1より， \Phi\colon\mathfrak{S}_n\ni\sigma\mapsto(\sigma^{-1}w_0\sigma,\sigma\alpha_{\sigma^{-1}w_0\sigma}^{-1})\in C(w_0)\times T(w_0,w_0) は全単射である．

集合 C(w_0) は，置換 w_0 とサイクルタイプが同じであるような置換の集合なので， C(w_0)=\mathcal{M}_n である．集合 T(w_0,w_0) は関係式 \sigma w_0=w_0\sigma を満たす置換 \sigma\in\mathfrak{S}_n の集合であり， w_0\sigma(i)=n+1-\sigma(i) ， \sigma w_0(i)=\sigma(n+1-i) より \sigma(i)=n+1-\sigma(n+1-i)=\sigma^{\mathsf{rc}}(i) ．よって T(w_0,w_0)=B_n ．（構成終わり）

全単射の組合せ論的構成

系2で構成した全単射 \Phi\colon\mathfrak{S}_n\to\mathcal{M}_n\times B_n は組合せ論的に構成することもできる．集合 \mathcal{M}_n は n が偶数のとき文字 1,\ldots,n を二つずつ組にしたマッチング， n が奇数のときは一文字だけ組にできない仲間はずれが残る部分的なマッチングと見なすことができる．集合 B_n の要素は b_1\cdots b_n とワード表記したとき，前半の \lfloor n/2\rfloor 個を定めれば一意的に定まる．以下で全単射 \Phi'\colon\mathfrak{S}_n\to\mathcal{M}_n\times B_n を構成する．以下では i\in\{1,\ldots,n\} に対して \overline{i}\triangleq n+1-i と定める．

構成（系2の別証）

置換 \sigma\in\mathfrak{S}_n のワード表記を w_1\cdots w_n とする．このワード表記において，各 i\in\{1,\ldots,\lfloor n/2\rfloor\} に対して文字 i と \overline{i} の間に弧を描く．こうして描かれる \lfloor n/2\rfloor 本の弧の組は \mathcal{M}_n の元とみなすことができる．これらの弧が結ぶ二つの文字 i,\overline{i} のうち， \sigma のワード表記において左側にあるものをオープナーと呼ぶ． \sigma のワード表記を左から右に読みオープナー \lfloor n/2\rfloor 個を順に集めれば， B_n の元を得る．この対応 \Phi'\colon\mathfrak{S}_n\to\mathcal{M}_n\times B_n は全単射である．（構成終わり）

命題3

代数的に定義した写像 \Phi と，組合せ論的に定義した写像 \Phi' は同じ写像である．

証明． 置換 \sigma\in\mathfrak{S}_n に対して \Phi(\sigma)=(m,b),\ \Phi'(\sigma)=(m',b') とする．まず m=m' を示す． i\in\{1,\ldots,n\} に対して m'(i) は \sigma のワード表記を w_1\cdots w_n とすると w_j=\overline{w_i} となる j であり，それは \sigma^{-1}(\overline{\sigma(i)})=\sigma^{-1}w_0\sigma(i)=m(i) である．

次に b=b' を示す．以下，この証明の中でのみ \alpha_{\sigma^{-1}w_0\sigma} を \alpha と略記し， k=\lfloor n/2\rfloor とする．置換 \sigma のオープナーを左から順に o_1,\ldots,o_k とする．示すべきことは \sigma\alpha^{-1}(i)=o_i\quad(i\in\{1,\ldots,k\}) である．置換 \sigma のオープナーの位置を左から順に p_1,\ldots,p_k とする．すなわち \sigma(p_i)=o_i\quad(i\in\{1,\ldots,k\}) とする．

集合 T(w_0,\sigma^{-1}w_0\sigma) は \sigma とマッチング構造が同じ置換全体の集合である．すなわち置換 \tau が \tau\in T(w_0,\sigma^{-1}w_0\sigma) を満たすならば，かつそのときに限り，任意の i,j\in\{1,\ldots,n\} に対して \overline{\tau(i)}=\tau(j)\iff\overline{\sigma(i)}=\sigma(j) が成り立つ．このことは， \tau\in T(w_0,\sigma^{-1}w_0\sigma) かつ \overline{\sigma(i)}=\sigma(j) ならば， \overline{\tau(i)}=\overline{w_0\tau\sigma^{-1}w_0\sigma(i)}=\tau\sigma^{-1}w_0\sigma(i)=\tau\sigma^{-1}\bigl(\overline{\sigma(i)}\bigr)=\tau\sigma^{-1}\sigma(j)=\tau(j) が成り立つことから分かる．よって \alpha の最小性から \alpha(p_i)=i である．よって p_i=\alpha^{-1}(i) であり， \sigma(p_i)=o_i=\sigma\alpha^{-1}(i) である．（証明終わり）

補足

補足1

集合\mathcal{M}_nの濃度は|\mathcal{M}_n|=\prod_{i\in\{1,\ldots,n\},\ i\colon{\rm odd}}iであり，集合B_nの濃度は|B_n|=\prod_{i\in\{1,\ldots,n\},\ i\colon{\rm even}}i
なので，これらを合わせて対称群の濃度は|\mathfrak{S}_n|=|\mathcal{M}_n||B_n|=n!であることがわかる．

補足2

本稿で定義した集合B_nは通常の置換の積によって群をなし，それはB_{\lfloor n/2\rfloor}型Weyl群（超八面体群）と同型である．

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

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をつけたものであるかのいずれかである，ということである．
（証明終わり）

ヤング図形の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

概要

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

\lambda=(4,3,3)のヤング図形

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

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

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

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

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

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

(a)標準盤の例．(b)半標準盤の例．

ヤング図形を任意に固定したときの標準盤の個数には下記の積公式が知られていて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が成り立つ．

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

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

  1. i\leq j\Rightarrow\sigma f^{-1}(i)\geq \sigma f^{-1}(j),
  2. 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)なので

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

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

  1. （式１） f(x)< f(y)\Leftarrow\sigma(x)> \sigma(y),
  2. （式２） 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-類似と呼ばれるものである．

一般化された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}.

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)であるとする．このとき，

  1. k\lt iならば \sigma(k)\lt \sigma(i)または \sigma(j)\lt \sigma(k)である．
  2. 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

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}がわかる．
（証明終わり）

(不動点の数-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（証明終わり．）