タカンゲーム

組合せ論という数学の分野において、タカンゲームは、マルセル・ポール・シュッツェンベルガー (1977) による構成であり、歪んだ標準ヤングの盤上の同値関係を定義します。タカンゲームスライドは、盤上の数字が15 のパズルのピースの動きと似た方法で移動する変換です。2 つの盤は、このようなスライドのシーケンスを介して一方が他方に変換できる場合、 タカンゲームと同等です。

「Jeu de taquin」（文字通り「からかいゲーム」）は、15 個のパズルのフランス語名です。

歪んだ形状 の歪んだ標準ヤングのタブローT が与えられたとき、歪んだ図に追加できる隣接する空のセルc を選びます。つまり、c はT内のセルと少なくとも 1 つの辺を共有し、歪んだ図でもあります。 c がTの左上にあるか右下にあるかによって、2 種類のスライドがあります。まず、 c が左上にあるとします。その隣接するセルからcに数字をスライドさせます。 cの右と下の両方に隣接するセルがある場合は、下の数字を優先して、これら 2 つの数字のうち小さい方を選びます (このルールは、行と列が増加するタブローの特性が保持されるように設計されています)。空になったばかりのセルの右または下に隣接するセルがない場合、スライドは完了します。それ以外の場合は、前と同じルールに従ってそのセルに数字をスライドさせ、スライドが完了するまでこの方法を続けます。この変換後、結果のタブロー (空になったセルは削除) は、依然として歪んだ (または直線の可能性がある) 標準的な Young タブローです。 ${\displaystyle \lambda /\mu}$${\displaystyle \lambda \setminus \mu }$${\displaystyle \{c\}\cup \lambda \setminus \mu }$

もう一方の種類のスライドは、c がTの右下にある場合、反対方向に進みます。この場合、左または上の隣のセルから空のセルに数字をスライドし、選択肢がある場合は常に大きい方の数字を選択します。2 種類のスライドは相互に逆であり、一方のスライドはもう一方のスライドを使用して元に戻すことができます。

上記の 2 つのスライドは、セルcへのスライドと呼ばれます。最初の種類のスライド ( c がTの左上にある場合) は内向きスライドと呼ばれ、2 番目の種類は外向きスライドと呼ばれます。

「slide」という単語はフランス語の「glissement」と同義であり、英語の文学でも時々使用されます。

ジュ・ド・タカン・スライドは、タブローのエントリの相対的な順序だけでなく、その形状も変更します。上記の定義では、ジュ・ド・タカン・スライドの結果は、歪んだ図と、それを形状とする歪んだ標準タブローとして与えられます。多くの場合、歪んだ図よりも歪んだ形状を扱う方が適しています。(すべての歪んだ形状から歪んだ図が生成されますが、たとえば、異なる歪んだ形状とは同じ歪んだ図を生成するため、これは単射対応ではないことを思い出してください。) このため、上記のジュ・ド・タカン・スライドの定義を変更して、歪んだ形状と歪んだ標準タブロー、および追加可能なセルを入力として与えられた場合に、出力で明確に定義された歪んだ形状と歪んだ標準タブローが生成されるようにすると便利です。これは次のように行われます:歪んだ形状の歪んだタブローTのセルcへの内側へのスライドは、 cが のコーナー(つまり、 がヤング図の場合) のときに上記のように定義され、結果として生じる歪んだ形状は に設定されます(ここで、dはスライド手順の終了時の空のセルです)。歪んだ形状の歪んだタブローTのセルcへの外側へのスライドは、 c がの共コーナー(つまり、 がヤング図の場合) のときに上記のように定義され、結果として生じる歪んだ形状は に設定されます(ここで、dはスライド手順の終了時の空のセルです)。 ${\displaystyle \lambda /\mu}$${\displaystyle \lambda \setminus \mu }$${\displaystyle (2,1)/(2)}$${\displaystyle (1,1)/(1)}$${\displaystyle \lambda /\mu}$${\displaystyle \mu}$${\displaystyle \mu \setminus \left\{c\right\}}$${\displaystyle (\lambda \setminus \left\{d\right\})/(\mu \setminus \left\{c\right\})}$${\displaystyle \lambda /\mu}$${\displaystyle \lambda}$${\displaystyle \lambda \cup \left\{c\right\}}$${\displaystyle (\lambda \cup \left\{c\right\})/(\mu \cup \left\{d\right\})}$

