Transcript Document

Programming Interest Group
http://www.comp.hkbu.edu.hk/~chxw/pig/index.htm
Tutorial Five
Combinatorics & Number Theory
1
Outline

Combinatorics (组合)




Basic Counting Techniques
Recurrence Relations
Binomial Coefficients
Number Theory




Prime Number
Congruences
Fermat’s Theorem
Euler’s Theorem
2
Part I: Combinatorics



Combinatorics is the mathematics of counting.
It appears to be a collection of unrelated puzzles
chosen at random.
E.g. 1:


Given n letters and n addressed envelopes, in how many
ways can the letters be placed in the envelopes so that no
letter is in the correct envelope?
E.g. 2: (a Google interview problem)

There are n stages. Every time you can go up either 1
stage or 2 stages. How many different ways can you reach
the last stage?
3
Basic Counting Techniques

Product Rule



If there are |A| possibilities from set A and |B| possibilities
from set B, then there are |A|x|B| ways to combine one
from A and one from B.
E.g., suppose you own 5 shirts and 4 pants, then there are
5x4 =20 different ways you can get dressed.
Sum Rule

If there are |A| possibilities from set A and |B| possibilities
from set B, then there are |A|+|B| ways for either A or B to
occur (assuming the elements of A and B are distinct).
4
Basic Counting Techniques

Inclusion-Exclusion Formula:


|AUB| = |A| + |B| - |A∩B|
|AUBUC| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C|
+ |A∩B ∩C|
B
A
B
A
C
5
Basic Counting Techniques

Permutations


A permutation is an arrangement of n items,
where every item appears exactly once.
There are n! different permutations.






2n-1 ≤ n! ≤ nn-1 =====> n! is a very large number.
232 = 4,294,967,296
10! = 3,628,800
11! = 39,916,800
12! = 479,001,600
13! = 6,227,020,800 > 232
6
Basic Counting Techniques

Number of subsets



A subset is a selection of elements from n
possible items. (including the empty set)
There are 2n distinct subsets of n things.
E.g., set {a, b, c} has 8 (=23) subsets:

Ф, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b ,c}
7
Recurrence Relations


Recurrence relation is an equation which is
defined in terms of itself.
E.g. 1: an = an-1 + 1, a1 =1


E.g. 2: an = 2an-1, a1 =2


 an = n
 an = 2n
E.g. 3: an = nan-1, a1 =1

 an = n!
8
Recurrence Relations

The interview question from Google

To reach the nth stage, there are two possibilities:



First reach the (n-2)th stage, then go to the nth stage
directly
First reach the (n-1)th stage, then go to the nth stage
We can have the following recurrence relation:


an = an-1 + an-2
a1 = 1, a2 = 2
9
Fibonacci Numbers



Fn = Fn-1 + Fn-2; F0 = 0; F1 = 1
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Closed form:
= -0.61803…
1 5 n 1 5 n
Fn  ((
) (
) )/ 5
2
2



It can easily proved by mathematical induction.
Golden ratio:
1 5

2
 1.61803
Fibonacci numbers grow exponentially.
10
Binomial Coefficients

How many ways are there to choose k things out
of n possibilities?
 n
n!
 
 k  ( n  k )! k !

Coefficients of (a+b)n
 n  n  n  n1
( a  b)    a    a b 
0
1
n
 n  nk k
 a b 
k
 n n
 b
 n
11
How to calculate binomial
coefficients?


It’s difficult to calculate the value of binomial
coefficients by using the previous equation
directly: arithmetic overflow will happen for n >
12!
Pascal’s triangle (1654), or 杨辉三角 (1261)
1
1 1
1 2 1
1
1
3
4
3
6
1
4
1
 n   n  1  n  1
 


k
k

1
k
  
 

1 5 10 10 5 1
1 6 15 20 15 6 1
12
How to calculate binomial
coefficients? (Cont.)
#define MAXN 100
/* compute n choose m */
long binomial_coef(int n, int m) {
int i, j;
long bc[MAXN][MAXN}; /* table of binomial coef */
for(i = 0; i <= n; i++) bc[i][0] = 1;
for(j = 0; j <= n; j++) bc[j][j] = 1;
for(i = 1; i <= n; i++)
for(j = 1; j < i; j++)
bc[i][j] = bc[i-1][j-1] + bc[i-1][j];
return (bc[n][m]);
}
13
Catalan Numbers
n 1
C0  1, Cn   Ck Cn1k
k 0

1  2n 

 
n 1  n 
How many ways are there to build a balanced
formula from n pairs of parentheses?



