数え上げに迷いをなくす方法

数学たん @suugakutan

数学Aの数え上げ数学が難しい人の多くは，どの公式を使えばよいか分からないと言う．その原因は，人は個々を区別し同じ色の碁石はしない，などという暗黙の了解があることや，単に日本語の意味が分からないことだと思う．そこで日本語でなく，集合を用いてその要素の数ということで定式化しよう．

数学たん @suugakutan

準備として，普通の集合と鞄と列を入れる．鞄の包含関係は重複度の大小で適当に定め，列の包含関係は部分列のそれとし，列の添字は，1から始まる自然数とする．列AについてA[i]でそのi番目の要素を言い，{a~b}でa以上b以下の整数の集合とする．

数学たん @suugakutan

新たな記法を入れる．”{”が”s{”となっていたら集合，”b{”となっていたら鞄，”r{”となっていたら列とする．

数学たん @suugakutan

そして，列から鞄への関数rtbはr{をb{にするようなものとし，列から集合へのrts，鞄から集合へのbtsも同様にし，集合から鞄へのstbはすべて重複度1で似た感じにする．

数学たん @suugakutan

実際にやってみる．「n人を1列に並べる並べ方の数は？」はcard s{ R∈{1~n}^n | rtbR=stb{1~n} }だ．これをF[n]としよう．F[n]=Σ{card s{ R∈{i}×{1~n}^(n-1) | rtbR = stb{1~n} } | i∈{1~n}}

数学たん @suugakutan

=Σ{card s{ R∈{i}×({1~n}-{i})^(n-1) | rtbR = stb{1~n} } | i∈{1~n}} =Σ{card s{ R∈{1~n-1}^(n-1) | rtbR = stb{1~n-1} } | i∈{1~n}}

数学たん @suugakutan

=n * card s{ R∈{1~n-1}^(n-1) | rtbR = stb{1~n-1} } =n * F[n-1] この通り，F[n]=n*F[n-1]と階乗の漸化式が出てくる． 順列や組合せにもやってみるとよい．

数学たん @suugakutan

こうしたことは確かに日本語から集合の記号に言い換えただけだけど，でもこれをやってから私は数え上げに迷いがなくなった．