この記事はCompetitive Programming Advent Calendarの26日目にあたる日に書かれましたし, 完結しているのでお疲れ様でした.
適当に吐き出しただけなので数学がガバガバだったり色々がガバガバだったり題材がガバガバだったり思いますゆるして
先日の忘年会でCODE FESTIVAL 2015 Okinawa FinalのG問題に関する話を聞きまして, まあ考えていたところ自分の人生にも照らしていろいろとつらくなったけど少しつらくなくなってきたので書きます
沖縄G
問題
上に1歩と右に1歩の移動ができるいつもの人がいるので, 図のような斜め45度の壁にぶつからずに黒から赤まで行く方法が何通りあるか求めてください.
実際の問題はもう一捻りあったようなのですが, 忘年会のときにはその一捻りの部分は省略した形で言われたのでとりあえずこれで
これが忘年会のときに話題になり, ちょっと考えたけどわからず, その後は和気あいあいと爆弾を解体して家に帰ったところ帰り道の途中で急に解けたのでまあ良かったのですが, すぐにわからなかったことや色々なことで結構凹んだので今回の記事を書きました.
下にネタバレがあるので改行をたくさんいれます
解答概要
赤いゴールを壁で何度も折り返して下の図のような赤や青の点をたくさん得ます.
黒から出発して赤か青のゴールに行く経路をとりあえず全部考えて, 「壁に最初にぶつかった点からあとを折り返す」ということを考えると, 「赤に行く経路のうち壁にぶつかるもの」と「青に行く経路 (自動的に壁にはぶつかる)」が1個ずつペアになるので, 結局(赤に行く経路の個数)-(青に行く経路の個数)が答え.
下図のような通常のカタラン数の数え上げは見たことがある人が多いと思います.
通常の時は壁が1枚しかないのですが, 赤いゴールとそれを壁で折り返した青いゴールを考えてさっきの"解答概要"と同じように赤い経路と青い経路をペアにすると壁にぶつからない経路が数え上げられるというやつです.
解答を見るとで折り返して符号をつけて足してるわけだし, そうなると通常のカタラン数は
だし, 他の鏡映群でも同じようなことができるんではとこの時は単にぼーっと考えてた
上で扱った問題は「壁が1枚のやつ」「壁が平行な2枚のやつ」でしたが, 同じような手法でパスの数え上げができる他のシチュエーションがあります.
hook公式
hook公式はたまにプログラミングコンテストで出てくることも多く*1, 数え上げが好きな競プロ勢にはよく知られていると思います. 中身はGoogleしてください. 今回は沖縄Gと絡めてhook公式の話をします.
hook公式は下のようなもの (Young標準盤) の個数を求める公式です. 字が汚いですが, 1~Nの数字が書かれていて行や列が単調増加になっています.
箱の並び方 (shapeと呼ばれます) を固定して標準盤の個数を知りたい, というのが問題です.
標準盤は下図のようにパスだと思うことができます. 例えば上の例なら, 1,2,3,4,5はそれぞれ1,1,2,3,2行目にあるので, 1,1,2,3,2の方向に1歩ずつ進んでいます. 図が汚いですが120度ずつのつもりです.
黒い線は「この線を超えて歩くと標準盤でなくなる」という線です. 黒い線を超えないパスを数えたいのですが, 灰色の壁に触れないパスと言っても同じことです.
(「shapeを固定して数える」というのは「終点 (と歩数) を固定して数える」に対応しています)
先と同じように, 壁でゴールをモリモリ折り返して, 壁にぶつかるような経路を反対の色のゴールに行くパスと対応させると, 壁にぶつからないパスの個数が(赤に行く経路の数)-(青に行く経路の数)で求まるはずです.
ゴールが上の図では6つありますが, これは3次対称群の元の数6=3!です.
より一般に行がk個あるshapeの標準盤を数えるなら壁はk-1枚になり, それらでゴールを折り返した結果k!個のゴールが現れることになります.
赤と青は置換の符号に対応しています.
赤や青のゴールに行く経路の個数は簡単な多項係数で求められ, 結果以下の行列式表示を得ます.
上の例ぐらいで具体的に計算してみるとわかりやすいと思います.
この行列式表示からhook公式を得るのはそれほど難しくありません*2([Sag]等).
この数え方絶対人生のどこかで目にしてるはずだと思うんですけど身に覚えがないので文献をゆるく募集します (というか一番そういう文献知らないといけないのは僕では (それはそう) )
他にもこの方針で語れることがありそうだしあって然るべきそうだけど思いつかない, 人間がダメ
まとめ
仮にも組合せ論的表現論が専門ですって言っておいてこれが即分からなかったのはどうなんだ組合せ論的表現論でもtableauxとかをいじらない人はいるけどそういう人じゃないでしょ
生きていると知らないことは色々あるので色々やっていくと良いと思います
[Sag]: B. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd edition, Springer, 2001.