Divide the formula into two parts: (……)(……)
The first part contains k pairs, the second part has n1-k pairs.
So the first part has Ck possibilities, while the second
part has Cn-1-k possibilities.
14
Practice 1:
How many pieces of land?



http://acm.uva.es/p/v102/10213.html
You are given an elliptical shaped land and
you are asked to choose n arbitrary points on
its boundary. Then you connect all these
points with one another with straight lines
(that’s n*(n-1)/2 connections for n points).
What is the maximum number of pieces of
land you will get by choosing the points on
the boundary carefully?
15
How many pieces of land?




Input
The first line of the input file
contains one integer S (0 <
S < 3500), which indicates
how many sets of input are
there. The next S lines
contain S sets of input.
Each input contains one
integer N (0<=N<2^31).
Output
For each set of input you
should output in a single
line the maximum number
pieces of land possible to
get for the value of N.
Sample Input:
4
1
2
3
4
Sample Output:
1
2
4
8
16
Analysis




Denote the solution by f(n), so f(1) = 1, f(2) = 2,
etc.
What’s the relationship between f(n) and f(n-1)?
Assume we have a maximum number of pieces
for n-1 points, which is f(n-1).
Now we add the nth point. We can connect this
point to other n-1 points. So we have n-1 new
lines.

Each line will lead to more pieces.
17
Analysis (Cont.)
i nodes on the left
k
Consider adding a new line
between node n and k.
n-2-i nodes on the right
The new line will intersect with
i(n-2-i) number of lines.
So, the new line will be divided
into i(n-2-i)+1 segments.
Each segment means a new
piece!
n
n 1
f (n)  f (n  1)  [i(n  2  i)  1]
i 0
18
Practice 2: Counting


http://acm.uva.es/p/v101/10198.html
Gustavo knows how to count, but he is now learning how write
numbers. As he is a very good student, he already learned 1, 2,
3 and 4. But he didn't realize yet that 4 is different than 1, so he
thinks that 4 is another way to write 1. Besides that, he is having
fun with a little game he created himself: he make numbers (with
those four digits) and sum their values. For instance:



132 = 1 + 3 + 2 = 6
112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (remember that Gustavo thinks that 4
= 1)
After making a lot of numbers in this way, Gustavo now wants to
know how much numbers he can create such that their sum is a
number n. For instance, for n = 2 he noticed that he can make 5
numbers: 11, 14, 41, 44 and 2 (he knows how to count them up,
but he doesn't know how to write five). However, he can't figure it
out for n greater than 2. So, he asked you to help him.
19
Counting (Cont.)

The Input


The Output



Input will consist on an arbitrary number of sets. Each set will consist on an
integer n such that 1 <= n <= 1000. You must read until you reach the end of file.
For each number read, you must output another number (on a line alone) stating
how much numbers Gustavo can make such that the sum of their digits is equal
to the given number.
Sample Input
2
3
Sample Output
5
13
20
Analysis



From the problem, we know f(1) = 2, f(2) = 5
From the sample Input/Output, we know f(3) = 13
A number can only start from 1, 2, 3, or 4






If it starts from 1, then the remaining n-1 digits should have a summation
of n-1
If it starts from 2, then the remaining n-1 digits should have a summation
of n-2
If it starts from 3, then the remaining n-1 digits should have a summation
of n-3
If it starts from 4, then the remaining n-1 digits should have a summation
of n-1 (because 4 is another way to write 1)
So, f(n) = 2f(n-1) + f(n-2) + f(n-3)
For this problem we can build a table for all f(n), 1 <= n <= 1000
 Remember to use big number library!
21
Part II: Number Theory




Number theory is concerned with properties of integers.
It is perhaps the most interesting and beautiful area of
mathematics.
Number theory plays an important role in modern cryptography.
Some outstanding unsolved problems:
 Goldbach’s Conjecture: every even integer n > 2 is the sum of 2
primes.
 Twin Prime Conjecture: There are infinitely many twin primes. (If
p and p+2 are primes, we say p and p+2 are twin primes.)
 Are there infinitely many primes of the form n2 + 1? How about
the form 2n -1?
22
Numbers




Natural numbers: N = {1, 2, 3,…}
Integers: Z = {…, -2, -1, 0, 1, 2, … }
Rational numbers: Q={n/m | m≠0}
Real numbers: R
23
Number Base Conversion

How to convert a decimal number to another
base b?
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int d, b, t, r;
vector<int> v;
cin >> d >> b;
while (d > 0) {
r = d % b;
v.push_back(r);
d = d/b;
}
reverse(v.begin(), v.end());
for (int i = 0; i < v.size(); ++i)
cout << v[i];
cout << endl;
return 1;
}
24
Big Modular

