Counting - 2
Sums and Products of a Sequence
Given a sequence of numbers:
\[a_1,a_2,\ldots,a_m,\ldots,a_n\]we can use the notation:
- $\sum^n_{i=m}a_i$ to represent $a_m+\ldots+a_n$.
- $\prod^n_{i=m}a_i$ to represent $a_m\times\ldots\times a_n$.
Following from this you could combine indexes to make multiple iteration:
\[\sum^5_{i=1}\sum^5_{j=i}(i+5)\]Here you would apply the sum using $j$ for each sum using $i$. The lower bound for the inner sum would increase every time to match the incrementing $i$.
Special Case $m=n$
\(\sum^n_{i=m}=a_m\)
Here you would just state the element at that index in the list.
Sums and Products Over Sets of Indices
Let $f:D\rightarrow\Bbb R$ be a function with some domain $D$. Then for $S\subseteq D$:
-
$\sum_{i\in S}f(i)$ denotes the sum of $f(i)$ over all $i\in S$.
-
$\prod_{i\in S}f(i)$ denotes the product of $f(i)$ over all $i\in S$.
Example
Suppose that the domain $D=\{a,b,c,d\}$. Additionally there is a function $f:D\rightarrow\Bbb R$
\[\begin{aligned} f(a)&=0&f(b)&=1\\ f(c)&=0.3&f(d)&=-1 \end{aligned}\]To find the sum of all the elements in $D$ with the function applied to them would be:
\[\sum_{i\in D}f(i)=0+1+.3-1=.3\]The same applies to products.
The Factorial Function
The product $\prod^n_{i=1}i$ comes up so often that is has a name. it is called $n$ factorial and is written as $n!$.
As $i=1$ then $0!=1$.
Permutations
A permutation of a set is just an ordering of its elements.
By the product rule the number of permutations of an $n$-element set is $n!$.
- This is because there are $n$ choices for the first element, then $n-1$ choices for the 2nd element, then $n-2$ choices for the 3rd element and so on.
- Therefore the number of permutations of a list of 3 elements would be $3!=6$
$k$-Permutations
A selection of $k$ distinct elements of a set, where order matters is called a $k$-permutation of the set.
The number $k$-permutations of an $n$-element set is:
\[\begin{aligned} P(n,k)&=n\times(n-1)\times\ldots\times(n-(k-1))\\ &=\frac{n!}{(n-k)!} \end{aligned}\]From the example last lecture, the number of combinations of three elements from a set of five elements where order matters is $P(5,3)=$ $5\times4\times3$.
Notable Example
I have a jar with 3 different sweet. Three children come in, and each take one. How many different outcomes are there?
\[P(3,3)=3\times2\times1=\frac{3!}{0!}=6\]This is an example of why $0!$ is 1.
Additionally, if the factorial is too large to calculate, you can cancel out values in the numerator and denominator to get a more manageable number.
Counting $k$-Combinations
A size-$k$ subset is called a $k$-combination.
The number of $k$-combinations of a set of size $n$ is:
\[C(n,k)=\frac{n!}{(n-k)!k!}\]Proof
- The number of $k$-permutations of the set is $P(n,k)=\frac{n!}{(n-k)!}$.
- A $k$-permutation is an ordering of $k$ distinct elements of the set.
- Each size-$k$ subset has $k!$ orderings, so it corresponds to $P(k,k)=k!$ of the $k$ permutations.
- By the division rule, $C(n,k)=\frac{P(n,k)}{P(k,k)}=\frac{n!}{(n-k)!k!}$.
This is to say that by dividing out the repeat values we are left with just distinct values.