2019-09-09

正n角形の3頂点を結んで作れる合同でない三角形の数

数Aの場合の数の問題で，
「正7角形の頂点を3つ結んで作れる互いに合同でない三角形は何種類ですか」
みたいなのがあります．

これが正 $n$ 角形だとどうなるか調べてみます．

参考
大阪府立高津高等学校の久世さんとバセダさんが，2010年に同じ研究をしていました．
正ｎ角形の頂点を結んでできる三角形の合同類の個数は？
ポスター並びに口頭発表要旨
上記研究では互いに合同でない三角形の個数を分割数で表すところまでは同じですが，そこから具体的に数えていく方法が本記事とは違うみたいです．

本記事の結論は以下の二つです．
定理１
正 $n$ 角形の3頂点を結んでできる互いに合同でない三角形の数を $\Delta(n)$ とする．
その母関数は以下で表される．
$\sum_{n\geq 0}\Delta(n)q^n = \frac{q^3}{(1-q)(1-q^2)(1-q^3)}$

定理２
正 $n$ 角形の $3$ 頂点を結んでできる互いに合同でない三角形の数を $\Delta(n)$ とする．
自然数 $n$ が非負整数 $k$ を用いて
$n-3=6k$ と表せるとき， $\Delta(n)=3k^2+3k+1$ ，
$n-3=6k+i\ (i=1,\ldots,5)$ と表せるとき， $\Delta(n)=(k+1)(3k+i)$ ．

定理１の証明
正 $n$ 角形 $A_1A_2\cdots A_n$ の $3$ 頂点 $\{A_i,A_j,A_k\}\ (i\lt j\lt k)$ を結んでできる三角形全体の集合を考え，合同関係による商を考える．
各同値類には以下の二条件を満たす三角形が唯一存在するため，それを代表元とする．

$A_i = A_1$
$A_iA_j \leq A_jA_k\leq A_kA_i$

各代表元は $A_1A_jA_k$ という形をしていて，
自然数 $x,y,z$ を $x\triangleq j-1,\ y\triangleq k-j,\ z\triangleq n-k+1$
と定めれば， $x+y+z=n,\ 1\leq x\leq y\leq z$ である．
また逆にそのような自然数 $x,y,z\in\mathbb{N}$ の全体は，完全代表系と一対一対応している．

よって正 $n$ 角形の3頂点を結んでできる互いに合同でない三角形の数 $\Delta(n)$ は，
自然数 $n$ の長さ3の分割 $\lambda=(\lambda_1,\lambda_2,\lambda_3)\vdash n$ の数に等しい．
ヤング図形の転置を考えることで，それはさらに
自然数 $n-3$ の分割で，各要素の大きさが $3$ 以下であるものの数
$\#\{\lambda=(\lambda_1,\ldots,\lambda_r)\vdash (n-3)\mid \lambda_i\leq 3\ (i=1,\ldots,r)\}$
にひとしい．
よって $\Delta(n)$ の母関数は $\sum_{n-3\geq 0}\Delta(n)q^{n-3}=\frac{1}{(1-q)(1-q^2)(1-q^3)}$ と表せる．（証明終）

補足
長さ $3$ の分割の母関数は，ヤング図形の転置を考えることなく母関数
$\sum_{1\leq x\leq y\leq z}q^{x+y+z}$ の直接計算によっても導くことができる．
その際は，MacMahonのΩ解析と呼ばれるテクニックが用いられる．

定理２の証明
自然数 $n-3$ の分割で，各要素の大きさが $3$ 以下であるものの数
$\#\{\lambda=(\lambda_1,\ldots,\lambda_r)\vdash (n-3)\mid \lambda_i\leq 3\ (i=1,\ldots,r)\}$
をがんばって求める．
求め方は，以前書いた以下の記事で使った素朴な方法と殆ど同じである．
iwalion.hatenablog.com
まず，分割に $3$ が何個含まれるかで場合分けし，さらに $2$ がいくつ含まれるかを考えてゆく．
例えば，非負整数 $k$ を使って $n-3=6k$ と表せるとき，
$3$ を $2i$ 回使うなら，残り $6k-6i$ を $1と2$ の和で表す方法は $3(k-i)+1$ 通り，
$3$ を $2i+1$ 回使うなら，残り $6k-6i-3$ を $1と2$ の和で表す方法は $3(k-i)-1$ 通り，
以上から全部で
$\sum_{i=0}^k\{3(k-i)+1\}+\sum_{i=0}^{k-1}\{3(k-i)-1\}=3k^2+3k+1$ 通り．