How to calculate A1A2…An mod p?


The product may be very large and overflow!
It can be calculated by:


(A1 mod p) x (A2 mod p) x … (An mod p)
Another example: how to calculate bp mod m?
long bigmod(long b, long p, long m) {
if (p == 0)
return 1;
else if (p%2 == 0)
return square(bigmod(b, p/2, m)) % m; // square(x) = x * x
else
return ((b % m) * bigmod(b, p-1, m)) % m;
}
25
Exponentiation

How to calculate bp?

Assume no overflow
long square(long n) {
return n*n;
}
long fastexp(long base, long power) {
if (power == 0)
return 1;
else if (power%2 == 0)
return square(fastexp(base, power/2));
else
return base * (fastexp(base, power-1));
}
26
Proof by Induction

Principle of Mathematical Induction:

Let P(n) be a statement concerning the integer
variable n. Let n0 be any fixed integer. P(n) is true
for all integers n ≥ n0 if one can establish both of
the following statements:


(a) P(n) is true if n = n0
(b) Whenever P(n) is true for n0 ≤ n ≤ k, then P(n) is
true for n = k+1
27
Divisibility

d | n means there is an integer k such that n
= d·k.

d | n has several readings:




d divides n
d is a divisor of n
d is a factor of n
n is a multiple of d
28
Divisibility Properties







n | n, and 1 | n
d | n and n | m  d | m
d | n and d | m  d | an + bm for all a and b
d | n  ad | an
d|0
If d and n are positive and d | n, then d ≤ n.
If d | n, then n/d | n, and

small(d, n/d) <= sqrt(n)
29
The Division Algorithm

If a and b are integers and b > 0, then there
exist unique integers q and r satisfying the
two conditions:



a = bq + r, and
0≤r<b
For b > 0, define a mod b = r where r is the
remainder given by the division algorithm
when a is divided by b, that is, a = bq + r and
0 ≤ r < b.
30
Prime Numbers

A prime number is an integer >1 and only has
divisors of 1 and itself




It cannot be written as a product of other numbers
E.g. 2,3,5,7 are prime, 4,6,8,9,10 are not
prime numbers are central to number theory
list of prime number less than 200 is:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
53 59 61 67 71 73 79 83 89 97 101 103
107 109 113 127 131 137 139 149 151 157
163 167 173 179 181 191 193 197 199
31
Primality Testing


We often need to find large prime numbers
Traditionally we can use trial division



i.e. divide by all numbers (primes) in turn, less than the
square root of the number
only works for small numbers
Alternatively, we can use statistical primality tests
based on properties of primes


for which all primes numbers satisfy property
but some composite numbers, called pseudo-primes, also
satisfy the property
32
Trial division
int is_prime(int n) {
if (n <= 1) return 0;
if (n == 2) return 1; // 2 is a prime
if (n%2 == 0) return 0; // NO prime is EVEN, except 2
for (int i = 3; i * i <= n; i += 2) // start from 3, jump 2 numbers
if (n%i == 0)
// no need to check even numbers
return 0;
return 1;
}
33
Divisibility check using
smaller primes below sqrt(N)


number N is a prime if and only if no primes below sqrt(N) can
divide N
Generate a prime table






Suppose max primes generated will not be greater than 2^31-1
(2,147,483,647).
We need smaller primes below sqrt(N), so we need to store primes no
greater that sqrt(2^31-1)
sqrt(2^31) = 46340.95
There will be at most 4792 primes in the range 1 to 46340.95
We only need about array of size (roughly) 4800 elements
check whether a big number N is a prime or not by dividing it
with small primes up to sqrt(N)

If you can find at least one small primes that can divide N, then N
is not prime, otherwise N is prime
34
Prime Table Generation (I)
bool isPrime[MAXN];
int i, tot, prime[];
memset(isPrime, true, sizeof(isPrime));
tot = 0;
prime[tot++] = 2;
for ( i = 3; i < MAXN; i+=2) {
if (isPrime[i])
prime[tot++] = i;
for(j = i + i; j < MAXN; j+=i)
isPrime[j] = false;
}
}
35
Prime Table Generation (II)
bool isPrime[MAXN];
int i, tot, prime[];
memset(isPrime, true, sizeof(isPrime));
tot = 0;
for ( i = 2; i <= n; i++) {
if (isPrime[i])
prime[tot++] = i;
for (j = 0; j < tot && i * prime[j] <= n; j++) {
isPrime[i*prime[j]] = false;
if (i % prime[j] == 0)
break;
}
}
36
Prime Distribution

