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$.



Divisibility of sum of multinomials
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$.


