組合せ・多項式・線形代数

概要

組合せ係数を入口に、包除による重複補正、約数格子・部分集合上のMöbius反転を続け、反射原理は別系統の直接数え上げ典型として学ぶ。反復合成と半環行列、線形方程式・XOR基底・分離可能変換を揃え、Prüfer符号・群作用・削除縮約・行列式・半順序で計数と構造定理を比較する。matroidの独立性と交換公理を中盤で学び、greedyによる最適化へ接続する。その後、母関数の係数解釈から畳み込み・Taylor shift・FPS・多点評価・有理母関数へ進む。発展的な係数抽出、onlineとsubsetの畳み込み、BEST定理、RSK、FPS合成を経て、rankと乱択を要する線形matroid交差を扱う。

組合せ・多項式・線形代数への変換

数え上げや遷移を係数列・多項式・線形写像へ変換する。

考え方

数える対象を一意に分解し、和・積・係数・線形写像として表す。組合せ式から生成関数へ、重複除去から反転へ、構造の存在からrankや交換公理へ進むことで、ABCの考察をさらに難しい問題へ再利用する。

成立条件と計算量

式の一致だけでなく、各項と数える対象の対応を示す。体や環、可逆な係数、収束ではなく形式的な演算という前提を確認する。高速な代数算法の費用には次数や精度を含める。

章の構成

項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。対象を係数・和・積へ翻訳し、数え方と高速な評価を分ける入口。

対象色の読み方は本書の読み方を参照してください。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-combinatorics-algebra

習得する技能

  • 数え上げや遷移を係数列・多項式・線形写像へ変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

数え上げを全単射・係数列・線形写像へ変換し、高速変換と構造定理へ接続する。

このUnitでは扱わないもの

  • なし

根拠