There are an infinite number of primes.



Let π(x) denote the number of primes p such that p
≤ x.
Prime number theorem states that primes occur
roughly every ln(n) integers:


Can you prove it?
π(x) ~ x/ln(x) for all x > 0.
Since we can immediately ignore evens and
multiples of 5, in practice we only need to test
0.4ln(n) numbers of size n before finding a prime
37
Prime Factorization

to factor a number n is to write it as a
product of other numbers: n=a × b × c

note that factoring a number is relatively hard
compared to multiplying the factors together
to generate the number
the prime factorisation of a number n is
when its written as a product of primes


E.g. 91=7×13 ; 3600=24×32×52
38
Prime Factorization
#include<iostream>
#include<vector>
using namespace std;
int is_prime(int n) { … }
/* another C function for prime factorization */
primefactors(long x)
{
long I;
long c = x;
vector<int> primefactors(int a)
{
vector<int> primefactors;
for (int i=1;i<=a;++i)
if(a%i==0&&is_prime(i))
{
primefactors.push_back(i);
a=a/i;
i=1;
}
return primefactors;
}
if ( c == 1) {
printf(“1\n”);
return;
}
while( (c%2) == 0) {
printf(“%ld\n”, 2);
c = c / 2;
}
i = 3;
while ( i <= (sqrt(c) + 1) ) {
if ( (c%i) == 0 ) {
printf(“%ld\n”, i);
c = c / I;
}
else
i = i + 2;
}
int main()
{
int b=2500;
if(!is_prime(b)) cout<<"not prime"<<endl;
vector <int> p = primefactors(b);
for(int i=0;i<p.size();++i)
cout<<p[i]<<endl;
return 0;
}
if (c > 1) printf(“%ld\n”, c);
}
39
Number of divisors

If the prime factorisation of a number n is

Then the number of positive divisors of n is
40
A related problem


http://acm.uva.es/p/v101/10110.html
The Problem: Light, More Light
 There is man named "mabu" for switching on-off light in our
University. He switches on-off the lights in a corridor. Every bulb
has its own toggle switch. That is, if it is pressed then the bulb
turns on. Another press will turn it off.
 To save power consumption (or may be he is mad or something
else) he does a peculiar thing. If in a corridor there is n bulbs, he
walks along the corridor back and forth n times and in ith walk he
toggles only the switches whose position is divisable by i. He
does not press any switch when coming back to his initial
position. The ith walk is defined as going down the corridor (while
doing the peculiar thing) and coming back again. Now you have
to determine what is the final state of the last bulb. Is it on or off?
1
2
3
4
….
n-1
n
41
Light, More Light







The question asks about the final state of the
last bulb
There are n rounds
In the 1st round, because 1|n, press
In the 2nd round, if 2|n, press;
In the 3rd round, if 3|n, press;
…
In the nth round, because n|n, press
42
Light, More Light
A simple algorithm:
long i;
long press = 0;
for(i = 1; i <= n; i++) {
if(n % i == 0)
press++;
}
if( press % 2 == 0)
printf(“no\n”);
else
printf(“yes\n”);

A better algorithm:
long i;
long press = 0;
for(i = 1; i <= n/2; i++) {
if(n % i == 0)
press++;
}
if( press % 2 == 0)
printf(“yes\n”);
else
printf(“no\n”);

43
Light, More Light




But the previous algorithm is O(n)!
Is there a better way?
We can make some observations:
Define the number of factors of n as f(n). If f(n) is
even, then the final state of the nth bulb is “off”; if f(n)
is odd, then the final state of the nth bulb is “on”.




f(1) = 1; f(2) = 2; f(3) = 2; f(4) = 3;
f(5) = 2; f(6) = 4; f(7) = 2; f(8) = 4;
f(9) = 3; f(10) = 4; f(11) = 2; f(12) = 6;
f(13) = 2; f(14) = 4; f(15) = 4; f(16) = 5
44
Light, More Light



It seems that, only if n is a square of another
number, f(n) is odd !
How to prove?
Prime factorization:
Assume n  p1a1 p2a2
pkak , where pi are all primes,
then f ( n)  (1  a1 )(1  a2 )
(1  ak ).
If f ( n) is odd, then all 1  ai are odd, and then all ai are even.
Therefore n  ( p1a1 / 2 p2a2 / 2
pkak / 2 )2 .
45
Relatively Prime Numbers & GCD

two numbers a, b are relatively prime if they
have no common divisors apart from 1


