What does this notation mean: $\tiny\left(\begin{matrix} y2-N \\ d_f -c, d_f-c \end{matrix}\right)$?

Question

Again, the notation is: $p_{split} = \left(\begin{matrix} y_2-N \\ d_f -c, d_f-c \end{matrix}\right)\left(\begin{matrix} 2N-y_2 \\ c,c \end{matrix}\right)\left(\begin{matrix} N \\ d_f, d_f \end{matrix}\right)^{-1}$.

This equation is from page 12 of this document on parameter generation for the NTRU PKCS. It is calculating the probability that the number of 1s and -1s in the last $2N-y_2$ entries of a trinary polynomial, $F$, will be equal to $c$.

I am implementing the algorithm and started implementing this as nCr but then I noticed the comma. Can anyone explain this notation?

Answer 1

One paragraph above:

Let $\binom{n}{r_1, r_2}$ denote a "trinomial" quantity, i.e. the number of ways of choosing $r_1$ positions of one kind and $r_2$ positions of another kind in a vector of length $n$. It is simple to confirm the following relationship between trinomial and binomial quantities: $\binom{n}{r_1, r_2} = \binom{n}{r_1}\binom{n-r_1}{r_2}$.

In more standard notation, you can express this as the multinomial:

$$ \binom{n}{r_1, r_2, n-r_1-r_2} $$

Answer 2

It looks like a multinomial coefficient.

Answer 3

If it is a multinomial coefficient, then $d_f+d_f=N$, $c+c=2N-y_2$, and $d_f-c+d_f-c=y_2-N$. These three equations are consistent, since in the order I wrote them, the first minus the second gives the third. So that's supporting evidence that you have multinomial coefficients.

What feels strange is that usually with multinomial coefficients that involve selection of two groups, as these would, there is no need to explicitly denote the size of the second group, and you can just use binomial coefficients. In other words, the multinomial coefficient $\binom{X}{a,b}$ is the same as the binomial coefficient $\binom{X}{a}$, since it $b$ can be deduced from $X$ and $a$.