置換をサイクル分解したとき現れるサイクルの数をサイクル数という．置換のサイクル数をとかく．この統計量について，次の式が知られいてる． (式 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 第一種チェビシェフ多項式は「閉路グラフのマッチン…

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

みなさん御存知の通り， です．この式の導出は「」をからまで足すみたいなやつが有名です．（ググればたぶん一番上に出てきます．） だけど，二乗和を求めると言われたときに「」を使う発想に至るのは飛躍が大きい気がして個人的にあまり好きじゃないです．…

twitterで，数学系の解説画像って需要あるかなって思ってアップしたんですが，全然「いいね」が来なかったのでここに供養します．

第一種および第二種スターリング数と呼ばれる数列を定義して，その組合せ論的な意味付けを紹介します．参考とした本： Martin Aigner, A course in Enumeration, GTM 238, 2007.変数の昇冪 と降冪 を と定義します． 多項式の集合とはどちらも]の基底だから…