典型タグ

生成関数による組合せ構造の符号化

和・積・sequence・set・cycleなどの組合せ構成を係数列の演算へ翻訳し、欲しい個数を係数として抽出する。

この典型を扱う単元: 組合せを生成関数へ符号化する

検索別名: generating function、母関数、生成関数

未知問からこの典型を見つける手掛かり

扱う対象
  • OGF/EGF
  • 係数列
  • 組合せclass
使う手掛かり
  • 独立な合成
  • 連結成分へ分解
保つ不変量
  • sizeに対する係数
  • 全単射
求めるもの
  • 係数抽出
  • 数え上げ式
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: 組合せ・多項式・線形代数への変換

関連する典型

  • 畳み込み・相互相関: 組合せの合成を生成関数の積へ符号化し、その係数を畳み込みで計算する流れで併用する。

学習成果と学習単位

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。