$n-3=6k+i\ (i=1,\ldots,5)$ と表せるときも，めんどくさいが同じようにできる．
（証明終）

2019-07-09

半標準ヤング盤の列挙アルゴリズム

プログラミング

追記：このプログラムにはおそらくバグがあり、特定のサイズのヤング版で正しく列挙できない現象が起こります。
使わないでください。
(2020/09/13)

12月頃，このブログで「平面分割」を列挙するアルゴリズムを載せました．
iwalion.hatenablog.com

今回は似てますが「要素に上限を持つ半標準ヤング盤」を列挙するアルゴリズムを作りました．

半標準ヤング盤とは

長さ $k$ 以下の整数の分割 $\lambda=(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k \geq 0)$ をとります．各 $\lambda_i$ は非負整数です．また， $k$ 以上の非負整数 $b\geq k$ をとります．
以下の二条件を満たす $k\times \lambda_1$ 行列 $A=(a_{i,j})_{1\leq i\leq k,1\leq j\leq \lambda_1}$ を列挙することを考えます．

$A$ の各要素は $1\leq i\leq k, 1\leq j\leq \lambda_i$ のとき， $1$ から $b$ までの整数で，それ以外の $i,j$ のとき $0$ .

$A$ の各要素は $1\leq i\leq k, 1\leq j\leq \lambda_i$ の範囲で，列に関して狭義増大，行に関して弱い意味で増大．

今回も詳細は書くのがめんどくさいので省きますが，c++のコードを載せておきます．
このコードでは例として $\lambda=(5,3,3,2), b=6$ を列挙しています．

たとえば，こんなやつです↓ （下向きに強く増大，右向きに非減少．0は省略している．）

1 1 3 4 4
2 3 4
3 4 5
6 6

このコードで列挙した半標準ヤング盤の集合が間違っていなさそうなことを，「Jadobi-Trudi恒等式」に当てはめて何通りかの $\lambda,b$ で検算しました．
「Jadobi-Trudi恒等式」については，ウィリアム・フルトン『ヤング・タブロー』（丸善，2019）のp. 78か，StanleyのEnumerative Combinatorics vol. 1(Cambridge, 2010) のp. 342を参照してください．

注意：main関数内でc++11が必要な書き方をしているので，-std=c++11をつけてコンパイルしてください．

//
//
// 最大要素を指定する半標準版ヤング盤列挙プログラム
//
// 07/09/2019
//
// author: iwalion
//
//
//
//

#include <iostream>
#include <vector>
#include <fstream>


#define INFTY 10000

using namespace std;

class Tableau
{
	//タブローの本体
	//1000 1000 1000 1000 1000
	//1000 1000 1000 1000    6
	//1000 1000 1000    6    5
	//1000    6    6    5    4
	//1000    5    5    4    3
	// のように行に関して弱く減少，列に関して強く減少の形で保持する
	// 1000は空欄を示す．
	// タブローのタイプより縦横ともにひとつ大きい配列を確保する．
	private:
		vector< vector<int> > my_tableau;
		vector<int> type;
		int size_row;
		int size_col;
		int max_entry;
		
		const int my_INF = INFTY;

	//コンストラクタ・デストラクタ
	public:
		Tableau(vector<int> partition, int max_number);
		~Tableau();

	public:
		//タブローを標準出力で見る
		void inspect();

		//タブローの全順序に従って一つ増やす
		//増やせたら1，増やせなかったら0を返す
		int increase_by_one(void);

		vector< vector<int> > nakami(void){
			return my_tableau;
		}

		//整形して出力するための関数
		void output_to_file(ofstream &ofs);
};

