# Divisibility of sum of multinomials

Let $$n, m$$ and $$t$$ be positive integers. Define the multi-family of sequences $$S(n,m,t)=\sum_{k_1+\cdots+k_n=m}\binom{m}{k_1,\dots,k_n}^t$$ where the sum runs over non-negative integers $$k_1,\dots,k_n$$. These numbers are related to average distances (from the origin) of uniform unit-step random walks on the plane.

QUESTION. Is it always true that $$n$$ divides $$S(n,m,t)$$?

Observe that $$S(n,m,1)=n^m$$.

We count the number of $$t$$-tuples $$(\xi_1,\ldots,\xi_t)$$ of the colorings of $$\{1,\ldots,m\}$$ with $$n$$ given colors, for which any two colorings use the same multisets of colors. If $$M$$ is the number of such tuples in which 1 is colored red in the coloring $$\xi_1$$ (red is one of our $$n$$ colors), the total number of $$t$$-tuples equals $$n\cdot M$$.