4
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

$${k\choose t_1, t_2, ... , t_m }=\frac{k!}{t_1! \ldots t_m!}$$

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.