void Tableau::output_to_file(ofstream &ofs)
{
	for(int i=0; i<=type.size()-1; i++){
		for(int j=0; j<=type[0]-1; j++){
			if(my_tableau[size_row-i-1][size_col-j-1] == my_INF){
				ofs << 0;
			}else{
				ofs << my_tableau[size_row-i-1][size_col-j-1];
			}
			if(j < type[0]-1 ){
				ofs << ',';
			}
		}
		if(i < type.size()-1){
			ofs << '/';
		}
	}
	ofs << '\n';
	return;
}


Tableau::Tableau(vector<int> partition, int max_number)
{

	if(max_number >= my_INF){
		cerr << "error: プログラム上の定数INFを大きくしてください" << endl;
		exit(1);
	}
	if(partition.size() > max_number){
		cerr << "error: 指定された最大要素は小さすぎて無理です" << endl;
		exit(1);
	}
	if(partition.size() == 0){
		cerr << "error: コンストラクタへの入力が空です\n" << endl;
		exit(1);
	}
	for(int i=0; i<=partition.size()-1; i++){
		if(partition.size() > 1 &&  partition[i] < partition[i+1]){
			cerr << "error: コンストラクタへの入力は単調非増加にしてください\n" << endl;
			exit(1);
		}
	}

	//必要なサイズよりひとつ大きい配列を確保する	
	//空欄はINFTYで埋めておく
	vector< vector<int> > hoge;
	for(int i=0; i<=partition.size(); i++){
		vector<int> piyo(partition[0]+1, my_INF);
		hoge.push_back(piyo);
	}


	//データの書き込み
	max_entry = max_number;
	my_tableau = hoge;
	size_row = my_tableau.size();
	size_col = (my_tableau[0]).size();
	type = partition;


	//大きさが一番小さいタブローを書き込む
	for(int i=0; i<=type.size()-1; i++){
		for(int j=0; j<=type[i]-1; j++){
			my_tableau[size_row-i-1][size_col-j-1] = i+1;
		}
	}


}

Tableau::~Tableau()
{
	cout << "破棄" << endl;
}


int Tableau::increase_by_one(void)
{
	for(int i=0; i<=type.size()-1; i++){
		for(int j=0; j<=type[i]-1; j++){

			//増やせる数字を探す
			if( my_tableau[size_row-i-1][size_col-j-1] < my_tableau[size_row-i-1][size_col-j-2] ){
				if( my_tableau[size_row-i-1][size_col-j-1] < my_tableau[size_row-i-2][size_col-j-1] -1 ){
					if(my_tableau[size_row-i-1][size_col-j-1] < max_entry){
						my_tableau[size_row-i-1][size_col-j-1] += 1;

						//もし増やした場合，それより以前の場所を全部初期化する．
						for(int inner_i=0; inner_i<=i; inner_i++){
							//今いる行より下は全部初期化
							if(inner_i < i){
								for(int inner_j=0; inner_j<=type[inner_i]-1; inner_j++){
									my_tableau[size_row-inner_i-1][size_col-inner_j-1] = inner_i+1;
								}
							}else
							//今いる行は，今いるところまで初期化
							{
								for(int inner_j=0; inner_j<=j-1; inner_j++){
									my_tableau[size_row-inner_i-1][size_col-inner_j-1] = inner_i+1;
								}
							}
						}
						
						//増やせたら1を返す
						return 1;
					}
				}
			}
			//三重ifここまで
		}
	}

	//増やせる数字が一つもないとき0を返す
	return 0;
}

void Tableau::inspect()
{
	for(int i=0; i<=size_row-1; i++){
		for(int j=0; j<=size_col-1; j++){
			if(my_tableau[i][j] != my_INF){
				printf("%2d",my_tableau[i][j]);
			}else{
				//printf("%5d",my_tableau[i][j]);
				printf("  ");
			}
		}
		printf("\n");
	}
}

int main(){
	vector<int> a{5,3,3,2};
	Tableau unko(a,6);

	int num = 1;
	

	ofstream ofs;
	ofs.open("TAB_5332_6.txt", ios::out);

	while(1){
		unko.inspect();
		unko.output_to_file(ofs);
		if(unko.increase_by_one() == 0){
			printf("NUM = %d\n",num);
			break;
		}
		num++;
	}

	ofs.close();
	return 0;
}

2019-07-03

1円玉，5円玉，10円玉を使ってN円をぴったり支払う方法の数

