数え上げでいけるんじゃないかな。
両辺m!倍してΣn!/[{n-(p1+p2+p3+…+pm)}!p1!p2!p3!…pm!]*m!/{(1!)^p1(2!)^p2(3!)^p3…(m!)^pm}=n^mを示す。
いま、n種類の文字をm個、重複を許して並べることを考えよう。そのやりかたの数はn^m通りだ。
ここで、1回現れる文字がp1個、2回現れる文字がp2個、…であるような並べ方がいくつあるかを考える。
このとき0回現れる文字はn-(p1+p2+…+pm)個だから、どの文字を何回使うかの部分に関しては
n!/((n-(p1+p2+…+pm))!p1!p2!…pm!)通りの選び方がある。
各々に対して、それらの文字の並べ方がm!/((1!)^p1(2!)^p2…(m!)^pm)通りあるから、これで示された。