Discrete Mathematics: II Combinations with Repetition

Combinations with Repetition


  1. How many combinations are there for \(N\) dice with \(S\) sides \(1, \ldots, S\)?

    Let \(X_1, \ldots, X_S\) represent the number of dice with each face value. Then:

    $$ X_1 + \ldots + X_S = N, \quad X_i \ge 0 $$

    This is a stars and bars problem with \(N\) stars and \(S-1\) bars. So:

    $$ \binom{N+S-1}{S-1} $$


  2. How many combinations are there for \(N\) dice with \(S\) sides \(1, \ldots, S\) such that the face value \(1\) appears exactly \(K\) times?

    Let \(X_1, \ldots, X_S\) represent counts. Then:

    $$ X_2 + \ldots + X_S = N-K, \quad X_i \ge 0 $$

    Stars and bars:

    $$ \binom{N-K+S-2}{S-2} $$


  3. How many combinations are there for \(N\) dice with \(S\) sides \(1, \ldots, S\) such that the face value \(1\) appears at least \(K\) times?

    Let:

    $$ X_1 + \ldots + X_S = N, \quad X_1 \ge K $$

    Set \(Y_1 = X_1 - K \ge 0\):

    $$ Y_1 + X_2 + \ldots + X_S = N-K $$

    Stars and bars:

    $$ \binom{N-K+S-1}{S-1} $$


  4. How many combinations are there for \(N\) dice with \(S\) sides \(1, \ldots, S\) such that the maximum value of the dice is \(M\)?

    Let:

    $$ X_1 + \ldots + X_M = N, \quad X_M \ge 1 $$

    Set \(Y_M = X_M - 1 \ge 0\):

    $$ X_1 + \ldots + Y_M = N-1 $$

    Stars and bars:

    $$ \binom{N-1+(M-1)}{M-1} = \binom{N+M-2}{M-1} $$


  5. How many combinations are there for \(N\) dice with \(S\) sides \(1, \ldots, S\) such that the minimum value of the dice is \(M\)?

    Let:

    $$ X_M + \ldots + X_S = N, \quad X_M \ge 1 $$

    Set \(Y_M = X_M - 1 \ge 0\):

    $$ Y_M + X_{M+1} + \ldots + X_S = N-1 $$

    Stars and bars:

    $$ \binom{N+S-M-1}{S-M} $$


  6. How many combinations are there for \(N\) dice with \(S\) sides \(1, \ldots, S\) that uses \(K\) distinct face values?

    Choose faces:

    $$ \binom{S}{K} $$

    Let each appear at least once:

    $$ X_1 + \ldots + X_K = N, \quad X_i \ge 1 $$

    Set \(Y_i = X_i - 1\):

    $$ Y_1 + \ldots + Y_K = N-K $$

    Stars and bars:

    $$ \binom{N-K+(K-1)}{K-1} = \binom{N-1}{K-1} $$

    Final answer:

    $$ \binom{S}{K}\binom{N-1}{K-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