数学趣味の人が記事を書いているMathlogというサイトがあります. 今後は,そちらに記事を書くことにしました. mathlog.info
-型数列と呼んでいるオブジェクトは,に入れるものを変えることにより,既存のいろんな数列を表すことができる. にいろいろ入れてみて,出てきたものをリスト化しておく. (「-型数列」は筆者の造語です.これを表す言葉がもうあるのを知ってる方は教えて…
対角成分の一つ上まで非零要素が入っていてよいような行列をヘッセンベルグ行列という. 行列 をここでは「要素が全部1のヘッセンベルグ行列」と呼ぶ.(は命題の特性関数.)命題 は自然数とする. 行列の成分はカタラン数である.つまり が成り立つ. 証明…
二次元平面において点から出発し,ステップとを用いて点までゆくパスをサイズの両側Dyck路という. サイズの両側Dyck路の数はである.サイズの両側Dyck路のうち,最初のステップがであるものの集合をとする. である. 集合の両側Dyck路の例 次に「型数列」…
非負整数の集合をとかく. 1円玉,5円玉,10円玉を使って円をぴったり支払う方法の数とは,集合 の要素数である.以前の記事 (1円玉,5円玉,10円玉を使ってN円をぴったり支払う方法の数 - 数学の命題示しました) では,非負整数が,非負整数とを用いて とか…
1,概要 正方行列の固有多項式について,が成り立つ. これをCayley–Hamiltonの定理という.Cayley–Hamiltonの定理は線形代数のクラスの後半で習うのが普通であるが,実は線形代数の知識を用いずに証明できる. 具体的には,置換を用いた行列式の定義と行列…
幅長さの場所の上に,以下の二種類のタイル 幅長さのタイル 幅長さのタイル を右詰めで,個以上敷くことを考える. このような敷き方の集合をとかく. (記事下にの例があるのでそれも参照せよ.)をフィボナッチ数とすると,このような敷き方は 通りである…
概要 Stieltjes連分数を普通の分数で書いたときの式 において,多項式がライングラフのマッチング多項式であることを示す. 証明はFlajoletの補題に基づいてStieltjes連分数をDyck路の母関数とみて,適当な対合を作る方法で行う. 用語の準備 Stieltjes連分…
Combinatorial species (Combinatorial species - Wikipedia)は,離散オブジェクトの指数型母関数を扱うための現代的な手法である. 本稿ではspeciesの理論自体を説明することはしないが,大まかに言えばspeciesの理論は離散オブジェクトの組合せ論的な構造…
置換の符号とは,対称群からへの唯一の非自明な準同型でとかきます. この置換の符号を使って,例えば行列式などが などと定義できるのでした.ここで,符号の値域をではなく,にすると,置換の符号を精密化した「一般化符号」ができて面白いんじゃないかと…
個の文字から重複を許して個とるとり方は 通りである.このことを二通りの方法で示す. 証明その1 個の文字から重複を許して個とるとり方は, 個の (区別できない)ボールと個の (区別できない)仕切りを一列に並べる並べ方と一対一対応する. なぜならば,そ…
命題 変数論理関数,つまり写像は通り存在する.証明 と書いた時点でほとんど明らかな気がするが,証明するには真理値表が何通り書けるかを考えればよい. からまでの通りの入力が,それぞれのどちらになるかを決めるので,通りになる. (証明終わり)蛇足 …
以下の命題の代数的証明と組合せ論的証明を紹介する.また,組合せ論的証明に基づいてパラメータを増やす拡張を行う.定理 自然数について が成立する.上式左辺は,添字が動く範囲がだということを表す. また右辺は,-解析の記号を使うとと書ける. 代数的…
記事概要 本記事では以下を組合せ論的に示す. 証明は対合を構成することで行う. 具体的には例えばのときはが成り立つ. 定義や準備など 調べたところ,第二種スターリング数の行列式を考えた研究には[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この巡回列に分解する方法の場合の数)のこの性質…
本記事の結論 時間がない人のために結論だけ書くと,以下が成立する (cf. [2]). , .とはそれぞれ第一種,第二種スターリング数で,右辺は基本,完全対称式である. このをに変えると, 標準的なスターリング数と呼ばれているものが得られる. 第一種,第二…
実数 , をとり, 点をこの順番に線分で結んでできる有界領域を「平行六角形」と呼ぶことにする.つまり,以下の図みたいなやつのことである. 平行六角形には上の図に赤い点線で描いたような内接楕円が存在するように見える. ここでいう内接楕円とは,平行…
三角格子上の平行六角形は,大きさに関わらずひし形タイル張りができることが知られている [1]. 例えば,下図左の赤で示された領域は右のようなひし形タイル張りが可能である.なので当然,任意の平行六角形に含まれる上向きの三角形△の数と下向きの三角形▽…
上向きの正三角形△と下向きの正三角形▽をつなぎ合わせて作る,下図の赤い部分で表される領域を考える. この領域は, △▽△▽△▽△▽△▽△▽△ ▽△▽△▽△▽△▽△▽△▽ みたいなやつを縦に積み重ねたものである.そこで,「底辺」に含まれる下向き三角形▽の数を,積み重ねた段の…
置換をサイクル分解したとき現れるサイクルの数をサイクル数という.置換のサイクル数をとかく.この統計量について,次の式が知られいてる. (式 1) 但し,は形式的な変数であり,とする.(式 1)についてより詳しくは,Stanley (R. P. Stanley, Enumerative…
自然数 について,以下の和を組合せ論的手法で求める. まず,和をの冪集合についての和に書き換える.とかくと さらに,この和を集合についての和に変えることができて, となる.のとき,からへの対合で,とすると, が成立するものを構成することができる…
major indexとは置換の統計量つまり,対称群から非負整数への写像の一種である. major indexは,以前このブログでも紹介した「置換の転倒数」と等分布であることが知られている. つまり,以下の母関数の式が成立する.(式 (1)とする.) .(参考:R. P. S…
本稿では置換の転倒数の母関数が綺麗という側面から転倒数に触れていくが,転倒数という概念自体は行列式の性質を証明するために有用であったりとか (岩瀬順一,岩瀬順一の「授業をする際のヒント --- 数学編」,転倒数を利用し、互換の積への分解を飛ばして…
Viennot先生の講義動画で,組合せ論的オブジェクトを有限オートマトンへ全単射的に変換して,母関数を簡単に求める方法が紹介されていました. 動画では,道グラフのマッチング(その個数はフィボナッチ数)を状態数2の有限オートマトンに変換していました.…
追記 (2023年2月4日) 三次の場合についても成り立つようです. stack exchangeで証明を教えていただきました. mathoverflow.net以下本文. 定理 定数でなく,また定数項がでない非負整数係数の二次多項式 は,係数の和 が素数ならば 上既約である.(整数の…
第一種チェビシェフ多項式は,により定義される多項式であり, 漸化式 により定義することもできます. 第一種チェビシェフ多項式についてはこのブログでも以前話題に上げました. iwalion.hatenablog.com 第一種チェビシェフ多項式は「閉路グラフのマッチン…
カッコを正しく並べる方法が通りあることを全単射的に示します.
みなさん御存知の通り, です.この式の導出は「」をからまで足すみたいなやつが有名です.(ググればたぶん一番上に出てきます.) だけど,二乗和を求めると言われたときに「」を使う発想に至るのは飛躍が大きい気がして個人的にあまり好きじゃないです.…