母関数高校数学

1円玉，5円玉，10円玉を使って $N$ 円をぴったり支払う方法の数を研究します．

同じことをやっている人は，ググった感じだと

組み合わせの問題です。 -（１）1円、5円、10円の硬貨をとりまぜて合計- 数学 | 教えて!goo
や
西三数学サークル通信44号
なんかがありました．

この記事では以下の定理を二通りの方法で証明します．

定理
$N$ は非負整数とする．1円玉，5円玉，10円玉を使って $N$ 円を正確に支払う方法の数は

非負整数 $n$ を使って $N=10n,10n+1,10n+2,10n+3,10n+4$ と書けるとき

$(n+1)^2$ 通り，

非負整数 $n$ を使って $N=10n+5,10n+6,10n+7,10n+8,10n+9$ と書けるとき

$(n+1)(n+2)$ 通り
である．

証明１．（直接数える証明）

非負整数 $n$ を使って $N=10n,10n+1,10n+2,10n+3,10n+4$ と書けるとします．
10円玉を何個使うかで場合分けします．
10円玉を $n$ 個使う場合は，払い方は1通り．
10円玉を $n-1$ 個使う場合は，払い方は5円玉を2個，1個，0個使う場合の3通り．
10円玉を $n-2$ 個使う場合は，払い方は5円玉を4個，3個，...，0個使う場合の5通り．
...
10円玉を $0$ 個使う場合は，払い方は5円玉を $2n$ 個，...，0個使う場合の $2n+1$ 通り．

これらを合わせると， $\sum_{i=0}^n(2i+1)=(n+1)^2$ 通り．

一方，非負整数 $n$ を使って $N=10n+5,10n+6,10n+7,10n+8,10n+9$ と書けるとします．
10円玉を $n$ 個使う場合は，払い方は5円玉を1個，0個使う場合の2通り．
10円玉を $n-1$ 個使う場合は，払い方は5円玉を3個，2個，1個，0個使う場合の4通り．
...
10円玉を $0$ 個使う場合は，払い方は5円玉を2n+1個，...，0個使う場合の2n+2通り．

これらを合わせると， $\sum_{i=0}^n(2i+2)=(n+1)(n+2)$ 通り．
（証明終）

証明２．（母関数を使う証明）

1円玉，5円玉，10円玉を使って $N$ 円を支払う方法の数は，形式的冪級数
$(1+q+q^2+q^3+\cdots)(1+q^5+q^{10}+q^{15}+\cdots)(1+q^{10}+q^{20}+q^{30}+\cdots)$
$=\frac{1}{(1-q)(1-q^5)(1-q^{10})}$
における $q^N$ の係数です．

定理の主張は，その $q^N$ の係数が，
非負整数 $n$ を使って $N=10n,10n+1,10n+2,10n+3,10n+4$ と書けるとき $(n+1)^2$ であり，非負整数 $n$ を使って $N=10n+5,10n+6,10n+7,10n+8,10n+9$ と書けるとき $(n+1)(n+2)$ であるというものです．

よって示すべき式は
$\sum_{n=0}^\infty(n+1)^2q^{10n}(1+q+q^2+q^3+q^4)$
$+\sum_{n=0}^\infty(n+1)(n+2)q^{10n+5}(1+q+q^2+q^3+q^4)$
$=\frac{1}{(1-q)(1-q^5)(1-q^{10})}$
です．

$(1+q+q^2+q^3+q^4)=\frac{1-q^5}{1-q}$ なので，この部分を右辺におしやり，さらに $q^5$ を新しく $x$ と書きます．
$\sum_{n=0}^\infty(n+1)^2(x^2)^{n}+x\sum_{n=0}^\infty(n+1)(n+2)(x^2)^{n} =\frac{1}{(1-x)^2(1-x^2)}$

左辺を
$\sum_{n=0}^\infty n^2x^n=\frac{x(1+x)}{(1-x)^3},$
$\sum_{n=0}^\infty nx^n=\frac{x}{(1-x)^2},$
$\sum_{n=0}^\infty x^n=\frac{1}{1-x},$
などを使って計算すれば右辺に一致します．
（証明終）

今後の課題

