母関数
1,概要 正方行列の固有多項式について,が成り立つ. これをCayley–Hamiltonの定理という.Cayley–Hamiltonの定理は線形代数のクラスの後半で習うのが普通であるが,実は線形代数の知識を用いずに証明できる. 具体的には,置換を用いた行列式の定義と行列…
幅長さの場所の上に,以下の二種類のタイル 幅長さのタイル 幅長さのタイル を右詰めで,個以上敷くことを考える. このような敷き方の集合をとかく. (記事下にの例があるのでそれも参照せよ.)をフィボナッチ数とすると,このような敷き方は 通りである…
概要 Stieltjes連分数を普通の分数で書いたときの式 において,多項式がライングラフのマッチング多項式であることを示す. 証明はFlajoletの補題に基づいてStieltjes連分数をDyck路の母関数とみて,適当な対合を作る方法で行う. 用語の準備 Stieltjes連分…
Combinatorial species (Combinatorial species - Wikipedia)は,離散オブジェクトの指数型母関数を扱うための現代的な手法である. 本稿ではspeciesの理論自体を説明することはしないが,大まかに言えばspeciesの理論は離散オブジェクトの組合せ論的な構造…
以下の命題の代数的証明と組合せ論的証明を紹介する.また,組合せ論的証明に基づいてパラメータを増やす拡張を行う.定理 自然数について が成立する.上式左辺は,添字が動く範囲がだということを表す. また右辺は,-解析の記号を使うとと書ける. 代数的…
置換をサイクル分解したとき現れるサイクルの数をサイクル数という.置換のサイクル数をとかく.この統計量について,次の式が知られいてる. (式 1) 但し,は形式的な変数であり,とする.(式 1)についてより詳しくは,Stanley (R. P. Stanley, Enumerative…
major indexとは置換の統計量つまり,対称群から非負整数への写像の一種である. major indexは,以前このブログでも紹介した「置換の転倒数」と等分布であることが知られている. つまり,以下の母関数の式が成立する.(式 (1)とする.) .(参考:R. P. S…
本稿では置換の転倒数の母関数が綺麗という側面から転倒数に触れていくが,転倒数という概念自体は行列式の性質を証明するために有用であったりとか (岩瀬順一,岩瀬順一の「授業をする際のヒント --- 数学編」,転倒数を利用し、互換の積への分解を飛ばして…
Viennot先生の講義動画で,組合せ論的オブジェクトを有限オートマトンへ全単射的に変換して,母関数を簡単に求める方法が紹介されていました. 動画では,道グラフのマッチング(その個数はフィボナッチ数)を状態数2の有限オートマトンに変換していました.…
第一種チェビシェフ多項式は,により定義される多項式であり, 漸化式 により定義することもできます. 第一種チェビシェフ多項式についてはこのブログでも以前話題に上げました. iwalion.hatenablog.com 第一種チェビシェフ多項式は「閉路グラフのマッチン…
みなさん御存知の通り, です.この式の導出は「」をからまで足すみたいなやつが有名です.(ググればたぶん一番上に出てきます.) だけど,二乗和を求めると言われたときに「」を使う発想に至るのは飛躍が大きい気がして個人的にあまり好きじゃないです.…
概要 の倍角公式 (第一種チェビシェフ多項式)を求める方法を四通り紹介します. は以下のようにの多項式として表せます. その具体的な式形をの倍角公式と呼ぶと思いますが,文脈によっては「第一種チェビシェフ多項式」と呼ぶこともあります.詳しい解説はW…
高校数学における場合の数や数列で練習を積んだおかげで、皆さんは有限個の何かを足し合わせることには慣れていると思います。 ところで、有限和を計算する場合はふつう有限の世界だけでの計算をする気がします。 有限のものを数える場合に、「有限=無限ー…
数Aの場合の数の問題で, 「正7角形の頂点を3つ結んで作れる互いに合同でない三角形は何種類ですか」 みたいなのがあります.これが正角形だとどうなるか調べてみます.参考 大阪府立高津高等学校の久世さんとバセダさんが,2010年に同じ研究をしていました…
1円玉,5円玉,10円玉を使って 円をぴったり支払う方法の数を研究します.同じことをやっている人は,ググった感じだと組み合わせの問題です。 -(1)1円、5円、10円の硬貨をとりまぜて合計- 数学 | 教えて!goo や 西三数学サークル通信44号 なんかがありま…
この記事では-二項係数を組合せ的に定義し,その値を求めます.非負整数 が与えられているとします. 長さ1の水平な線分と垂直な線分を使って作れる,点 から点 への最短路の個数は,二項係数を使って と表されます.図1はそのような最短路の例です.図1: 点…