遺伝学・遺伝統計学関連の姉妹ブログ『ryamadaの遺伝学・遺伝統計学メモ』
京都大学大学院医学研究科ゲノム医学センター統計遺伝学分野のWiki
講義・スライド
医学生物学と数学とプログラミングの三重学習を狙う学習ツール
駆け足で読む○○シリーズ
ぱらぱらめくるシリーズ
カシオの計算機
オンライン整数列大辞典

ぱらぱらめくる『Noncrossing partitions』

Noncrossing partition 整数分割 分割 カタラン数 組み合わせ論 ポセット 代数的組み合わせ論

Introduction and Definitions, notation, and preliminaries

  • 整数分割
    • nの分割というとき、{1,2,...,n}をdisjointな部分集合に分割する、そのやり方の集合
    • 分割の記法：分割のグループ内では、要素を昇順に並べる。どのグループを先に書くかは、グループ内メンバーの中の最小値を代表値として取り出し、その順序で並べる
  • Noncrossing partitions
    • Noncrossing partitionssというとき、1,2,...,nを一列に並べて、分割して同じグループになったもの同士をトーナメント戦のようにフォークのようにつなぐこととした時に、フォークの線が交叉しないような分割のことを指す
    • 同様に1,2,3,...,nを円周上に並べて、同じグループのメンバー同士に線を引くことを考える。このときに線が交差しないようにできるようなグループ分けのことをNoncrossing partitionsという
    • この定義は「1 \le a < b < c < d \leのときに、a,cが同じグループで、b,dが同じグループだとしたら、a,b,c,dは全部同じグループであるような分割」と書かれる
    • このNoncrossing partitionsの場合の数がカタラン数になることが知られており、C_n=\frac{1}{n+1}\begin{pmatrix}2n \\ n \end{pmatrix}と計算される
  • (整数)分割の半順序・ポセット
    • 1/25/34/6/7 < 134/25/67 のような順序ルールを入れる。1,3,4が２グループに別れているか、１グループになっているかで、順序が入る。全てのグループで同じ方向の順序関係になっていれば、分割間でその順序関係があるものとする。グループごとに順序関係が入れ替わる場合は、分割としての順序関係は入れられないことにする。従って、半順序になる
    • 全要素を全て個別に分ける分け方は、分割のポセットの一番下になり、それを\hat {0}と書く。逆に全ての要素を全く分けないような分け方は、分割のポセットの一番上になり、それを\hat {1}と書く
    • このように上と下とが１点に閉じているポセットはlattice
    • 分割全体もlatticeであり、Noncrossing partitionsもlatticeである
    • Noncrossing partitionsは、各Noncrossing partitionのブロック数でグループ分けできて、そのn-ブロック数をランクという
    • ランクごとに幾つのNoncrossing partitionsがあるかの式も知られている
      • NC_n(k) := \#\{\pi \in NC_n: rank(\pi) = n-k \} = \frac{1}{n} \begin{pmatrix}n\\k \end{pmatrix} \begin{pmatrix} n\\ k-1 \end{pmatrix}
      • {1,2,...,n}のNoncrossing partitionsのうちブロックの数がkのものの数は、Noncrossing partitions集合の要素\piがrank(\pi) = n-kとかけるが、その数は、右辺で計算できる、と、読める
      • カタラン数C_nが、次のように和にできる、ということである。C_n = \sum_{k=1}^n NC_n(k) = \sum_{k=1}^n \frac{1}{n} \begin{pmatrix} n\\k \end{pmatrix} \begin{pmatrix} n\\ k-1 \end{pmatrix}
      • Rで確かめておく

    • メビウス関数とかもある
    • 全部でb個のブロックに分かれるとして、要素数i個のブロック数がm_iだとすると、\sum_{i=1}^n m_i=bが成り立ち、そのようなNoncrossing partitionsの場合の数にも式が知られていて\#NC_n(1^{m_1}2^{m_2},,,n^{m_n}) = \frac{n(n-1)(n-2)...(n-b+2)}{\prod_{i=1}^n m_i!}

