この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

代数的組合せ論の問題

難易度 3大学院入試の専門科目の標準レベル大学院数学代数的組合せ論

$0$ 以上の整数の分割 $λ = (λ_{1} \geq λ_{2} \geq \dots \geq λ_{ℓ} > 0)$ を考える（ $0$ の分割として空の分割 $λ = \emptyset$ も含め、 $∣ λ ∣ = λ_{1} + \dots + λ_{ℓ}$ とする）。部分の個数 $ℓ$ が $6$ 以下で、最大の部分 $λ_{1}$ が $8$ 以下であるような分割 $λ$ （すなわちヤング図形が $6 \times 8$ の長方形に収まる分割）全体を $B$ とする。 $B$ に属する分割 $λ$ のうち、 $∣ λ ∣$ が $4$ の倍数であるものの個数を求めよ。

この問題で使うもの

分割の統計量の母関数（説明と入口の問題）
分割数と分割の母関数（説明と入口の問題）
方程式 $z^{n} = a$ の解（説明と入口の問題）

この問題を解けるようになるまで（66 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

箱に収まる分割の母関数をガウスの二項係数で表し、1 の 4 乗根を代入して $4$ の倍数次の係数の和を取り出す。

ヒント 2

$\sum_{λ \in B} q^{∣ λ ∣} = [146]_{q}$ であり、求める個数は $\frac{1}{4} (F (1) + F (i) + F (- 1) + F (- i))$ 。 $F (ζ)$ は積表示で $0/0$ になる因子どうしの極限を考えて求める。

ヒント 3

$F (1) = (6 14) = 3003$ 、 $F (i) = F (- i) = 3$ となる。あとは $F (- 1)$ を、偶数次の因子の比 $\frac{( 1 - x ^{5} ) ( 1 - x ^{6} ) ( 1 - x ^{7} )}{( 1 - x ) ( 1 - x ^{2} ) ( 1 - x ^{3} )}$ の $x \to 1$ での値から求める。

答えと解説

答えを見る

761

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

母関数. $ℓ \leq n$ 、 $λ_{1} \leq m$ をみたす分割全体についての母関数は、ガウスの二項係数
$λ \sum q^{∣ λ ∣} = [m + n n]_{q} = j = 1 \prod n \frac{1 - q ^{m + j}}{1 - q ^{j}}$
で与えられる（ヤング図形の境界を $m$ 個の横の一歩と $n$ 個の縦の一歩からなる格子路とみなし、最後の一歩で場合分けすると漸化式 $[m + n n]_{q} = [m + n - 1 n - 1]_{q} + q^{n} [m + n - 1 n]_{q}$ が両辺で成り立つことから従う）。 $m = 8, n = 6$ として
$F (q) = λ \in B \sum q^{∣ λ ∣} = [146]_{q} = \frac{( 1 - q ^{9} ) ( 1 - q ^{10} ) \dots ( 1 - q ^{14} )}{( 1 - q ) ( 1 - q ^{2} ) \dots ( 1 - q ^{6} )} .$

1 の 4 乗根による係数抽出. $i$ を虚数単位とすると、求める個数 $N$ は
$N = \frac{1}{4} (F (1) + F (i) + F (- 1) + F (- i)) .$

$F (1)$ : $F (1) = (6 14) = 3003$ 。

$F (i)$ : 分子・分母のうち $q = i$ で $0$ になる因子は、指数が $4$ の倍数のもの、すなわち分子の $1 - q^{12}$ と分母の $1 - q^{4}$ だけである。 $x = q^{4}$ とおくと
$\frac{1 - q ^{12}}{1 - q ^{4}} = 1 + x + x^{2} \to 3 (q \to i) .$
残りの因子は、 $i^{9} = i, i^{10} = i^{2}, i^{11} = i^{3}, i^{13} = i^{5}, i^{14} = i^{6}$ より、分子 $(1 - q^{9}) (1 - q^{10}) (1 - q^{11}) (1 - q^{13}) (1 - q^{14})$ と分母 $(1 - q) (1 - q^{2}) (1 - q^{3}) (1 - q^{5}) (1 - q^{6})$ が $q = i$ で同じ値（ $0$ でない）をとるので、比は $1$ である。よって $F (i) = 3$ 。 $F$ は実数係数なので $F (- i) = F (i) = 3$ 。

$F (- 1)$ : $q = - 1$ で $0$ になるのは指数が偶数の因子で、 $x = q^{2}$ とおくと
$\frac{( 1 - q ^{10} ) ( 1 - q ^{12} ) ( 1 - q ^{14} )}{( 1 - q ^{2} ) ( 1 - q ^{4} ) ( 1 - q ^{6} )} = \frac{1 - x ^{5}}{1 - x} \cdot \frac{1 - x ^{6}}{1 - x ^{2}} \cdot \frac{1 - x ^{7}}{1 - x ^{3}} \to 5 \cdot 3 \cdot \frac{7}{3} = 35.$
残りの奇数次の因子は分子 $(1 - q^{9}) (1 - q^{11}) (1 - q^{13})$ 、分母 $(1 - q) (1 - q^{3}) (1 - q^{5})$ で、 $q = - 1$ でともに $2^{3} = 8$ なので比は $1$ 。よって $F (- 1) = 35$ 。

（これは $q$ -Lucas の定理 $[146]_{i} = (1 3) [22]_{i} = 3$ 、 $[146]_{- 1} = (3 7) = 35$ とも一致する。）

結論.
$N = \frac{1}{4} (3003 + 3 + 35 + 3) = \frac{3044}{4} = 761.$
（検算: 同様に $∣ λ ∣ \equiv 1, 2, 3 (mod 4)$ の個数は $742, 758, 742$ となり、合計 $761 + 742 + 758 + 742 = 3003$ と一致する。）

別解

$B$ の分割を $∣ λ ∣$ で数える母関数は、ガウス二項係数 $G (q) = (6 14)_{q}$ である。 $∣ λ ∣ \equiv 0 (mod 4)$ となる個数は、1 の 4 乗根による総和で求める。

$\frac{1}{4} j = 0 \sum 3 G (i^{j})$

各値は次のとおり。
- $G (1) = (6 14) = 3003$ 。
- $G (- 1)$ は $q$ -Lucas の定理（ $d = 2$ ）を使う。 $14 = 2 \cdot 7 + 0$ 、 $6 = 2 \cdot 3 + 0$ なので $G (- 1) = (3 7) = 35$ 。
- $G (\pm i)$ は $q$ -Lucas の定理（ $d = 4$ ）を使う。 $14 = 4 \cdot 3 + 2$ 、 $6 = 4 \cdot 1 + 2$ なので $G (\pm i) = (1 3) (2 2)_{\pm i} = 3 \cdot 1 = 3$ 。

よって個数は $(3003 + 35 + 3 + 3) /4 = 3044/4 = 761$ となり、整数になっている。

代数的組合せ論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題