形式的べき級数の逆元を使った無限和圧縮
形式的べき級数の逆元を使った無限和圧縮
多項式・形式的べき級数（２）式変形による解法の導出 | maspyのHPの一節を自分に理解できるところまで噛み砕いたもの
逆元
A = \sum_{n=0}^\infty x^n
B = 1-x
この時A \times B = 1が成り立つ
A = 1 + x + x^2 + \ldots (1)
xA = x + x^2 + \ldots (2)
(1-x)A = 1 (1) - (2)
等比数列の和の計算でよくやるテクニック
一般にFが[x^0]F = 0であるような定数項を持たない形式的べき級数の時、
(1-F) \times (\sum_{n=0}^\infty F^n) = 1
この証明には形式的べき級数環に位相を定義して、収束を定義する必要がある
【問題】Nを正の整数の和として表す方法を数え上げよ。ただし、和の順序の違いは区別する。
F = \sum_{n=1}^\infty x^n,G = \sum_{n=0}^\infty F^nとした時
[x^n]G が答え
Gの無限和を逆元で置き換える
G = \sum_{n=0}^\infty F^n = \frac{1}{1 - F}
Fの無限和も逆元で置き換える
F = \sum_{n=1}^\infty x^n = \sum_{n=0}^\infty x^{n+1} = x\sum_{n=0}^\infty x^n = \frac{x}{1-x}
FをGに代入する
G = \frac{1}{1 - F} = \frac{1}{1-\frac{x}{1-x}} = (1-x) \frac{1}{1-2x}
ここで2xの部分は形式的べき級数なので無限和に戻すことができる、これをJと呼ぶことにする
J = \frac{1}{1-2x} = \sum_{n=0}^\infty (2x)^n
[x^n]J = 2^n である
ここから[x^n] G = [x^n](1-x)J = [x^n]J - [x^{n-1}]J = 2^n - 2^{n-1} = 2^{n-1}
Related Pages
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →ホッケースティック恒等式×二項係数の公式×vandermondeの恒等式×巨大なnについての二項係数×形式的べき級数×ARC110D_FPS×oeis×重複組合せの畳み込み×arc110d_nonfps×arc110→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]