|
PDF
The Catalan numbers $C_{n}=(2 n) ! / n !(n+1) !$ are are well-known integers that arise in many combinatorial problems. The numbers $6(2 n) ! / n !(n+2) !, 60(2 n) ! / n !(n+3) !$, and more generally $(2 r+1) ! / r ! \cdot(2 n) ! / n !(n+r+1) !$ are also integers for all $n$. We study the properties of these numbers and of some analogous numbers that generalize the ballot numbers, which we call super ballot numbers. 1. Introduction
The Catalan numbers
$$
C_{n}=\frac{(2 n) !}{n !(n+1) !}
$$
are well-known integers that arise in many combinatorial problems. The number
$$
\frac{(2 n) !}{n !(n+2) !}
$$
need not be an integer, but
$$
6 \frac{(2 n) !}{n !(n+2) !}=4 C_{n}-C_{n+1}
$$
must be. More generally, we might consider generalized Catalan numbers of the form
$$
J_{r} \frac{(2 n) !}{n !(n+r+1) !}
$$
where $J_{r}$ is chosen so that this quantity is always an integer. It turns out that we may take $J_{r}=(2 r+1) ! / r !$.
Many of the properties of the Catalan numbers generalize easily to the ballot numbers
$$
\frac{k}{2 n+k}\left(\begin{array}{c}
2 n+k \\
n
\end{array}\right),
$$
which reduce to the Catalan numbers for $k=1$. For a recent exposition of the basic combinatorial properties of the Catalan and ballot numbers, with many references, see Hilton and Pederson (1991). Our generalized Catalan numbers also have ballot number analogs, which we call super ballot numbers. They may be given by the formula
$$
g(n, k, r)=\frac{(k+2 r) !}{(k-1) ! r !} \frac{(2 n+k-1) !}{n !(n+k+r) !} .
$$
For $r=0$ they reduce to the ballot numbers. An intriguing problem is to find a combinatorial interpretation for them. Although we do not find such a combinatorial interpretation, we do find many interesting properties of these numbers. One of the most surprising is that they are closely related to the coefficients of $(1-x-y-z+4 x y z)^{-1}$, which have been studied by several authors: Askey (1975), Askey and Gasper (1977), Gillis and Kleeman (1979), Gillis, Reznick, and Zeilberger (1983), Gillis and Zeilberger (1983), Ismail and Tamhankar (1979), and Zeilberger (1981).
Many of the proofs are omitted or only sketched. Once the formulas are found, the proofs are usually straightforward computations, and in fact, if we start at "the right place" nearly all the formulas can be proved quite easily. However, finding the right place to start is the most interesting part of the journey.
Most of the results of this paper were found with the help of the Maple symbolic
algebra programming language.
2. Some CalculationsIt is well known that $(m+n)!$ is always divisible by $m ! n !$; the quotient is the binomial coefficient $\left(\begin{array}{c}m+n \\ n\end{array}\right)$ which counts $m$-element subsets of an $(m+n)$-element set. It is not true in general that $(m+n)!$ is divisible by $(m+1) ! n !$. However if $m=n$ the quotient is the Catalan number $C_{n}=\frac{1}{n+1}\left(\begin{array}{c}2 n \\ n\end{array}\right)$. We can see that $C_{n}$ is an integer by expressing it as a difference of two binomial coefficients:
$$
\frac{1}{n+1}\left(\begin{array}{c}
2 n \\
n
\end{array}\right)=\frac{(n+1)-n}{n+1}\left(\begin{array}{c}
2 n \\
n
\end{array}\right)=\left(\begin{array}{c}
2 n \\
n
\end{array}\right)-\left(\begin{array}{c}
2 n \\
n+1
\end{array}\right)\tag1
$$
We might ask if $(2 n) ! /(n+1) !^{2}$ is always an integer, but its denominator will clearly be divisible by $n+1$ if $n+1$ is a prime, and thus there is no $K$ such that $K(2 n) ! /(n+1) !^{2}$ is an integer for all $n$. The quotient $(2 n) ! / n !(n+2) !$ is more interesting:$$\begin{array}{c|cc}n&0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline{(2n)!\over n!(n+2)!}&1 / 2 & 1 / 3 & 1 / 2 & 1 & 7 / 3 & 6 & 33 / 2 & 143 / 3 & 143 & 442 & 4199 / 3\end{array}$$It seems that the denominators are always 2 or 3 , so
$$
\frac{6}{(n+1)(n+2)}\left(\begin{array}{c}
2 n \\
n
\end{array}\right)\tag2
$$
is apparently always an integer. Let us now try $(2 n) ! / n !(n+3) !$ :$$\begin{array}{c|cc}n&0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline\frac{(2 n) !}{(n+3) ! n !}&1 / 6 & 1 / 12 & 1 / 10 & 1 / 6 & 1 / 3 & 3 / 4 & 11 / 6 & 143 / 30 & 13 & 221 / 6 & 323 / 3\end{array}$$Apparently
$$
\frac{60}{(n+1)(n+2)(n+3)}\left(\begin{array}{c}
2 n \\
n
\end{array}\right)\tag3
$$
is always an integer.
We could prove these observations, and even more precise divisibility results, by using the well-known formula for the power of a prime dividing a factorial. For example, we can show not only that (2) is always an integer, but that it is even unless $n+2$ is a power of 2 and that it is divisible by 3 unless $n$ is congruent to 1 modulo 3 . However, we set off in a more combinatorial direction by generalizing (1).3. Super Ballot NumbersIt is straightforward to check that
$$
3\left(\begin{array}{c}
2 n \\
n
\end{array}\right)-4\left(\begin{array}{c}
2 n \\
n+1
\end{array}\right)+\left(\begin{array}{c}
2 n \\
n+2
\end{array}\right)=6 \frac{(2 n) !}{n !(n+2) !}\tag4
$$
and
$$
10\left(\begin{array}{c}
2 n \\
n
\end{array}\right)-15\left(\begin{array}{c}
2 n \\
n+1
\end{array}\right)+6\left(\begin{array}{c}
2 n \\
n+2
\end{array}\right)-\left(\begin{array}{c}
2 n \\
n+3
\end{array}\right)=60 \frac{(2 n) !}{n !(n+3) !}\tag5
$$
Thus (2) and (3) are integers. To find the pattern, it is useful to consider a generalization. It is well known that the Catalan numbers are special cases of the ballot numbers, which for now we normalize as
$$
\frac{k-1}{n+1}\left(\begin{array}{c}
2 n+k \\
n
\end{array}\right)\tag6
$$
Note that (6) reduces to a Catalan number for $k=2$ and to the negative of a Catalan number for $k=0$. The ballot numbers are integers since
$$
\left(\begin{array}{c}
2 n+k \\
n+1
\end{array}\right)-\left(\begin{array}{c}
2 n+k \\
n
\end{array}\right)=\frac{k-1}{n+1}\left(\begin{array}{c}
2 n+k \\
n
\end{array}\right)
$$To find ballot generalizations of $(4)$ and $(5)$, I used Maple to find coefficients $c_{i}$ (rational functions of $k$ which are independent of $n$ ) satisfying
$$
\sum_{i=0}^{r} c_{i}\left(\begin{array}{c}
2 n+k \\
n+i
\end{array}\right)=\frac{(2 n+k) !}{(n+k) !(n+r) !}
$$
then multiplied through by the denominators to yield a polynomial identity in $k$. I found the following formulas:
\begin{align*}
(k-1)\left(\begin{array}{c}
2 n+k \\
n+2
\end{array}\right)-2(k-2)\left(\begin{array}{c}
2 n+k \\
n+1
\end{array}\right)+&(k-3)\left(\begin{array}{c}
2 n+k \\
n
\end{array}\right) \\
&=\frac{(k-1)(k-2)(k-3)}{(n+1)(n+2)}\left(\begin{array}{c}
2 n+k \\
n
\end{array}\right)\tag7
\end{align*}
\begin{align*}
(k-1)(k-2)\left(\begin{array}{c}
2 n+k \\
n+3
\end{array}\right)-3(k-1)(k-4)\left(\begin{array}{c}
2 n+k \\
n+2
\end{array}\right) \\
+3(k-2)(k-5)\left(\begin{array}{c}
2 n+k \\
n+1
\end{array}\right)-(k-4)(k-5)\left(\begin{array}{c}
2 n+k \\
n
\end{array}\right) \\
= \frac{(k-1)(k-2)(k-4)(k-5)(k-3)}{(n+1)(n+2)(n+3)}\left(\begin{array}{c}
2 n+k \\
n
\end{array}\right)\tag{8}
\end{align*}\begin{align*}
(k-1)(k-2)(k-3)\left(\begin{array}{c}
2 n+k \\
n+4
\end{array}\right)-4(k-1)(k-2)(k-6)\left(\begin{array}{c}
2 n+k \\
n+3
\end{array}\right) \\
+6(k-1)(k-4)(k-7)\left(\begin{array}{c}
2 n+k \\
n+2
\end{array}\right)-4(k-2)(k-6)(k-7)\left(\begin{array}{c}
2 n+k \\
n+1
\end{array}\right) \\
+(k-5)(k-6)(k-7)\left(\begin{array}{c}
2 n+k \\
n
\end{array}\right) \\
=\frac{(k-1)(k-2)(k-3)(k-4)(k-5)(k-6)(k-7)}{(n+1)(n+2)(n+3)(n+4)}\left(\begin{array}{c}
2 n+k \\
n
\end{array}\right)\tag9
\end{align*}
and so on. It is not completely clear from these examples what the general formula is, but by working out a few more cases, we guess that
$$
\sum_{i=0}^{r}(-1)^{r-i}\left(\begin{array}{l}
r \\
i
\end{array}\right) A_{r, i}(k)\left(\begin{array}{c}
2 n+k \\
n+i
\end{array}\right)=\prod_{i=1}^{2 r-1}(k-i) \cdot \frac{(2 n+k) !}{(n+r) !(n+k) !}\tag{10}
$$
where
$$
A_{r, i}(k)=\prod_{j \in S_{r, i}}(k-j)
$$ |
阿鲁
发表于 2016-6-8 23:27
hbghlyj
发表于 2024-10-31 16:54
