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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.