1円，5円，10円，50円，100円，500円を使って $N$ 円を支払う方法の数が気になります．
誰か自由研究でやってください．

追記 (2022年6月7日)：この記事の続編を書きました。

上の二つとは違う、より全単射的な証明を書いています。
iwalion.hatenablog.com

2019-06-22

(nCk)^2 > (nC_{k+1})(nC_{k-1})の三通りの証明

全単射的証明高校数学

二項係数の不等式
$({}_n{\rm C}_k)^2>({}_n{\rm C}_{k+1})({}_n{\rm C}_{k-1})$
を代数的方法、全単射的方法、非交差経路を使う方法により証明します。

続きはpdfで。

drive.google.com

2019-06-14

どの数もあまり後ろへは行かないような置換の総数+行列式計算への応用

置換行列式

ある会社では社員が７人いて，それぞれの社員に「窓際＜新人＜係長＜課長＜部長＜社長＜会長」の順番でエラさに差があるポストが割り振られるそうである．
ある時この会社は人事刷新をして，全員でポストを決め直すことになった．ただし，元々エラかったひとが一気に格下になるとショックで辞めてしまうので，どの人についてもエラさの階級が３段階以上さがらないようにしたい．
そのようなポストの決め方は何通りあるだろうか．

答えは，486通りである．
一般に，社員が $n$ 人いて，それぞれの階級が $k\ (n\geq k\geq 1)$ 段階以上さがらないように同じことをする場合，決め方は $k!k^{n-k}$ 通りである．

続きはpdfで．

drive.google.com

2018-12-05

平面分割の列挙アルゴリズム

プログラミング

10月末に綾@ (@ayaHSYKZ)さんが，以下のような問題をツイートしました．

問題、深夜にひっそりあげてみる pic.twitter.com/xE8UcrztR3
— 綾@ (@ayaHSYKZ) 2018年10月27日

消えたときのために文章でも書いておくと，

以下の二条件を満たす $5\times 5$ 行列 $A=(a_{i,j})_{0\leq i,j\leq 4}$ の個数を求めよという問題です．

$A$ の各要素は $0$ か $1$ か $2$ である．

全ての整数 $0\leq i,j\leq 4$ に対して $a_{i+1,j}\leq a_{i,j}$ かつ $a_{i,j+1}\leq a_{i,j}$ が成立．つまり $A$ は各行各列について単調非増加である．

この問題は実は，「平面分割 (plane partition)」という名前でより一般に研究されています．
Plane partition - Wikipedia

今回は，一般に行列サイズが $a\times b$ で，各要素が $0$ から $n-1$ までの整数だとしたとき，上記の条件を満たす行列を列挙するアルゴリズムを設計し，c++で実装しました．

詳細は書くのがめんどくさいので省きますが，コードを載せておきます．
ちなみに，このアルゴリズムを使って求めた結果，綾@さんの問題の答えは「 $19404$ 通り」でした．

#include <iostream>
#include <vector>
#include <utility>

#define MIN(x,y) ((x<y)? x: y)

using namespace std;

void vector_vanish(vector<int> &vec);
void vector_inspect(vector<int> vec);
int vector_increment(vector<int> sup, vector<int> &data);
int level_increment(pair< vector<int>, vector<int> > sup,
					pair< vector<int>, vector<int> > &data);
int PP_increment(vector< pair< vector<int>, vector<int> > > &pp);
void PP_inspect(vector< pair< vector<int>, vector<int> > > pp);

int main(){
	const int r=5;
	const int c=5;
	//r<=cを仮定する．
	const int n=2;

	vector< pair< vector<int>,vector<int> > > pp;
	for(int i=r-1; i>=0; i--){
		vector<int> hor(c-i,0);
		vector<int> var(r-1-i,0);
		pair< vector<int>,vector<int> > adj(hor, var);
		pp.push_back(adj);
	}
	//平面分割を入れる箱を準備
	
	vector<int> hor(c+1,n);
	vector<int> var(r,n);
	pair< vector<int>, vector<int> > adj(hor, var);
	pp.push_back(adj);
	//平面分割の高さの上限を設定
	
	int count=0;
	do{
		PP_inspect(pp);
		count++;
		cout << endl;
	}while(PP_increment(pp));

	cout << "count = " << count << endl;

	double prod = 1;
	for(int i=0; i<=r-1; i++){
		for(int j=0; j<=c-1; j++){
			for(int k=0; k<=n-1; k++){
				prod *= ((double)(i+j+k+2))/((double)(i+j+k+1));
			}
		}
	}
	cout << "prod = " << prod << endl;

	return 0;
}

