Introduction to Discrete Mathematics

For \(n\in\mathbb{N}\text{,}\) we define \({[n]:=\{1,2,\ldots,n\}}\text{.}\) That is, \([n]\) is just clever shorthand for the set containing 1 through \(n\text{.}\) This notation is meant to resemble interval notation.

For \(k\in\mathbb{N}\) and a nonempty set \(A\text{,}\) a \(k\)-permutation of \(A\) is an injective function \(w:[k]\to A\text{.}\) The set of all \(k\)-permutations of \(A\) is denoted by \({S_{A,k}}\text{.}\) If \(A\) happens to be the set \([n]\text{,}\) we use the notation \({S_{n,k}}\text{.}\) And if \(n=k\text{,}\) we write \({S_n:=S_{n,n}}\) and refer to each \(n\)-permutation in \(S_n\) as a permutation. Let \({P(n,k):=|S_{n,k}|}\text{.}\) By convention, we set \({P(n,0):=1}\text{,}\) including the case when \(n=0\text{.}\)

The game of chess is played on an \(8\times 8\) grid. We will consider chessboards with arbitrary dimensions, say \(n\times k\) (\(n\) rows, \(k\) columns) with \(1\leq k \leq n\text{.}\) A rook is a castle-shaped piece that can move horizontally or vertically any number of squares. In a typical chess game, there are two black rooks and two white rooks, but for our purposes we will assume we have \(k\) rooks, where all the rooks are the same color. We say that an arrangement of rooks on an \(n\times k\) chessboard is non-attacking if no two rooks lie in the same row or column. Figure 3.1 shows one possible non-attacking rook arrangement on an \(6\times 4\) chessboard.

Recall that for \(n\in\mathbb{N}\text{,}\) the factorial of \(n\) is defined \({n!:=n\cdot (n-1)\cdots 2\cdot 1}\text{,}\) and we define \({0!:=1}\) for convenience.

Do you see why this \(4\)-permutation corresponds to the non-attacking rook arrangement in Figure 3.1?

The formula in the previous problem is an example of a recurrence relation, which will be a topic of focus in a later chapter.

Interpreting a permutation as a linearly ordered arrangement of objects (i.e., string), a circular permutation is similar to a permutation except the objects are arranged on a circle, so that there is no beginning or end. An example of a circular permutation of length 8 is given in Figure 3.2. Any circular rotation yields the same circular permutation. However, for \(n\geq 3\text{,}\) reversing the relative order of the elements (i.e., encountering the same numbers counterclockwise instead of clockwise) yields a different circular permutation. Do you see why we included the restriction on \(n\) in the previous sentence?

We encountered circular permutations back in Problem 1.39 when we counted circular seating arrangements of six friends sitting around a circle to play a game. Recall that the trick in that problem was to make use of the Division Principle.

Moving away from circular permutations and back to \(k\)-permutations, recall that we can represent each \(k\)-permutation of \([n]\) as a string of length \(k\text{,}\) where each entry is from \([n]\) and no repeats are allowed. What if we allow repeats?

Consider a set of \(n\) objects that are not necessarily distinct, with \(p\) different types objects and \(n_i\) objects of type \(i\) (for \(i=1,2,\ldots, p\)), so that \(n=n_1+\cdots +n_p\text{.}\) An ordered arrangement of these \(n\) objects is called a generalized permutation and the number of such arrangements is denoted by \({P(n;n_1,\ldots,n_p)}\text{.}\) For example, the number of words we can make out of the letters of POPPY is \(P(5;3,1,1)\text{.}\) The following theorem follows immediately from the Division Principle.