Special Counting Sequences

Theorem 9.1

#

The number of sequences

\begin{equation} \label{8.1} a_1, a_2, \ldots , a_{2n} \end{equation}

1

of \(2n\) terms that can be formed by using exactly \(n\) +1s and exactly \(n\) -1s whose partial sums are always positive:

\begin{equation} \label{8.2} a_1 + a_2 + \cdots + a_{k} \geq 0, \qquad (k = 1, 2, \ldots , 2n) \end{equation}

2

equals the nth Catalan number

\begin{align*} C_n = \frac{1}{n+1} \binom {2n}{n}, \qquad (n \geq 0). \end{align*}

Theorem 9.2

#

Let the geneml term of a sequence be a polynomial of degree \(p\) in \(n\):

\[ h_n = a_pn^p + a_{p-1}n^{p-1} + \cdots + a_1n + a_0, \qquad (n \geq 0). \]

Then \(\Delta ^{p+1}h_n = 0\) for all \(n \geq 0\).

Theorem 9.3

#

The geneml term of the sequence whose difference table has its Oth diagonal equal to

\[ c_0, c_1, c_2, \ldots , c_p, 0, 0, 0, \ldots , \qquad \text{where} c_p \neq 0 \]

is a polynomial in n of degree \(p\) satisfying

\begin{equation} \label{8.12} h_n = c_0\binom {n}{0} + c_1\binom {n}{1} + c_2\binom {n}{2} + \cdots + c_p\binom {n}{p}. \end{equation}

3

Theorem 9.4

#

Assume that the sequence \(h_0, h_1, h_2, \ldots , h_n, \ldots \) has a difference .table whose Oth diagonal equals

\[ c_0, c_1, c_2, \ldots , c_p, 0, 0, 0, \ldots . \]

Then

\begin{equation} \sum \limits _{k = 0}^{n}h_k = c_0\binom {n+1}{1} + c_1\binom {n+1}{2} + c_2\binom {n+1}{3} + \cdots + c_p\binom {n+1}{p+1}. \end{equation}

4

Theorem 9.5

#

If \(1 \leq k \leq p- 1\), then

\[ S(p, k) = kS(p-1, k) + S(p-1, k-1) \]

Theorem 9.6

#

The Stirling number of the second kind \(S(p, k)\) counts the number of partitions of a set of \(p\) elements into \(k\) indistinguishable boxes in which no box is empty.

Theorem 9.7

#

For each integer \(k\) with \(0 \leq k \leq p\), we have

\[ S^{\# }(p, k) = \sum \limits _{t = 0}^{k} (-1)^t \binom {k}{t}(k-t)^p \]

hence,

\[ S(p, k) = \frac{1}{k!}\sum \limits _{t = 0}^{k} (-1)^t \binom {k}{t}(k-t)^p \]

Theorem 9.8

#

If \(p \geq 1\), then

\[ B_p = \binom {p-1}{0}B_0 + \binom {p-1}{1}B_1 + \cdots + \binom {p-1}{p-1}B_{p-1}. \]

Theorem 9.9

#

If \(1 \leq k \leq p- 1\), then

\[ s(p, k) = (p-1)s(p-1, k) + s(p-1, k-1). \]

Theorem 9.10

#

The Stirling number \(s(p, k)\) of the first kind counts the number of arrangements of \(p\) objects into \(k\) nonempty circular permutations.

Theorem 9.11

#

Let \(n\) be a positive integer. Let \(p_n^s\) equal the number of self-conjugate partitions of \(n\), and let \(p_n^t\) be the number of partitions of \(n\) into distinct odd parts. Then

\[ p_n^s = p_n^t. \]

Theorem 9.12

#

Let \(n\) be a positive integer. Let \(p_n^{\textbf{o}}\) be the number of partitions of \(n\) into odd parts, and let \(p_n^{\textbf{d}}\) be the number of partitions of \(n\) into distinct parts. Then

\[ p_n^{\textbf{o}} = p_n^{\textbf{d}}. \]

Theorem 9.13

#

\[ \sum \limits _{n=0}^{\infty }p_nx^n = \prod \limits _{k=1}^{\infty }(1-x^k)^{-1} \]

Theorem 9.14

#

Lexicographic order is a linear extension of the partial order of majorization on the set \(\mathcal{P}_n\) of partitions of a positive integer \(n\).

Theorem 9.15

#

Let \(n\) be a positive integer. Let \(p_n^{\prime }\) be the number of partitions of \(n\) into an even number of distinct parts, and let \(p_n^{\prime \prime }\) be the number of partitions of \(n\) into an odd number of distinct parts. Then

\[ p_n^{\prime } = p_n^{\prime \prime } \]

where \(e_n\) is an error term given by \(e_n = (-1)^j\) if \(n\) is of the form \(j(3j\pm 1)/2\), and 0 otherwise.

Theorem 9.16

#

The number of rectangular lattice paths from \((r, s)\) to \((p, q)\) equals the binomial coefficient

\[ \binom {p-r+q-s}{p-r} = \binom {p-r+q-s}{q-s} \]

Theorem 9.17

#

Let \(n\) be a nonnegative integer. Then the number of subdiagonal rectangular lattice paths from \((0,0)\) to \((n, n)\) equals the \(n\)th Catalan number

\[ C_n = \frac{1}{n+1}\binom {2n}{n}. \]

Theorem 9.18

#

Let \(p\) and \(q\) be positive integers with \(p \geq q\). Then the number of subdiagonal rectangular lattice paths from \((0,0)\) to \((p, q)\) equals

\[ \frac{p-q+1}{p+1}\binom {p+q}{q}. \]

Theorem 9.19

#

Let \(r \leq \min \{ p, q\} \). Then

\[ K(p, q : rD) = \begin{pmatrix} & p+q-r & \\ p-r & q-r & r \end{pmatrix} = \frac{(p+q-r)!}{(p-r)!(q-r)!r!}, \]

and

\[ K(p,q) = \sum \limits _{r=0}^{\min \{ p, q\} }\frac{(p+q-r)!}{(p-r)!(q-r)!r!}. \]

Theorem 9.20

#

Let \(p\) and \(q\) be positive integers with \(p \geq q\), and let \(r\) be a nonnegative integer with \(r \leq q\). Then

\begin{align*} R(p, q : rD) & = \frac{p-q+1}{p-r+1}\frac{(p+q-r)!}{r!(p-r)!(q-r)!} \\ & = \frac{p-q+1}{p-r+1} \begin{pmatrix} & p+q-r & \\ r & (p-r) & (q-r) \end{pmatrix}\end{align*}

and

\[ R(p, q)=\sum \limits _{r=0}^q \frac{p-q+1}{p-r+1} \frac{(p+q-r)!}{r!(p-r)!(q-r)!} \]

Theorem 9.21

#

The generating function for the sequence (\(s_n: n \geq 1\)) of small Schroder numbers is

\[ \sum \limits _{n=1}^{\infty } s_n x^n=\frac{1}{4}\left(1+x-\sqrt{x^2-6 x+1}\right). \]

Theorem 9.22

#

The generating function for the sequence (\(R_n: n \geq 0\)) of large Schroder numbers is

\[ \sum \limits _{n=0}^{\infty } R_n x^n=\frac{1}{2x}\left(-(x - 1)-\sqrt{x^2-6 x+1}\right). \]

Theorem 9.24

#

Let \(n\) be a positive integer. Then the number of dissections of a convex polygonal region of \(n + 1\) sides equals the small Schroder number \(s_n\).

Combinatorics

9 Special Counting Sequences