Discrete Math: Combinations Without Repetition

Combinations without Repetition


    1. How many teams of $L$ people can be formed from $N$ people?

      We choose $L$ people from $N$ without regard to order:

      $$ \binom{N}{L} $$

    2. How many teams of $L$ people can be formed from $N$ people if a specific person must be on the team?

      Fix the person, then choose the remaining $L-1$ from the other $N-1$:

      $$ \binom{N-1}{L-1} $$

    3. How many teams of $L$ people can be formed from $N$ people if a specific person cannot be on the team?

      Choose all $L$ people from the remaining $N-1$:

      $$ \binom{N-1}{L} $$

    4. How many teams of $L$ people can be formed from $N$ people if all $k$ specific people must be on the team?

      Fix the $k$ people, then choose the remaining $L-k$:

      $$ \binom{N-k}{L-k} $$

    5. How many teams of $L$ people can be formed from $N$ people if exactly one of two specific people is on the team?

      Choose which one is included (2 ways), then choose the remaining $L-1$ from $N-2$:

      $$ 2\binom{N-2}{L-1} $$

    6. How many teams of $L$ people can be formed from $N$ people if at least one of $k$ specific people is on the team?

      Total minus none of them:

      $$ \binom{N}{L} - \binom{N-k}{L} $$

    7. How many teams of $L$ people can be formed from $N$ people if 2 people are never on the same team?

      We count all teams and subtract those where both are together. Total teams:

      $$ \binom{N}{L} $$ Teams where both are included:

      $$ \binom{N-2}{L-2} $$ Thus the number of valid teams is:

      $$ \binom{N}{L} - \binom{N-2}{L-2} $$

    8. How many teams of $L$ people can be formed from $N$ people if 2 people stick together?

      Let the two people be a pair.

      Case 1: Both are on the team. Then we choose the remaining $L-2$ people from the other $N-2$:

      $$ \binom{N-2}{L-2} $$

      Case 2: Neither is on the team. Then we choose all $L$ people from the other $N-2$:

      $$ \binom{N-2}{L} $$ Total:

      $$ \binom{N-2}{L-2} + \binom{N-2}{L} $$

    9. How many teams of $L$ people can be formed from $N$ people if no two of $k$ specific people can be on the team together?

      We can choose at most one of the $k$ people. Case 1: Choose none:

      $$ \binom{N-k}{L} $$

      Case 2: Choose exactly one of the $k$ (there are $k$ choices), then choose $L-1$ others:

      $$ k\binom{N-k}{L-1} $$ Total:

      $$ \binom{N-k}{L} + k\binom{N-k}{L-1} $$

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