Discrete Mathematics: Permutations Without Repetition

Permutations Without Repetition

1. How many ways are there to permute \(N\) objects in a line?



Example. $N=3$



$$\boxed{N!}$$

2. How many ways are there to permute \(N\) objects in a circle clockwise?



Example. $N=4$



$$\boxed{(N-1)!}$$

3. How many ways are there to permute \(K\) out of \(N\) objects in a line?



Example. $N=4, K=3$



$$\boxed{\frac{N!}{(N-K)!}}$$

4. How many ways are there to permute \(K\) out of \(N\) objects in a circle clockwise?



Example. $N=4, K=3$



$$\boxed{\frac{N!}{K (N-K)!}}$$

5. How many ways are there to permute \(N\) objects in a line if \(Z\) of them cannot be adjacent? Hint: Consider the gaps between the remaining objects.



Example. $N=3, Z=2$ ($A$ and $B$)



$$\boxed{(N-Z)!\binom{N-Z+1}{Z}Z!}$$

6. How many ways are there to permute \(N\) objects in a circle if \(Z\) of them cannot be adjacent? Hint: Consider the gaps between the remaining objects.



Example. $N=4, Z=2$ ($A$ and $B$)



$$\boxed{(N-Z-1)!\binom{N-Z}{Z}Z!}$$

7. How many ways are there to permute \(N\) objects in a line if no object stays in its original position? Hint: Use the Inclusion-Exclusion Principle
$$ \left| \bigcap_{i=0}^{K} A_i^c \right| = |T| - \sum_{i=0}^{K} |A_i| $$ $$ + \sum_{0 \le i_1 < i_2 \le K} |A_{i_1} \cap A_{i_2}| - \ldots $$ $$ + (-1)^{K+1} \sum_{0 \le i_1 < \ldots < i_{K} \le K} \left| A_{i_1} \cap \cdots \cap A_{i_{K}} \right| $$


where \(T\) is the total set of permutations and \(A_i\) is the set of permutations where the \(i\)th object stays fixed.




Example. $N=3$, Original Position $(A,B,C)$



$$ \boxed{ D_N = N!\sum_{k=0}^{N}\frac{(-1)^k}{k!} } $$

8. How many ways are there to permute \(N\) objects in a circle if no object stays in its original position?



Example. $N=4$, Original Position: $(A,B,C,D)$



$$\boxed{\frac{D_N}{N} = (N-1)!\sum_{k=0}^{N}\frac{(-1)^k}{k!}}$$