自己紹介&Worpitzky's identityについてのお話

方針で定義したように$f(m,n)$を定義し、これを$2$通りで数え上げる。
($1$通りめ)
仕切り順列の要素の順番にかかわらず常に仕切りは$m-1$個ある。よって仕切り順列は、$m-1$個の仕切りによって$n$個の数からなる順列が$m$個の順列(左から順に$p_{1},p_{2},…,p_{m}$とする)に分割されたものと捉えることができる(仕切りが連続する部分については、空集合(のようなもの)として分割されたと考える)。仕切り順列の満たす条件より、各$p_{i}(1\leq i \leq m)$は常に単調減少数列になる(または要素の個数が$1$あるいは$0$となる)。したがって、各$p_{i}$に当てはまる要素がすべて決定されると$p_{i}$も決定されることになる。ここで、$g:\{1,2,…,n\}\rightarrow\{1,2,…,m\}$を満たす写像$g$を考える。任意の$x\in\{1,2,…,n\}$について$x$を$p_{g(x)}$に当てはめるような割り振り方を考えれば、$g$と各仕切り順列が一対一に対応することがわかる。各$x\in\{1,2,…,n\}$について$g(x)$には$1,2,…,m$の$m$通りの値の取り方があるので、$g$としてありうるものは$m^{n}$個ある。したがって$$f(m,n)=m^{n}$$を得る。
($2$通りめ)
仕切りを加える順列を固定して考える。ここで$0\leq k \leq n-1$を満たす$k$について、上昇要素の個数が$k$であるとする。このとき$k$個の上昇要素の直前に仕切りを入れなければならないので、追加する場所に制限のない仕切りの数は$m-1-k$である。$m-1-k < 0$のときは、ありうる仕切り順列の個数は$0$であるとしてよく、以下そうでない時を考える。仕切りを入れられる箇所は、順列の要素数が$n$なので$n+1$個あり、仕切りは区別されないので、入れる場所に制限のない仕切りの入れ方は常にひとつにつき$n+1$通りである。それに加えて、仕切りを入れられる箇所は、そこが左から何番目にあるかによって全て区別される。以上より、入れる場所に制限のない仕切りの入れ方の総数は、$n+1$個の物の中から重複を許して$m-1-k$個の物を選ぶ選び方の総数と等しく、それは$$\c{(n+1)+(m-1-k)-1}{m-1-k}=\c{n+m-1-k}{m-1-k}=\c{n+m-1-k}{n}$$
に等しい。また、$p< q$のとき$\c{p}{q}=0$と定義したので、$m-1-k$の符号によらず(つまり$k$の値によらず)、固定された順列に仕切りを加える方法の総数は$\c{n+m-1-k}{n}$である。一方、上昇要素の個数が$k$である順列の個数は定義より$\e{n}{k}$であるから、以上より上昇要素の個数が$k$のとき、仕切り順列は$\e{n}{k}\c{n+m-1-k}{n}=\e{n}{n-1-k}\c{n+m-1-k}{n}$通り存在する。ここで、$\e{n}{k}=\e{n}{n-1-k}$を用いた(順列を右から見ていったときの上昇要素を考えれば証明できる)。よって$k$を$0\leq k \leq n-1$の範囲で動かして、
\begin{align} \displaystyle f(m,n)&=\sum_{k=0}^{n-1}\e{n}{n-1-k}\c{n+m-1-k}{n}\\ f(m,n)&=\sum_{k=0}^{n-1}\e{n}{k}\c{k+m}{n} \end{align}

以上$2$通りの数え上げにより、
$$f(m,n)=m^{n}=\sum_{k=0}^{n-1}\e{n}{k}\c{k+m}{n}$$
を得るが、これはWorpitzky's identityそのものである。