タカン スライドは、歪んだ半標準 (歪んだ標準とは対照的) のタブローに一般化され、その一般性においてその特性のほとんどを保持します。内向きスライドの定義を一般化するために行う必要がある唯一の変更は、(一時的に) 空のセルにその下と右に隣接するセルがあり、これらの隣接するセルに同じ数字が埋め込まれている場合の処理​​方法に関するルールです。この状況では、下の隣接するセル(右のセルではありません) を空のセルにスライドさせる必要があります。同様の変更が外向きスライドの定義 (上の隣接するセルを選択する必要があります) にも必要です。これらの変更は恣意的に見えるかもしれませんが、実際には「唯一の合理的な選択」を行うことを意味します。つまり、タブローの列 (空のセルは無視) が厳密に増加する (弱く増加するだけではない) 唯一の選択を行うということです。

歪んだ標準または歪んだ半標準のタブローTが与えられた場合、タブローが直線形状になるまで（つまり、これ以上の直線形状は不可能になるまで）、 Tに内側へのスライドを繰り返し適用することができます。これは通常、さまざまな方法で実行できます（最初にスライドするセルを自由に選択できます）が、結果として得られる直線形状のタブローは、すべての可能な選択に対して同じであることがわかっています。このタブローは、Tの修正と呼ばれます。

2 つの歪んだ半標準盤TとS は、スライドのシーケンス (内側スライドと外側スライドの両方が許可されます) (空の場合もあります) を使用して、一方を他方に変換できる場合、ジュ・ド・タカンと同等であると言われます。同様に、2 つの歪んだ半標準盤TとS は、同じ修正を持つ場合にのみ、ジュ・ド・タカンと同等です。

すべてのヤングの盤面に単語 (組合せ論の意味で、つまりアルファベットの要素の有限の列、ここでは正の整数の集合) を関連付けるには、さまざまな方法があります。ここでは、最も人気のある方法を選択します。つまり、すべてのヤングの盤面Tに、 Tの行を下の行から上の行まで連結して得られる単語を関連付けます。 ( Tの各行は、その項目を左から右に読むだけで単語として見なされます。また、ヤングの盤面を英語表記で描くときは、直線形状の盤面の最長の行が一番上に表示されるようにします。) この単語をTの読み単語、または簡単に単語と呼びます。

すると、2つの歪んだ半標準図表TとSがジュ・ド・タカン同値であるためには、TとSの読み言葉がクヌース同値であることが示されます。その結果、歪んだ半標準図表Tの修正は、ロビンソン-シェンステッド対応の下でTの読み言葉の挿入図表として得ることもできます。

タカンゲームは、任意の形状の標準的なヤングの盤面に対する操作を定義するために使用できます。この操作は反転になりますが、定義からは明らかではありません。まず、左上隅の正方形を空にして、盤面を正方形が 1 つ少ない斜めの盤面に変えます。次に、タカンゲーム スライドを適用して、斜めの盤面をまっすぐな盤面に変えます。これにより、外側の境界に 1 つの正方形が空きます。次に、この正方形を、左上隅で最初に削除された値の負の数で埋めます。この負の値は、元の盤面ではなく新しい盤面の一部と見なされ、後続の盤面でも位置は変わりません。元の盤面がエントリを保持している限り、左上隅のエントリx を削除し、元の盤面の残りの部分でタカンゲーム スライドを実行し、値 − x を解放した正方形に配置するという操作を繰り返します。元のタブローのすべてのエントリが処理されると、それらの負の値は行と列が増加するように配置されます。最後に、すべてのエントリに適切な定数を追加して、正のエントリを含む Young タブローを取得できます。

タカンゲームは、ロビンソン・シェンステッド・クヌース対応、リトルウッド・リチャードソン規則、クヌース同値などのトピックと密接に関連しています。

• Désarménien, J. (2001) [1994]、「Jeu de taquin」、Encyclopedia of Mathematics、EMS Press
• セーガン、ブルース E. (2001)、「対称群：表現、組み合わせアルゴリズム、対称関数」、Graduate Texts in Mathematics 203（第2版）、ニューヨーク：シュプリンガー、ISBN 0-387-95067-2
• フルトン、ウィリアム（1997）、Young Tableaux、ロンドン数学協会学生テキスト35（第1版）、メルボルン：ケンブリッジ大学出版局、ISBN 0-521-56144-2
• Haiman, MD (1992). 「プロクターの予想を含む双対同値性の応用」離散数学. 99 (1–3): 79–113. doi : 10.1016/0012-365X(92)90368-P .
• Schützenberger、Marcel-Paul (1977)、「La communicationance de Robinson」、Foata、Dominique (編)、Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS、Univ. Louis-Pasteur Strasbourg、Strasbourg、1976)、講演数学のノート、vol. 579、ベルリン: Springer、59–113 ページ、土井:10.1007/BFb0090012、ISBN 978-3-540-08143-2

• スタンレー、リチャード P. (1999)、列挙的組合せ論、ケンブリッジ高等数学研究 62、第 2 巻、ケンブリッジ大学出版局、ISBN 0-521-56069-1