MCスプラウト 数学 夏の学校「最長増加部分列の数学」

8月5日(月)、名古屋大学大学院多元数理科学研究科、岡田聡一教授に「最長増加部分列の数学」というテーマで講座をしていただき、中学生を含め56名が参加しました。

 最初に、順列の部分列、最長増加部分列を定義し、講義の前半のテーマ「順列が与えられたとき、その最長増加部分列の長さは?」、「順列が与えられたとき、その最長増加部分列を求めよ。」が、提示されました。これらを、4つのモデル「本の並べ替え」「カードゲーム(ペイシャンスソート)」「航空機への搭乗モデル」「粒子の生成・消滅モデル」を用いて教えていただきました。

 後半は、「最長増加部分列の長さの平均の挙動は?」という問に関連した話題でした。ある長さnの順列と、ヤング図形の挿入アルゴリズムによる挿入盤と記録盤のペアの間に1:1の対応(ロビンソン・シェークステッド・クヌース対応)が得られることを教えていただきました。ロビンソン・シェークステッド・クヌース対応が、最長増加部分列の長さの平均の挙動につながることを教えていただきました。