void PP_inspect(vector< pair< vector<int>, vector<int> > > pp){
	int r = pp.size()-1;
	int c = pp[r-1].first.size();

	vector< vector<int> > kekka;
	for(int i=0; i<=r-1; i++){
		vector<int> a(c,0);
		kekka.push_back(a);
	}

	for(int i=0; i<=r-1; i++){
		for(int j=0; j<=c-1; j++){
			if(i<=j){
				kekka[i][j] = (pp[r-1-i].first)[j-i];
			}else{
				kekka[i][j] = (pp[r-1-j].second)[i-j-1];
			}
		}
	}


	for(int i=0; i<=r-1; i++){
		for(int j=0; j<=c-1; j++){
			cout << kekka[i][j] << " ";
		}
		cout << endl;
	}

	//平面分割になってるかチェックする
	for(int i=0; i<=r-2; i++){
		for(int j=0; j<=c-2; j++){
			if(kekka[i][j] < kekka[i+1][j] ||
					kekka[i][j] < kekka[i][j+1]){
				cout << "Error: 平面分割になってません." << i << j << endl;
				exit(1);
			}
		}
	}
	return ;
}

int PP_increment(vector< pair< vector<int>, vector<int> > > &pp){
	int r = pp.size()-1;
	for(int i=0; i<=r-1; i++){
		if(level_increment(pp[i+1],pp[i])){
			//レベルiがインクリメントできたとき
			//レベルiより前を全部消す
			for(int j=0; j<=i-1; j++){
				vector_vanish(pp[j].first);
				vector_vanish(pp[j].second);
			}
			//mainに戻る
			return 1;
		}
	}
	//これ以上インクリメントできないとき
	return 0;
}


int level_increment(pair< vector<int>, vector<int> > sup,
					pair< vector<int>, vector<int> > &data){
	//verがインクリメントできるならverをインクリメント
	//horをインクリメントできるならhorをインクリメントしvarを消す
	//インクリメントできたなら1を返す
	
	//まず，関数vector_incrementに突っ込むためのベクトルを作る
	//verについて
	int ver_size = data.second.size();
	vector<int> vec_ver_sup(ver_size);
	for(int i=0; i<=ver_size-1; i++){
		vec_ver_sup[i] = MIN((sup.second)[i+1], (data.first)[0]);
	}
	//horについて
	int hor_size = data.first.size();
	vector<int> vec_hor_sup(hor_size);
	for(int i=0; i<=hor_size-1; i++){
		vec_hor_sup[i] = MIN((sup.first)[i+1], (sup.second)[0]);
	}
	
	//どちらもインクリメントできないなら0を返す
	if(vec_hor_sup == data.first && vec_ver_sup == data.second){
		return 0;
	}

	//varをインクリメント
	if(vector_increment(vec_ver_sup, data.second)){
		return 1;
	}
	//varがインクリメントできなかったとき
	//horをインクリメント
	vector_vanish(data.second);
	if(vector_increment(vec_hor_sup, data.first)){
		return 1;
	}

	//ここまで達するのはおかしい
	cout << "Error" << endl;
	exit(1);
}


int vector_increment(vector<int> sup, vector<int> &data){
	if(sup == data){
		return 0;
	}
	int r = sup.size();

	for(int j=r-1; 1<=j; j--){
		if(data[j-1] > data[j]){
			if(sup[j] > data[j]){
				data[j]++;
				for(int i=r-1; j<i; i--){
					data[i] = 0;
				}
				return 1;
			}
		}
	}
	if(sup[0] > data[0]){
		data[0]++;
		for(int i=r-1; 0<i; i--){
			data[i] = 0;
		}
		return 1;
	}else{
		cout << "Error" << endl;
		exit(1);
	}
}


