---
tags: NTNU,CSIE,必修,Discrete Mathematics
title: Counting
description:
---

{%hackmd @NTNUCSIE112/S1VbPN1HU %}

# Counting
##### e.g.
> In how many ways can a total number of 6 attendees of the meeting be listed (from top to bottom)?
## Permutation
Assume that you have $n$ distinct objects.
An **ordered** arrangement of $r$ elements of them is called an **$r$-permutation**.
The numver of r-permutations is $n(n-1)(n-2)...(n-r+1)$, denoted by $P(n,r)$;namely $P(n,r) = \frac{n!}{(n-r)!}$

##### e.g.
>In how many ways can we select three members from a group of six people to be listed?
>
Ans. $P(6,3) = 120$
## Combination
Assume that you have $n$ distinct object.
An **unsorted** selection of $r$ objects from them is an **$r$-combination**.
The number of r-combination is $\frac{P(n,r)}{r!}$,denoted C(n,r), or simple ${n \choose r}$.
$\to {n \choose r}$
(e.g. {a,b,c}(n=3), r= 2) $\to$ {ab;ba}, {ac,ca},{bc,cb})
(Any r-permutation(of the r selected ones) corresponds to an identical r-combination.)

##### e.g.
- How many poker hands of five card can be dealt from a standard deck of 52 cards?
$\to {52\choose 5}$
- How many poker hands of 47 card can be dealt from a standard deck of 52 cards?
$\to {52\choose 47}$

$\to {n \choose r} = {n \choose n-r}$

##### e.g.
- How many bit strings of length $n$ are there?
$\to 2^n$
- How many bit strings of length $n$ containing exactly $r$ $1$s are there?
$\to {n \choose r}$
- How many bit strings of length $n$ containing an even number of $1$s are there?
$\to {n \choose 0}+ {n\choose 2} + {n\choose 4} +{n\choose 6}+\cdots {n\choose x}$ (if x=n if n is even, n-1 o.w.)
- another idea: there are half of the $2^n$ strings contain an even number of $1$s.
Any string starts with either 0 or 1.$\to 2^{n-1}$

## Binomial theorem
$(x+y)^n = {n\choose 0}x^0y^n + {n\choose 1}x^1y^{n-1}+{n\choose 2}x^2y^{n-2}+\cdots+{n\choose {n-1}}x^{n-1}y^{1}+ {n \choose n}x^ny^0$

e.g.
- $(x+y)^2 = x^2 + 2xy +y^2$
- $(x+y)^3 = y^3+3xy^2+3x^2y+x^3$
$\to (x+y)(x+y)(x+y)(x+y)(x+y)\cdots (x+y)$

$\to {n\choose 0}+{n\choose 2}+ {n\choose 4}+{n\choose 6}+\cdots {n\choose x} \iff 2^{n-1}$
- x= -1, y = 1
$\to {n\choose 0}-{n\choose 1}+ {n\choose 2}-{n\choose 3}+{n\choose 4} -\cdots +{n\choose {n-1}}(-1) + {n\choose n}(-1^n)$
- x= 1, y = 1
$\to {n\choose 0}+{n\choose 1}+ {n\choose 2}+{n\choose 3}+{n\choose 4} +\cdots +{n\choose {n-1}} + {n\choose n}$

### Pascal's identity

${n\choose k} = {n-1\choose {k-1}}+{{n-1}\choose k }$

### Vandermonde's identity

${\binom {n+m}{k}}=\sum _{i=0}^{k}{\binom {n}{i}}{\binom {m}{k-i}}$

