Discrete Math: Permutations Without Repetition

Permutations without Repetition


  1. How many ways are there to permute $n$ objects in a line?

    To permute $n$ distinct objects in a line, we choose an ordering step by step. There are $n$ choices for the first position, $n-1$ for the second, ..., and $1$ for the last. Thus the total number of permutations is:

    $$ n(n-1)(n-2)\cdots 1 = n! $$

  2. How many ways are there to permute $k$ out of $n$ objects in a line?

    To permute $k$ out of $n$ distinct objects in a line, we first choose and then order the objects. There are $n$ choices for the first position, $n-1$ for the second, ..., and $n-k+1$ for the $k$-th position. Thus the total number of ways is:

    $$ n(n-1)(n-2)\cdots(n-k+1) $$ This is written using factorials as:

    $$ \frac{n!}{(n-k)!} $$

  3. How many ways are there to permute $n$ objects in a circle?

    To permute $n$ distinct objects in a circle, arrangements that differ only by rotation are considered the same. We fix one object to remove rotational symmetry, leaving $n-1$ objects to arrange in a line. Thus the number of circular permutations is:

    $$ (n-1)! $$

  4. How many ways are there to permute $k$ out of $n$ objects in a circle?

    First choose $k$ objects from $n$:

    $$ \binom{n}{k} $$ Then arrange the $k$ chosen objects in a circle:

    $$ (k-1)! $$ Thus:

    $$ \binom{n}{k}(k-1)! $$ Equivalently:

    $$ \frac{n!}{(n-k)!\,k} $$

  5. How many ways are there to permute $n$ objects in a line if $z$ of them cannot be adjacent?

    First arrange the $n-z$ remaining objects:

    $$ (n-z)! $$ These create $n-z+1$ gaps:

    $$ \_\,A\,\_\,A\,\_ \cdots A\,\_ $$ Choose $z$ of these gaps and permute the $z$ special objects:

    $$ \binom{n-z+1}{z} \cdot z! $$ Thus:

    $$ (n-z)! \binom{n-z+1}{z} z! $$ Equivalently:

    $$ \frac{(n-z+1)!}{(n-2z+1)!} $$

  6. How many ways are there to permute $n$ objects in a circle if $z$ of them cannot be adjacent?

    First arrange the $n-z$ non-special objects in a circle:

    $$ (n-z-1)! $$ This creates $n-z$ gaps:

    $$ \_\,A\,\_\,A\,\_ \cdots A\,\_ $$ Choose $z$ gaps and permute the $z$ special objects:

    $$ \binom{n-z}{z}\cdot z! $$ Thus:

    $$ (n-z-1)! \binom{n-z}{z} z! $$ Equivalently:

    $$ \frac{(n-z)!}{(n-2z)!} $$

Comments

Post a Comment

Popular posts from this blog

Linear Algebra: IX The Fundamental Theorem of Linear Algebra

Image
The Fundamental Theorem of Linear Algebra Consider a linear transformation $T: \mathbb{R}^n \rightarrow \mathbb{R}^m$ defined by $T(\vec{x}) = A\vec{x}$ where $A$ is an $m$ by $n$ matrix. The row echelon form and reduced row echelon form of a matrix described below are products of $m$ by $m$ elementary matrices (row operations) times $A$ / compositions of linear transformations with these elementary matrices and $A$. Row Echelon Form (REF) An $m$ by $n$ matrix $A$ is in row echelon form , denoted $\text{REF}(A)$, if: Each row has a non-zero leading entry called its pivot . The next pivot is to the right of the previous pivot above it. Every entry below each pivot is zero. All zero rows are at the bottom. A free variable of $A$ is a variable in the equation $T(\vec{x}) = A\vec{x} =\vec{0}$. The number of free variables is the number of columns without pivots in $\text{REF}(A)$. Reduced Row Echelon Form (RREF) An $m$ by $n$ matri...
Read more

Linear Algebra: III Square and Inverse Matrices

Square and Inverse Matrices An $n$ by $n$ square matrix has the same number of rows and columns: $$ A = \begin{bmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{bmatrix} $$ If $A$ is an $n$ by $n$ square matrix and $\vec{x} \in \mathbb{R}^n$, then the product $A\vec{x}$ is also a vector in $\mathbb{R}^n$, defining a linear transformation $T: \mathbb{R}^n \to \mathbb{R}^n$. The Identity Matrix The identity matrix $I$ is an $n$ by $n$ square matrix with 1s on the main diagonal and 0s elsewhere: $$ I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix} $$ It satisfies: $$ AI = IA = A $$ Inverse Matrices The inverse of a square matrix $A$, denoted $A^{-1}$, is a matrix such that: $$ A A^{-1} = A^{-1} A = I $$ Which may not exist. If $A^{-1}$ exists, then $A$ is ...
Read more

Linear Algebra: VII Orthonormal Matrices

Orthonormal Matrices A square $n$ by $n$ matrix $Q$ is called orthonormal if: $$ QQ^\top = Q^\top Q = I $$ $$ Q^{-1} = Q^\top $$ The columns $\vec{q}_1, \ldots, \vec{q}_n$ of $Q$ (and the rows) form an orthonormal basis of $\mathbb{R}^n$: $$ \vec{q}_i^\top \vec{q}_j = 0 \text{ if } i \neq j, \quad \|\vec{q}_i\| = 1 $$ Orthonormal Matrix Properties An orthonormal matrix preserves inner products / dot products: $$ (Q\vec{x})^\top(Q\vec{y}) = \vec{x}^\top Q^\top Q \vec{y} = \vec{x}^\top I \vec{y} = \vec{x}^\top \vec{y} $$ An orthonormal matrix also preserves magnitude: $$ \|Q\vec{x}\|^2 = (Q\vec{x})^\top Q\vec{x} = \vec{x}^\top Q^\top Q \vec{x} = \vec{x}^\top I \vec{x} = \vec{x}^\top \vec{x} = \|\vec{x}\|^2 $$ So an orthonormal matrix preserves angles between vectors: $$ \cos{\theta} = \frac{(Q\vec{x})^\top(Q\vec{y})}{\|Q\vec{x}\|\|Q\vec{y}\|} = \frac{\vec{x}^\top \vec{y}}{\|\vec{x}\|\|\vec{y}\|} $$ There are two special types of o...
Read more