Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I'm reading through this paper (on Dyck Paths). Near the middle of the second page, the author states the following:
Remark For the set $h_n$ there are ${k\choose t_1, t_2, ... , t_m }$ $n + k \choose{k}$ $=$ $ n + k\choose {n, t_1, t_2, ..., t_m}$ different Dyck paths.
What does ${k\choose t_1, t_2, ... , t_m }$ mean? I know what the binomial coefficient is, but I'm not sure how to interpret it when one of the parameters is a set.
It is the multinomial coefficient. That is, the coefficient of $x_1^{t_1}x_2^{t_2}\cdots x_m^{t_m}$ in $(x_1 + x_2 + \cdots + x_m)^k$. It is given by
$$ \frac{k!}{t_1!\cdots t_m!} $$
if each $t_i$ is non-negative and $t_1 + \dots + t_m = k$ and $0$ otherwise.
A special case is the binomial coefficient ($m = 2$):
$$ \binom{n}{k} = \binom{n}{k,n-k}. $$
$${k\choose t_1, t_2, ... , t_m }=\frac{k!}{t_1! \ldots t_m!}$$
The multinomial coefficient is defined by $${k\choose t_1, t_2, ... , t_m }=\frac{k!}{t_1! \ldots t_m!}, \sum t_i = k.$$ Combinatorially, it counts the number of ways to partition a set of $k$ elements into equivalence classes $S_1,\dots, S_m$ where each $|S_i|=t_i$.
In addition to the formal definition of the multinomial coefficient as given in other answers posted, note also that $$\begin{align} \binom k{t_1, t_2,\cdots, t_m} &=\frac {k!}{t_1! t_2! \cdots t_m!}\\ &=\binom k{t_1}\binom {k-t_1}{t_2}\binom {k-t_1-t_2}{t_3}\cdots \binom {k-t_1-t_2-\cdots t_{m-1}}{t_m}\\ &=\binom k{t_1}\binom {k-t_1}{t_2}\binom {k-t_1-t_2}{t_3}\cdots \binom {t_m}{t_m}\\\end{align}$$ where $t_1+t_2+t_3+\cdots+t_m=k$.
Hence $$\begin{align} \binom {n+k}k \binom k{t_1, t_2,\cdots, t_m} &=\binom {n+k}n\binom k{t_1}\binom {k-t_1}{t_2}\binom {k-t_1-t_2}{t_3}\cdots \binom {t_m}{t_m}\\ &=\binom {n+k}{n,t_1, t_2,\cdots, t_m}\end{align}$$