Enumerative combinatorics

  • Exactな列挙、漸近列挙の両方について、色々な列挙問題があり、それについての知見がある
    • 文章・文法領域的な列挙問題がある
    • 幾何・経路とそれが作る面積に関する列挙問題がある
    • 制約付き成長パターン列挙問題がある
    • 直交多項式の組み合わせ列挙問題がある
    • 制約付き順列列挙としてのNoncrossing partitions列挙問題がある
    • Diagonal harmonicsというものと関係しているらしい。Diagonal harmonicsがなんなのかわからないのだが、何か大事そうな匂いはする

Connections with topology

この問題は現れる

  • Maps, Hypermaps
    • Fig5の説明をしてみる
    • 平面に２つのノードa, b がある
    • ノードa,bにはそれぞれ(1,2,3,4,5), (6,7,8,9,10)という整数が振られている。５つの数字を順番にぐるりと回って円ができるが、その円がノードだとみる。このとき、{1,2,3,4,5,6,7,8,9,10}のNoncrossing partitionsの一つとして(1,2,3,4,5)(6,7,8,9,10)があることがわかる。これを\sigmaというNoncrossing partitionとする。このNoncrossing partitionがノードa,bの存在と状態を表している。ノード上での数値の配置は時計回りとする
    • 今、この２つのノードa,bに複数のハイパーエッジがある、aから出てaに戻り、もう一度aから出てaに戻り、さらにもう一度aから出てaに戻るエッジ"aaa"、aから出てaに戻りaから出てbへ渡りbから出てbに戻りbから出てbに戻りaに戻ってくる。これを"aabbb"と書く。同様に"bb"。ハイパーエッジでは、数値をたどるサイクルの回り方は反時計回りとする。これもNoncrossing partitionになっていて、(1,2,3)(4,5,8,9,10)(6,7)と表せる。これを\alphaとする
    • このとき、もう一つNoncrossig partitionが構成されていて、それは「面、face」を表しているという。今、ハイパーエッジをサイクルとして描図した時に、あるエッジが i->jと引けていたとする。このとき、iからスタートしてjの方向にはいけるけれど、jはそのエッジの「反対側〜向こう側」にあって、たどり着けないとする。エッジi->j自体をたどるならたどり着けるのだが、今は、エッジが分割した「残りの領域・面」の部分だけを歩くことが許されている、と考えれば良いだろうか。ノード上の数値を辿っているサイクルの方も同様で、1->2->...とたどるが、1から出発すると、2にはたどり着けない。そんな風にして、たどり着ける数値を、ノードのサイクルについては時計回りに、エッジのサイクルについては反時計回りにたどることを許すと、(1)(2)(3,10,7,5)(4)(6)(8)(9)なるNoncrossing partitionが現れる。これを\alpha^{-1}\sigmaと書く。おそらく、時計回り、反時計回りの区別がインバース表記に対応するのだろう
    • 結局、平面上に実現されたハイパーマップにて、ノード、エッジ、フェイスがNoncrossing partitionsで表現されることとなった

f:id:ryamada:20190327063327j:plain
hypergraph-noncrossing partition

    • ここで、ノード的サイクル数　＋エッジ的サイクル数　＋フェイス的サイクル数＝N+2-2g、ただしgはgenusナンバーと成っている
    • これは、#Nodes - #Edges + #Faces = 2-2g というオイラーの式の一般化になっている。一般的な平面グラフでは、Noncrossing partition的な意味ので総ノード数N = 2 * エッジ系のサイクル数。なぜなら、普通のグラフでは、エッジは２端点のみを持っていて、それらをすべて別個に数え上げるのが、Noncrossing partition的ハイパーグラフ表現になっているから、#Nodes - #Edges + #Faces = 2-2gの両辺にNを加えると、#Nodes + #Edges + #Faces = N + 2-2gとなる
  • さらに、グラフの色塗り問題への代数的・多項式的アプローチにも使われ
  • ふたつのnoncrossig partitions的ペアリングを張り合わせるとNoncrossing サイクルが現れるとかにも応用される
  • どちらも、行列式とかを使った表現がある

Relations with geometric combinatorics

  • Convex polytope, hyperplane arrangement, reflection groupとかに応用される

Relations with algebra

  • 応用範囲が広いので、その(抽象)代数が展開されれば扱いやすいし、その方面での知見もある

Further examples

  • RNAの二次構造の場合わけとかに使える