Mathlogに活動の場を移しました.
数学趣味の人が記事を書いているMathlogというサイトがあります.
今後は,そちらに記事を書くことにしました.
mathlog.info
f-型数列の個数のリスト
-型数列と呼んでいるオブジェクトは,に入れるものを変えることにより,既存のいろんな数列を表すことができる.
にいろいろ入れてみて,出てきたものをリスト化しておく.
(「-型数列」は筆者の造語です.これを表す言葉がもうあるのを知ってる方は教えて頂けると幸いです.)
-型数列の定義
自然数の集合の部分集合の列
に対し,
(つまりが与えられているとし,)
数列であって,条件
- ,
を満たすものを,長さの-型数列という.
与えられたに対して,長さの-型数列の個数をとかく.
そして,数列を,-型数列の個数列という.
例:
のとき.(但し,)
長さの-型数列:1通り
長さの-型数列:1通り
長さの-型数列:の2通り
長さの-型数列:の5通り
...
-型数列の個数列はであり,それはカタラン数列であることが証明できる.
以下,与えたに応じて,-型数列の個数列のリストを作成した.
(中には予想も含まれるので注意.)
リストの見方
リストは三列からなる.
- 左の列は,
- 中央の列は,そのによってできる-型数列の個数列の名前や,オンライン数列大辞典へのリンク.
- 後ろの列は,筆者がその証明を知っているか,知らないかの区別を記している.「○」は筆者が証明を知っていることを表し,「X」は証明があってもそれを筆者が知らないか,または予想であることを表す.
なお,列によっては,の最初の数項だけが重要で,それ以降の項は-型数列の個数列に無関係な場合もある.その場合は,初項から必要な項までのみを記す.
リスト(最終更新日: 2023年02月02日)
自然数の部分集合の列 | -型数列の個数列 | 証明 |
○ | ||
, フィボナッチ数列 | ○ | |
○ | ||
フィボナッチ数列の偶数項 | X | |
母関数の数列.A052529 - OEIS | X | |
カタラン数 | ○ | |
○ | ||
母関数の数列.はカタラン数の母関数 | X | |
母関数の数列. | X | |
, A001764 - OEIS | X | |
X | ||
ある種の二分木の数, A002449 - OEIS | X | |
ある種の木, A000958 - OEIS | X | |
カタラン数の部分和, A014138 - OEIS | X | |
カタラン数の隣接項の和-1, | X | |
directed animalの個数, A005773 - OEIS | X |
要素が全部1のヘッセンベルグ行列のn乗の(1,1)成分はカタラン数
対角成分の一つ上まで非零要素が入っていてよいような行列をヘッセンベルグ行列という.
行列
命題
は自然数とする.
行列の成分はカタラン数である.つまり
が成り立つ.
証明
有向グラフをと
により定義すると,行列はグラフの隣接行列である.
よって,の成分はの節点から節点への,長さの歩道の数である.
ここで,グラフの全ての節点は節点1への枝を持つので,上記の歩道の数は節点を始点とする長さの歩道の数に等しい.
そのような歩道を,訪れた順に節点を並べることにより
という節点の列として表記する.
(である.また,歩道の長さがなので,この列の長さはなことに注意.)
するとグラフの作り方からが成り立つ.
例:長さの歩道は
の5通り.
このような列から「サイズのballot sequence」への全単射を構成する.
サイズのballot sequenceとは,個のと個のからなる長さの列で,すべての部分和が非負なものである.
サイズのballot sequenceの数はカタラン数であることが知られている.
(例えば [1]の問77を見よ.)
例:サイズのballot seqenceは
の5通り.
長さの歩道からサイズのballot sequenceへの全単射は以下のように作る.([1]の問80より.)
とする.
歩道の各を,に置き換える.
(は,個のを表す.)
例:
(証明終わり)
参考文献:
StanleyのCatalan numbers (2015)
www.amazon.com
両側Dyck路と(3,3,4,5,6,...)型数列の全単射
二次元平面において点から出発し,ステップとを用いて点までゆくパスをサイズの両側Dyck路という.
サイズの両側Dyck路の数はである.
サイズの両側Dyck路のうち,最初のステップがであるものの集合をとする.
である.
次に「型数列」を定義する.
写像が与えられているとする.
自然数の列で条件
- ,
- ならば,
を満たすものを,-型数列,あるいは型数列と呼ぶことにする.
サイズの型数列とは,長さの自然数の列
であって,以下の条件を満たすものである.
- ,
- のとき,.のとき,,
ただし.
サイズの型数列の集合をとする.
例えば,である.
本稿では以下を証明する.
命題
集合と集合の間に全単射が作れる.
またここから,がわかる.
この命題を証明するために,いくつか準備をする.
以下では集合の両側Dyck路をとかく.
このとき集合の定義からである.
両側Dyck路に対し自然数を以下のように定義する.
- のとき,,
- のとき,.
集合を
と定める.
補題
集合と集合の間に全単射が作れる.
証明
集合と集合の間の全単射を作る.
をとる.サイズの両側Dyck路を
- または,かつのとき
- かつのとき
と定める.
すると,上記でまたはを入れた場所は,
パスがという形のときは最初に現れる谷として,また
パスがそれ以外の形のときは最初に現れる頂上として同定可能である.
ゆえにを見ればが復元できるので対応は全単射である.
(証明終わり)
補題
とする.上記で定めた全単射について,
のとき, ,
のとき, ,
が成り立つ.
証明
のときとのときの両方について,
の場合に場合分けして確かめればわかる.
命題の証明
数列をとる.
上記補題により,あるとあるに対してならば,である.よって,
に対応するの元を
と定めることができる.
が可逆なのでこの対応は可逆である.
(証明終わり)
1円玉,5円玉,10円玉を使ってN円をぴったり支払う方法のq-母関数
非負整数の集合をとかく.
1円玉,5円玉,10円玉を使って円をぴったり支払う方法の数とは,集合
の要素数である.
以前の記事
(1円玉,5円玉,10円玉を使ってN円をぴったり支払う方法の数 - 数学の命題示しました)
では,非負整数が,非負整数とを用いて
とかけるとき,であることを示した.
本記事ではこの集合について単なる要素数より詳しい下式を証明する.
定理
は非負整数とし,とする.集合を
と定める.このとき
が成立する.
補足
右辺はには依存しない.
とすると,以前証明した式に戻る.
証明
まず,任意の非負整数に対して,との間には
という全単射がとれる.
だから,証明はに対して行えばよい.
第一象限の点の集合
を考える.これは
とかける.
また,第一象限の点の集合
も考える.
集合から集合への全単射
であって,
を満たすものを作れば証明が完了する.
以下,そのような全単射を作る.
の例で全単射を説明する.
集合と集合を図示すると以下の図 (上)のようになる.
集合から集合への全単射は図の (下)のように作る.
すなわち,集合において直線の上に乗っている点を、直線と平行に
適当な距離だけ北西へ移動させると,集合に一致させることができる。
この移動によって,の値は変わらない。
(証明終わり)
ケーリー・ハミルトンの定理の組合せ論的証明
1,概要
正方行列の固有多項式について,が成り立つ.
これをCayley–Hamiltonの定理という.
Cayley–Hamiltonの定理は線形代数のクラスの後半で習うのが普通であるが,実は線形代数の知識を用いずに証明できる.
具体的には,置換を用いた行列式の定義と行列の乗の定義から,組合せ論的考察により証明できる.
本記事で紹介する証明は,組合せ論的な視点から線形代数を再構成したBrualdi [1]の本からとったものである.
以下第2節ではまず準備として行列式や固有多項式を,組合せ論的オブジェクトの母関数として解釈する.
次に第3節で,行列の乗とグラフ上の歩道の対応を復習する.
最後に第4節で,上の二つを組み合わせてCayley–Hamiltonの定理を証明する.
2,行列式のHarary-Coater流の定義
以下で述べるように,行列式はグラフのサイクルの母関数として解釈できる.
この考え方はBrualdi [1]の第4章に詳しく,行列式のHarary-Coater流の定義と呼ばれる.
グラフ理論の用語の定義
有向グラフの部分グラフとは,節点集合と枝集合をもつ有向グラフである.
部分グラフの節点集合がもとのグラフの節点集合に等しいとき,つまりのとき,グラフを全域部分グラフという.
以下でははある体を表す。
有向グラフの枝重みとは,関数である.有向グラフと枝重みの組のことを,重み付き有向グラフという.
重み付き有向グラフの重みを,グラフの枝重みの積と定める.
有向グラフが2-正則であるとは,全ての節点の入次数と出次数が1であることである.
(これは一般的な言葉遣いとは違うかもしれない.)
2-正則であるような全域部分グラフのことを2-正則全域部分グラフという.
下図のように,2-正則全域部分グラフは有向グラフの全ての節点を,いくつかの交わりを持たないサイクルによって覆う方法であると思うこともできる.
次正方行列に対応する有向グラフとは,
節点集合と,枝集合をもつ有向グラフである.
有向グラフの枝重みを,枝に対してと定める.
次正方行列に対し,有向グラフの2-正則全域部分グラフの集合をとかく.
グラフに含まれるサイクルの数(連結成分の数と言い換えてもよい)をとかく.
下図はその例.
図中で枝重みを青色で書いている.
行列式のサイクル母関数としての表示
これらの用語を用いると,行列式は次のよう書ける.
証明の概略行列式を置換を用いて定義し,置換のサイクル分解を考える.
(証明終わり)
これについては,例を見るとより納得できるだろう.
上の図で登場した行列
である.
これは以下の図に示すとおり,の各要素について,その重みを足し合わせたものにひとしい.
固有多項式と,2-正則部分グラフ
次正方行列に対し,有向グラフの (全域でなくてもよい)2-正則部分グラフの集合をとかく.
有向グラフの節点のうち,部分グラフに含まれていないものの数を,とかく (isolated points,孤立点の意).
すると以下が成り立つ.
証明の概略まず定理1を用いて行列式を2-正則全域部分グラフの母関数として書く.
グラフに自己ループがあるとき,その自己ループしている枝の重みはであり,それを枝重みの自己ループとして残すか,重みの孤立点として扱うかを選ぶことができる.
(証明終わり)
例として,以下の行列を考える.
行列の固有多項式はである.
一方,グラフの2-正則部分グラフの重み和は下図の通り.
3,行列の乗と,グラフ上の歩道の対応
グラフの隣接行列を乗した行列の第成分は,グラフの節点から節点への長さの歩道の母関数である.
これはグラフ理論やマルコフ連鎖の理論でよく使う事実であるから,知っている人も多いと思う.
本節ではこの事実を復習する.
枝重み付き有向グラフの節点から節点への歩道とは,節点の列
であって,隣り合う節点,からへの枝がある,つまり
なるものである.
歩道の重みを,枝重みの積により
と定める.
歩道の長さを,列の要素数と定める.
節点から節点への歩道の集合をとかく.
すると以下が成り立つ.
次正方行列に対しの第成分は
と表せる.但し和は節点から節点への長さの全ての歩道にわたってとる.
4,Cayley–Hamiltonの定理の組合せ論的証明
Cayley–Hamiltonの定理
次正方行列に対しと定めると,
が成り立つ.
証明
まず定理2から,
である.
次にに行列を代入すると,
となる.
定理3から,行列の第成分は
である.
以下,やることは,対合を作ってを示すことである.
行列とに対して,ケーリーハミルトン配置の集合を以下のように定義する.
.
以下はケーリーハミルトン配置の例である.
言葉でいうと,ケーリーハミルトン配置とは,グラフ上のいくつかのサイクル(上図赤色)と,節点からへの歩道(上図青色)の重ね合わせであって,歩道の長さがサイクルに含まれないの節点の数(上図の例では4個)に等しいものである.
これを用いると,今考えている和はケーリーハミルトン配置にわたる和として
(★)
とかける.
式(★)が0であることを示すには以下のような対合を構成すればよい.
であって,
を満たすもの.
以下,そのような対合を構成する.
任意のケーリーハミルトン配置について,
歩道をとすると,以下の1, 2のどちらかが成り立つような最小の添字が存在する.
- 節点は,グラフのあるサイクルに含まれる.
- より小さい添字が存在して,である.つまり,歩道が節点を訪れるのは二度目である.
また,これらの二つが同時に成り立つことはない.
ここから,対合を次のように構成する.
1. が成り立つとき,節点を含むサイクルをグラフから消し,歩道に加える.
2. が成り立つとき,歩道の中のという部分を歩道から消し,サイクルとしてグラフに追加する.
図で書くと以下のようになる.
この対応は所望の対合である.
(証明終わり)
線分上に右詰めで並べる母関数の行列式表示
幅長さの場所の上に,以下の二種類のタイル
- 幅長さのタイル
- 幅長さのタイル
を右詰めで,個以上敷くことを考える.
このような敷き方の集合をとかく.
(記事下にの例があるのでそれも参照せよ.)
をフィボナッチ数とすると,このような敷き方は
通りである.ここではより精密に数える.
タイルを置く場所にの数直線を書き,
- ]の場所に置かれた長さのタイルの重みは,
- ]の場所に置かれた長さのタイルの重みは
とする.
タイルの敷き方の重みは,含まれるタイルの重みの積によって定める.
タイルの敷き方に対して,タイルの長さの和をとかく.
以下は,のときのタイルの敷き方とその重みの例.
この重みに関する母関数
は以下のような行列式表示を持つ.
(これは,のときの例.)
以下は,のときのこの主張の例.