Discrete Mathematics: I Permutations with Repetition

Permutations with Repetition


  1. How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0, \ldots, N-1\)?

    There are \(N\) outcomes for all \(L\) digits so:

    $$ N^L $$


  2. How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0, \ldots, N-1\) without leading zero?

    There are \(N-1\) outcomes for the digit with greatest place value and \(N\) outcomes for the rest of the digits so:

    $$ (N-1)N^{L-1} $$


  3. How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0, \ldots, N-1\) where the digit \(1\) appears \(K\) times?

    There are \(\binom{L}{K}\) possible combinations of positions for the \(1\)s that appear \(K\) times. For the remaining \(L-K\) digits, there are \((N-1)^{L-K}\) possible combinations. Therefore:

    $$ \binom{L}{K}(N-1)^{L-K} $$


  4. How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0, \ldots, N-1\) where the digit \(1\) appears at least \(K\) times?

    Add all possible combinations where the digit \(1\) appears \(K, \ldots, L\) times so:

    $$ \sum_{i=K}^{L} \binom{L}{i}(N-1)^{L-i} $$

    Equivalently:

    $$ N^L - \sum_{i=0}^{K-1} \binom{L}{i}(N-1)^{L-i} $$


  5. How many distinct strings of length \(L\) are there in a system with \(N\) digits \(0, \ldots, N-1\) with no two consecutive \(1\)s?

    Let \(f(L)\) be the number of valid strings. Then \(f(1)=N\), \(f(2)=N^2-1\).

    Case 1: Last digit is not \(1\):
    \((N-1)f(L-1)\)

    Case 2: Last digit is \(1\) and previous is not \(1\):
    \((N-1)f(L-2)\)

    Therefore:

    $$ f(L) = (N-1)f(L-1) + (N-1)f(L-2) $$

    with \(f(1)=N\), \(f(2)=N^2-1\).


  6. How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0, \ldots, N-1\) that uses \(K\) distinct digits?

    First choose the \(K\) digits: \(\binom{N}{K}\).

    Fix a set of \(K\) digits and use inclusion–exclusion:

    $$ \sum_{j=0}^{K} (-1)^j \binom{K}{j}(K-j)^L $$

    Multiplying:

    $$ \binom{N}{K} \sum_{j=0}^{K} (-1)^j \binom{K}{j}(K-j)^L $$


  7. How many distinct strings of length \(L\) can be formed using digits \(0,1,\ldots,N-1\) where each digit \(i\) appears exactly \(n_i\) times (so \(n_0+n_1+\cdots+n_{N-1}=L\))?

    This is a multiset permutation problem. We are arranging a total of \(L\) digits, but some digits are identical, so swapping identical digits does not create a new string.

    If all digits were distinct, there would be \(L!\) permutations. However, we must correct for overcounting caused by identical digits. For each digit \(i\), we divide by \(n_i!\).

    Therefore, the number of distinct strings is:

    $$ \frac{L!}{n_0!\,n_1!\cdots n_{N-1}!} $$

Comments

Post a Comment

Popular posts from this blog

Linear Algebra: IX The Fundamental Theorem of Linear Algebra

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$ matrix ...
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