### Place objects in boxes
- Objects : distinguishable, indistinguishable
- Boxes : distinguishable, indistinguishable
#### Placing $n$ **distinguishable** objects into $r$ **distinguishable** boxes
$\to r^n$
- such that box $i$ contains exactly $n_i$ objects $(n\geq 0)$and $\sum_in_i =n$
$\to \frac{n!}{n_1!m_2!\cdots n_r!}$
$P(n,r') \to n \text{ distinguishable objects into } r = r'+1 \text{ boxes, where }n_1=n_2=\cdots = n_{r'}=1\text{, and }n_{r'+1} = n-r'$
$C(n,r') \to n \text{ distinguishable objects into }2\text{ boxes, where }n_1=r' \text{ and } r_2 = n - r'$

#### Placing $n$ **indistinguishable** objects into $r$ **distinguishable** boxes
- $\text{how many solutions of }x_1 +x_2+\cdots + x_r = n \text{ are there?}$
$\to \frac{(n+r-1)!}{n!(r-1)!} = {n+r-1 \choose r-1}$

#### Placing $n$ **(in)distinguishable** objects into $r$ **indistinguishable** boxes
(no simple closed form)
##### e.g. **indistinguishable** 4 objects into 3 **indistinguishable** boxes
(enumeration)
the numbers of objects in the boxes: $0\ 0\ 4\ |\ 0\ 1\ 3\ |\ 0\ 2\ 2\ |\ 1\ 1\ 2\ |\ 0\ 0\ 4$
##### e.g. distinguishable 4 objects into 3 indistinguishable boxes
the numbers of objects in the boxes: $0\ 0\ 4\ |\ 0\ 1\ 3\ |\ 0\ 2\ 2\ |\ 1\ 1\ 2\ |\ 0\ 0\ 4$
$0\ 0\ 4\ \to 1$
$0\ 1\ 3\ \to 4$
$0\ 2\ 2\ \to 3$
$1\ 1\ 2\ \to 6$

### Enumeration
#### Generating all permutations of $\{\ 1,\ 2,\ 3,\cdots ,\ n\}$
##### e.g. $n=3$
$1,2,3\ |\ 1,3,2\ |\ 2,1,3\ |\ 2,3,1\ |\ 3,2,1\ |\ 3,1,2$
#### Question:
Given a positive integer n, (write a program to ) output all permutation of $\{1,2,3,\cdots , n\}$

##### Recursive formula
- We don't know how the $n-$permutation are generated, but we know that every number( from 1 to n ) appears in the 1st position of some permutation.
- All the permutations that contain i as the 1st element can be formed by generating all (n-1)-permutation

void gen_per(int a[], int n, int s)
{
    //terminal condition
    
    if( s == n )
    {
        print_per( a, n);
        return;
    }
    //recursive formula
    for(int i = 0; i < n; i++)
    {
        swap( a, s, i);
        gen_per( a, n, s+1);
        swap( a, s, i);
    }
    return;
        
}

#### Generating all the r-combination of $\{\ 1,\ 2,\ 3,\cdots ,\ n\}$
##### e.g. $n=4, r=2$
$1,2\ |\ 1,3\ |\ 1,4\ |\ 2,3\ |\ 2,4\ |\ 3,4$
We can apply Pascal's identity to generate all r-combinations recursively.
Recall (Pascal's identity): ${n} \choose {r}$ = ${n-1}\choose {r}$+${n-1}\choose {r-1}$

//compute the number of r-combinations
int comb(iny n, int r)
{
    //assume that n >= r
    //terminal condition
    if(n == r || r == 0)
        return 1;
    //recursive formula
    return comb(n - 1, r) + comb(n - 1, r - 1);
}

//generate all the r-combinations
void fen_comb(int n, int r, int a[], int sm int b[], int t)
{
    // terminal cindition
    if(n - s == r || r == 0)
    {
        print(b, 0, t);
        print(a, s, s + r);
        printf("\n");
    }
    else
    {
        //recursive formula
        gen_comb(n, r, a, s + 1, b, t);
        b[t] = a[s];
        gen_comb(n, r - 1, a, s + 1, b, t + 1);
    }
    return;
}

### Lexicographic Order

The lexicographic ordering is an ordering defined on the permutations of a set whose elements are linearly ordered.
e.g. $\{1,2,\cdots,n\},\{a,b,c,\cdots,z\},\cdots$

Permutation $a_1a_2\cdots a_n$ Precedes permutation $b_1b_2\cdots b_n$ if for some $k$, with $1\leq k \leq n$, such that $a_1 = b_1, a_2=b_2,\cdots , a_{k-1}=b_{k-1}, a_k < b_k$
+

e.g. $n = 3$
1, 2, 3 | 1, 3, 2 | 2, 1, 3 | 3, 1, 2 | 3, 2, 1
$n = 4$
1, 2, 3, 4 | 1, 2, 4, 3 | 1, 3, 2, 4 | $\cdots$

<!---->
#### Generate the next permutation of a given one:
- Let $a_1, a_2, \cdots a_n$ be the give permutation.
- Find the greatest index j such that $a_j < a_{j+1}$ and $a_{j+1},\cdots a_n$ is decreasing.
- If no such j exists, then the permutation is the last one.
- Let $a_k$ be the least element in $\{a_{j+1}, \cdots , a_n\}$ satisfying $a_k > a_j$.
- Interchange $a_j$ and $a_k$.
- Reverse the sequence $a_{j+1}, \cdots, a_{k-1},a_j,a_{k+1},\cdots, a_n$.

Then you will get the requested permutation, which is
$a_1, \cdots, a_{j-1}, a_k, a_n, \cdots,a_{k+1}, a_j,a_{k-1}, \cdots,a_{j+1}$.