対角成分の一つ上まで非零要素が入っていてよいような行列をヘッセンベルグ行列という． 行列 をここでは「要素が全部1のヘッセンベルグ行列」と呼ぶ．（は命題の特性関数．）命題 は自然数とする． 行列の成分はカタラン数である．つまり が成り立つ． 証明…

二次元平面において点から出発し，ステップとを用いて点までゆくパスをサイズの両側Dyck路という． サイズの両側Dyck路の数はである．サイズの両側Dyck路のうち，最初のステップがであるものの集合をとする． である． 集合の両側Dyck路の例 次に「型数列」…

非負整数の集合をとかく． 1円玉，5円玉，10円玉を使って円をぴったり支払う方法の数とは，集合 の要素数である．以前の記事 (1円玉，5円玉，10円玉を使ってN円をぴったり支払う方法の数 - 数学の命題示しました) では，非負整数が，非負整数とを用いて とか…

１，概要 正方行列の固有多項式について，が成り立つ． これをCayley–Hamiltonの定理という．Cayley–Hamiltonの定理は線形代数のクラスの後半で習うのが普通であるが，実は線形代数の知識を用いずに証明できる． 具体的には，置換を用いた行列式の定義と行列…

概要 Stieltjes連分数を普通の分数で書いたときの式 において，多項式がライングラフのマッチング多項式であることを示す． 証明はFlajoletの補題に基づいてStieltjes連分数をDyck路の母関数とみて，適当な対合を作る方法で行う． 用語の準備 Stieltjes連分…

Combinatorial species (Combinatorial species - Wikipedia)は，離散オブジェクトの指数型母関数を扱うための現代的な手法である． 本稿ではspeciesの理論自体を説明することはしないが，大まかに言えばspeciesの理論は離散オブジェクトの組合せ論的な構造…

個の文字から重複を許して個とるとり方は 通りである．このことを二通りの方法で示す． 証明その１ 個の文字から重複を許して個とるとり方は， 個の (区別できない)ボールと個の (区別できない)仕切りを一列に並べる並べ方と一対一対応する． なぜならば，そ…

以下の命題の代数的証明と組合せ論的証明を紹介する．また，組合せ論的証明に基づいてパラメータを増やす拡張を行う．定理 自然数について が成立する．上式左辺は，添字が動く範囲がだということを表す． また右辺は，-解析の記号を使うとと書ける． 代数的…

記事概要 本記事では以下を組合せ論的に示す． 証明は対合を構成することで行う． 具体的には例えばのときはが成り立つ． 定義や準備など 調べたところ，第二種スターリング数の行列式を考えた研究には[1]がある． また，数学質問サイトStack exchangeには第…

命題 自然数に対して以下が成立する． . 証明 人の中から偶数人の参加者を選ぶ方法が通りであることを言えばよい． 参加者を次のように決める： 一人目，二人目,...,人目までは，参加／不参加を自由に決める． 最後の人目は参加者の合計が偶数になるように，…

前回の記事（第一種スターリング数の恒等式 Σc(n,k)2^k=(n+1)!の三通りの証明 - 数学の命題示しました）では、第一種スターリング数の恒等式 に二通りの全単射的証明をつけた。今回は、 Amazon | Proofs that Really Count: The Art of Combinatorial Proof …

追記：よりシンプルな証明を本で見つけたので、記事にしました。 iwalion.hatenablog.comツイッターで「スターリング数」で検索してみると、次のようなツイートを見かけた。第1種スターリング数（n個の数をkこの巡回列に分解する方法の場合の数）のこの性質…

自然数 について，以下の和を組合せ論的手法で求める． まず，和をの冪集合についての和に書き換える．とかくと さらに，この和を集合についての和に変えることができて， となる．のとき，からへの対合で，とすると， が成立するものを構成することができる…

第一種チェビシェフ多項式は，により定義される多項式であり， 漸化式 により定義することもできます． 第一種チェビシェフ多項式についてはこのブログでも以前話題に上げました． iwalion.hatenablog.com 第一種チェビシェフ多項式は「閉路グラフのマッチン…

カッコを正しく並べる方法が通りあることを全単射的に示します．

二項係数の不等式 を代数的方法、全単射的方法、非交差経路を使う方法により証明します。続きはpdfで。drive.google.com