E.g. 8 & 15 are relatively prime since factors of 8
are 1,2,4,8 and of 15 are 1,3,5,15 and 1 is the
only common factor
We can determine the greatest common
divisor by comparing their prime
factorizations and using least powers

E.g. 300=21×31×52 18=21×32 hence
GCD(18,300)=21×31×50=6
46
GCD: Euclid’s algorithm

Two observations:




If b|a, then gcd(a,b) = b
If a = bt + r, then gcd(a,b) = gcd(b, r)
Euclid’s algorithm is recursive, repeated
replacing the bigger integer by its remainder
mod the smaller integer.
E.g.: a = 34398, b = 2132
gcd(34398, 2132) = gcd(34398 mod 2132, 2132) = gcd(2132, 286)
= gcd(2132 mod 286, 286) = gcd(286, 130)
= gcd(286 mod 130, 130) = gcd(130, 26)
= gcd(130 mod 26, 26) = gcd(26, 0)
= 26
47
Sample Code
//Greatest Common Divisor
int gcd(int a, int b) {
while (b > 0) {
a = a % b;
a ^= b;
b ^= a;
a ^= b;
}
return a;
}
int t = b;
b = a;
a = t;
// Lowest Common Multiple
int lcm(int a, int b)
{
return a*b/gcd(a, b);
}
48
Extended Euclid’s Algorithm

gcd(a,b) can be expressed as ax+by


Given a and b, find out not only gcd(a,b), but also
x and y
The previous function only gives gcd(a,b)
int ext_gcd(int a, int b, int& x, int& y) {
int t, ret;
if (!b){
x=1; y=0;
return a;
}
ret=ext_gcd(b, a%b, x, y);
t=x; x=y; y=t-a/b*y;
return ret;
}
49
Congruences




We say that a≡b (mod m) if m|(a-b).
Congruences are an alternate notation for modular
arithmetic.
Addition: Suppose a≡b (mod n) and c≡d (mod n), then
a+c≡b+d (mod n)
Multiplication:




If a≡b (mod n), then a·d≡b·d (mod n).
If a≡b (mod n) and c≡d (mod n), then ac≡bd (mod n)
Exponentiation: If a≡b (mod n), then am≡bm (mod n)
Division??? 6·2≡6·1 (mod 3), but …
50
Congruences

Theorem 1: Let m ≥ 2. If a and m are
relatively prime, there exists a unique integer
a* such that aa* ≡ 1 (mod m) and 0 < a* < m.



We call a* the inverse of a modulo m.
Theorem 2: Let m > 0. If ab ≡ 1 (mod m),
then both a and b are relatively prime to m.
Theorem 3: Let m > 0 and assume
gcd(c,m)=1. Then ca ≡ cb (mod m)  a ≡ b
(mod m).
51
Fermat's Little Theorem

If p is prime and gcd(a, p) = 1, then


ap-1 mod p = 1
E.g., how to calculate 12347865435 mod 11?




1234 ≡ 2 (mod 11)  12347865435 ≡ 2 7865435 (mod 11)
210 ≡ 1 (mod 11) (according to Fermat’s litter theorem)
2 7865435 ≡ 2786543x10+5 (mod 11)
≡ (2^10)786543 x 25 (mod 11)
≡ 1786543x 25 (mod 11)
≡ 25 (mod 11)
≡ 10 (mod 11)
So 12347865435 mod 11 = 10.
52
Euler Totient Function ø(n)



when doing arithmetic modulo n
complete set of residues is: 0..n-1
reduced set of residues is those numbers
(residues) which are relatively prime to n




E.g. for n=10,
complete set of residues is {0,1,2,3,4,5,6,7,8,9}
reduced set of residues is {1,3,7,9}
number of elements in reduced set of residues is
called the Euler Totient Function ø(n)
53
Euler Totient Function ø(n)


To compute ø(n), we need to count number
of elements to be excluded
in general, it needs prime factorization, but



for p (p prime)
ø(p) = p-1
for p.q (p,q prime) ø(p·q) = (p-1)(q-1)
E.g.


ø(37) = 36
ø(21) = (3–1)×(7–1) = 2×6 = 12
54
Euler's Theorem

aø(n) mod n = 1



where gcd(a, n)=1
It is a generalisation of Fermat's Theorem
E.g.

a=3;n=10; ø(10)=4;


hence 34 = 81 = 1 mod 10
a=2;n=11; ø(11)=10;

hence 210 = 1024 = 1 mod 11
55
More Practices




http://acm.uva.es/p/v101/10104.html
http://acm.uva.es/p/v101/10139.html
http://acm.uva.es/p/v101/10168.html
http://acm.uva.es/p/v100/10042.html
56