離散数学・組合せ論の問題
集合 からそれ自身への全単射（置換） のうち、次の 2 つの条件をともに満たすものの個数を求めよ。
- すべての について
- すべての について
（たとえば 人の生徒 が席替えをするとき、生徒 が元の席 にも右隣の席 にも座らないような座り方の数に当たる。席 の右隣は考えない。）
この問題で使うもの
- 禁止位置のある順列とルーク多項式（説明と入口の問題）
- 一般の包除原理（説明と入口の問題）
- 組合せ（説明と入口の問題）
この問題を解けるようになるまで（11 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
置換を の盤へのルークの配置とみなし、禁止マス（対角線とそのすぐ右上）を使わない配置を包除原理で数える。
ヒント 2
互いに行も列も共有しない禁止マス 個の選び方を とすると、求める個数は 。禁止マスを と一列に並べると、衝突するのは隣り合うマスどうしだけである。
ヒント 3
一列に並んだ 個から隣り合わないように 個選ぶ方法は 通り。よって和は となる。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
置換 を の盤上の配置（第 行の第 列にルークを置く）とみなす。禁止されるマスは
の 個である。
包除原理. マス に対し、 を「 がマス を使う」置換の集合とする。求める個数は である。 の部分集合 （）について、 のマスどうしが行も列も共有しなければ、 のマスをすべて使う置換は残りの 行への割り当てで 個、行か列を共有する 2 マスを含めば 個である。よって、 から互いに行も列も共有しない 個のマスを選ぶ方法の数を とすると
の計算. のマスを
と一列に並べる。 と は同じ行、 と は同じ列にあり、この列で隣り合う 2 マスは衝突する。逆に、隣り合わない 2 マスは行も列も異なる（ と が同じ行になるのは 、同じ列になるのは のときだけで、どちらも隣り合う場合である）。したがって は「一列に並んだ 個から、どの 2 つも隣り合わないように 個選ぶ方法の数」であり、
計算.
- :
- :
- :
- :
- :
- :
- :
- :
よって
（確認：同じ方法で のとき となり、実際に条件を満たす置換は の 1 個だけである。）
答え：
別解
禁止される (行,列) の位置は () と () の計 13 個である。包除原理により、求める個数は となる。ここで は、禁止位置から同じ行にも同じ列にも入らないように 個選ぶ方法の数である。
、 とおく。 と は行 を共有し、 と は列 を共有する。それ以外の組は行も列も共有しない。したがって競合関係は という 13 頂点の道になる。 は、この道から隣り合わない頂点を 個選ぶ方法の数なので である。
。
個数
。
検算として、同じ方法を小さい場合に適用した。 では のみで 1 通りとなり、直接数えた結果と一致した。