Day 083-Q5 — オイラー多項式・降下置換・第一種オイラー数（descent statistics・EGF）

2026-07-06 赤色 Master / Phase 8+ ★★★★★★★★★ Eulerian Number・descent・EGF + FPS

問題

長さ $N$ の置換 $\sigma \in S_N$ の降下数（descent number）を $\text{des}(\sigma) = |\{i : \sigma(i) > \sigma(i+1)\}|$ と定義する。

ちょうど $K$ 個の降下を持つ置換の個数 $A(N, K)$（第一種オイラー数）を全ての $K = 0, 1, \ldots, N-1$ について求めよ。さらに、ランダム置換の降下数の期待値を $\text{mod } 998244353$ で出力せよ。

制約

パラメータ範囲備考
$N$$1 \le N \le 3000$置換の長さ
出力形式mod 998244353大きな数は mod

入出力例

入力例1

4

出力例1

1 11 11 1
499122177

入力例2

3

出力例2

1 4 1
1

概念図: オイラー数の三角形と降下置換

オイラー数の三角形（Euler's Triangle） N\K 0 1 2 3 4 1 1 2 1 1 3 1 4 1 4 1 11 11 1 5 1 26 66 26 1 漸化式 A(N,K) = (K+1)·A(N-1,K) + (N-K)·A(N-1,K-1) 直感: N を置換 S_{N-1} に挿入 ・降下を維持する位置: K+1箇所 ・降下を1増やす位置: N-K箇所 N=3 の全置換と降下数: 123: des=0 132: des=1 (3>2) 213: des=1 (2>1) 231: des=1 (3>1) 312: des=1 (3>1,2>1) ←des=1のみ! 321: des=2 (3>2, 2>1) 期待値の公式 E[des(σ)] = Σ P[des at pos i] = (N-1) × 1/2 = (N-1)/2 理由: 各位置 i で σ(i)>σ(i+1) の確率 = 1/2 （対称性より）

ヒント

ヒント1（方向性）

第一種オイラー数 $\langle {N \atop K} \rangle$ の漸化式：$$\langle {N \atop K} \rangle = (K+1) \langle {N-1 \atop K} \rangle + (N-K) \langle {N-1 \atop K-1} \rangle$$基底: $\langle {0 \atop 0} \rangle = 1$（空置換には降下が 0 個）。直接 $O(N^2)$ で計算できる。

ヒント2（アプローチ）

$N \le 3000$ の制約なら漸化式の $O(N^2)$ が通る。期待値 $E[\text{des}(\sigma)] = (N-1)/2$ は各降下位置での対称性から直接導ける。modular inverse を使って $(N-1) \cdot 2^{-1} \pmod{p}$ を計算。

ヒント3（ほぼ答え） 
MOD = 998244353

def eulerian_numbers(N):
    prev = [0] * (N + 1)
    prev[0] = 1  # <0,0> = 1
    for n in range(1, N + 1):
        curr = [0] * (N + 1)
        for k in range(n):
            curr[k] = (k + 1) * prev[k] % MOD
            if k > 0:
                curr[k] = (curr[k] + (n - k) * prev[k - 1]) % MOD
        prev = curr
    return prev[:N]  # <N,0> ... <N,N-1>

# 期待値
inv2 = pow(2, MOD - 2, MOD)
expected = (N - 1) * inv2 % MOD

模範解答

import sys
input = sys.stdin.readline

def solve():
    MOD = 998244353
    N = int(input().strip())

    if N == 1:
        print(1)
        print(0)
        return

    prev = [0] * (N + 1)
    prev[0] = 1  # <0,0> = 1

    for n in range(1, N + 1):
        curr = [0] * (N + 1)
        for k in range(n):
            curr[k] = (k + 1) * prev[k] % MOD
            if k > 0:
                curr[k] = (curr[k] + (n - k) * prev[k - 1]) % MOD
        prev = curr

    eulerian = prev[:N]  # <N,0>, ..., <N,N-1>
    print(' '.join(map(str, eulerian)))

    # 期待値 E[des] = (N-1)/2
    inv2 = pow(2, MOD - 2, MOD)
    expected = (N - 1) * inv2 % MOD
    print(expected)

solve()

Step-by-Step 解説

Step 1: オイラー数の定義と直感

$A(N, K)$ = 長さ $N$ の置換でちょうど $K$ 個の降下を持つものの数。

NK=0K=1K=2K=3合計
11———1
211——2
3141—6
411111124

Step 2: 漸化式の導出

$N$ を置換 $\sigma \in S_{N-1}$ に挿入するとき、

  • 降下数を維持する（$K \to K$）位置: $K+1$ 箇所
  • 降下数を1増やす（$K-1 \to K$）位置: $N-K$ 箇所
for n in range(1, N + 1):
    curr = [0] * (N + 1)
    for k in range(n):
        curr[k] = (k + 1) * prev[k] % MOD      # K 維持
        if k > 0:
            curr[k] += (n - k) * prev[k - 1]   # K-1 → K
            curr[k] %= MOD
    prev = curr

Step 3: 期待値の計算

各降下位置 $i$（$1 \le i \le N-1$）について $\Pr[\sigma(i) > \sigma(i+1)] = 1/2$。したがって $E[\text{des}] = (N-1)/2$。

inv2 = pow(2, MOD - 2, MOD)  # フェルマー小定理
expected = (N - 1) * inv2 % MOD

よくあるミス

ミス原因正しい書き方
prev[k] を上書きしながら計算同じ配列を使いまわしcurr = [0]*(N+1) で新配列を作成
$K$ の範囲を $[0,N]$ にする$A(N,N) = 0$（N個の降下は不可能）出力は prev[:N]
期待値を $N/2$ と誤る降下位置は $1..N-1$ の $N-1$ 箇所$(N-1)/2$ が正しい
漸化式の係数を逆にする$(K+1)$ と $(N-K)$ の混同(k+1)*prev[k] と (n-k)*prev[k-1]

次のステップ

  • 発展問題: q-オイラー数 $\langle {N \atop K} \rangle_q$ を FPS で $O(N^2)$ より高速に計算せよ
  • 参考: Stanley "Enumerative Combinatorics" Vol. 1, Ch. 1.4

自己評価

理解度: / /

自分の回答:

気づき・メモ: