info prev up next book cdrom email home

Roman Coefficient

A generalization of the Binomial Coefficient whose Notation was suggested by Knuth,

\begin{displaymath}
\left\lfloor{\matrix{n\cr k\cr}}\right\rceil ={\left\lfloor{...
...\left\lfloor{k}\right\rceil !\left\lfloor{n-k}\right\rceil !}.
\end{displaymath} (1)

The above expression is read ``Roman $n$ choose $k$.'' Whenever the Binomial Coefficient is defined (i.e., $n\geq
k\geq 0$ or $k\geq 0>n$), the Roman coefficient agrees with it. However, the Roman coefficients are defined for values for which the Binomial Coefficients are not, e.g.,
$\displaystyle \left\lfloor{\begin{array}{c}n\\  -1\end{array}}\right\rceil$ $\textstyle =$ $\displaystyle {1\over\left\lfloor{n+1}\right\rceil }$ (2)
$\displaystyle \left\lfloor{\begin{array}{c}0\\  k\end{array}}\right\rceil$ $\textstyle =$ $\displaystyle {(-1)^{k+(k>0)}\over\left\lfloor{k}\right\rceil },$ (3)

where
\begin{displaymath}
n<0\equiv\cases{
1 & for $n<0$\cr
0 & for $n\geq 0$.\cr}
\end{displaymath} (4)


The Roman coefficients also satisfy properties like those of the Binomial Coefficient,

\begin{displaymath}
\left\lfloor{\matrix{n\cr k\cr}}\right\rceil =\left\lfloor{\matrix{n\cr n-k\cr}}\right\rceil
\end{displaymath} (5)


\begin{displaymath}
\left\lfloor{\matrix{n\cr k\cr}}\right\rceil \left\lfloor{\m...
...right\rceil \left\lfloor{\matrix{n-r\cr k-r\cr}}\right\rceil ,
\end{displaymath} (6)

an analog of Pascal's Formula
\begin{displaymath}
\left\lfloor{\matrix{n\cr k\cr}}\right\rceil =\left\lfloor{\...
...ight\rceil +\left\lfloor{\matrix{n-1\cr k-1\cr}}\right\rceil ,
\end{displaymath} (7)

and a curious rotation/reflection law due to Knuth
\begin{displaymath}
(-1)^{k+(k>0)}\left\lfloor{\matrix{-n\cr k-1\cr}}\right\rceil =(-1)^{n+(n>0)}\left\lfloor{\matrix{-k\cr n-1\cr}}\right\rceil
\end{displaymath} (8)

(Roman 1992).

See also Binomial Coefficient, Roman Factorial


References

Roman, S. ``The Logarithmic Binomial Formula.'' Amer. Math. Monthly 99, 641-648, 1992.




© 1996-9 Eric W. Weisstein
1999-05-25