3.4 Factorials and Permutations

Class: CSE 16 Subject: computer-science discrete-math Date: 2024-10-14 Teacher: Prof. Musacchio

Counting

Factorial

• If $n$ is a non-negative integer, then $n!$ is the number of lists of length n that can be made from n symbols, without repetition. Thus $0!$ = 1 and $1!$ = 1. If $n>1$, then $n!$ = n(n − 1)(n − 2) · · · 3 · 2 · 1.

Permutation

• a permutation of a set is an arrangement of all of the set’s elements in a row, that is, a list without repetition that uses every element of the set. For example, the permutations of the set $X$ = {1, 2, 3} are the six lists:
  • 123, 132, 213, 231, 312, 321.
• a function in python is defined by jsvaskvn

k-permutation

• Assume a set called $X$:
• a k-permutation is a non-repetitive list made from k elements of X .

General Formula

• if $0\le k\le n$ $\mathbb{P}(n,k)=\frac{n!}{(n-k)!}$
• n is the set and k is how many we’re choosing

Other Formula

• if $k>0$ $n!$

Example

• You deal five cards off of a standard 52-card deck, and line them up in a row. How many such lineups are there that either consist of all red cards, or all clubs? Solution:
• There are 26 red cards. The number of ways to line up five of them is $\mathbb{P}(26,5)$ = 26 · 25 · 24 · 23 · 22 = 7, 893, 600.
• There are 13 club cards (which are black). The number of ways to line up five of them is $\mathbb{P}(13,5)$ = 13 · 12 · 11 · 10 · 9 = 154, 440.
• By the addition principle, the answer to our question is that there are $\mathbb{P}(26,5)$ + $\mathbb{P}(13,5)$ = 8, 048, 040 lineups that are either all red cards, or all club cards.