void vector_vanish(vector<int> &vec){
	int size = vec.size();
	for(int i=0; i<=size-1; i++){
		vec[i] = 0;
	}
	return;
}

void vector_inspect(vector<int> vec){
	int size = vec.size();
	for(int i=0; i<=size-1; i++){
		cout << vec[i]  << " ";
	}
	cout << endl;
	return;
}

2018-10-20

q-二項係数

母関数

この記事では $q$ -二項係数を組合せ的に定義し，その値を求めます．

非負整数 $m,n$ が与えられているとします．
長さ1の水平な線分と垂直な線分を使って作れる，点 $(0,n)$ から点 $(m,0)$ への最短路の個数は，二項係数を使って
$\binom{m+n}{n}$
と表されます．図1はそのような最短路の例です．

定義と例

$q$ -二項係数は二項係数の拡張です．まず一つ必要な定義をします．
点 $(0,n)$ から点 $(m,0)$ への最短路 $P$ に対してその面積 ${\rm area}(P)$ を，路 $P$ と， $x$ 軸， $y$ 軸で囲まれた部分の面積だと定義します．
例えば図1の路を $P$ とすると，その面積は ${\rm area}(P)=14$ です．例えば ${\rm area}(P)$ は図2における緑色の部分の面積に対応しています．

面積を使って $q$ -二項係数を次のように定義します．
定義( $q$ -二項係数)
非負整数 $m,n$ に対し，
$\binom{m+n}{n}_q\triangleq\sum_{P:(0,m){\rm to}(n,0)} q^{{\rm area}(P)}$
を， $m+n, n$ に対する $q$ -二項係数という．
ただし和の添字は， $(0,m)$ から $(n,0)$ への最短路全てについての和をとることを意味する．

$q$ -二項係数は， $q=1$ のとき通常の二項係数に一致し，その意味で通常の二項係数の一般化となっています．
例として $m=2, n=2$ の場合について定義を確認してみます．
点 $(0,2)$ と点 $(2,0)$ を結ぶ最短路は六つあり，面積0, 1, 3, 4のものがそれぞれ一つづつ，面積2のものが二つあります．詳しくは表1を見てください．
よって定義から $4,2$ に対する $q$ -二項係数は，
$\binom{4}{2}_q=1+q+2q^2+q^3+q^4$ です．

表1: 点 $(0,2)$ と点 $(2,0)$ を結ぶ最短路の一覧と，その面積．

$P$	${\rm area}(P)$
	0
	1
	2
	2
	3
	4

$q$ -二項係数を求める

与えられた非負整数 $k\leq n$ に対し， $\binom{n}{k}_q$ の値を求めます．

命題1
非負整数 $n,k$ は $1\leq k\leq n$ を満たすとする．そのとき，
$\binom{n+1}{k}_q = q^k\binom{n}{k}_q + \binom{n}{k-1}_q$ .

証明
左辺は点 $(0,k)$ と点 $(n-k+1,0)$ をむすぶ最短路 $P$ について $q^{{\rm area}(P)}$ の和をとったものです．
そのような最短路を，

点 $(0,k)$ から下へ行くもの
点 $(0,k)$ から右へ行くもの

の二つに分けます．
前者の場合，点 $(0,k)$ から下へ伸びている最短路は全て，「点 $(0,k-1)$ と点 $(n-k+1,0)$ をむすぶ最短路」に「点 $(0,k-1)$ から点 $(0,k)$ への線分」をつけたものになっています．図3は前者の場合の路の模式図です．

「点 $(0,k-1)$ から点 $(0,k)$ への線分」をつける前と後で面積は変化しないので，前者に含まれる最短路 $P_1$ について $q^{{\rm area}(P_1)}$ の和をとると，それは $\binom{n}{k-1}_q$ に一致します．

後者の場合，点 $(0,k)$ から右へ伸びている最短路は全て，「点 $(0,k)$ と点 $(n-k,0)$ をむすぶ最短路」を右方向に１だけ平行移動したものになっています．
図4は後者の場合の模式図で，赤い路は点 $(0,k)$ から点 $(n-k+1,0)$ への最短路を表していて，黄色い路は赤い路に対応する，点 $(0,k)$ から点 $(n-k,0)$ への最短路を表しています．