Modelli Biologici Discreti / Discrete Biological Models: Exercises for Lectures 2-5

Modelli Biologici Discreti / Discrete Biological Models (a.a. 2014/2015)

Exercises

Prove the basic recursion for binomial coefficients algebraically, i.e. by using the formula (n choose k) = n!/k!(n-k)!
(Recall the basic recursion: ((n+1) choose k) = (n choose k) + (n choose (k-1)).)
Prove for 0 ≤ l ≤ k ≤ n: (n choose k) (k choose l) = (n choose l) ((n-l) choose (k-l)).
Hint: Count in two ways all pairs (L,K), where L ⊆ K, |L|=l, |K|=k.
Every student has to take exactly 4 courses, out of a total of 7 which are offered. The lecturers report the following numbers as participants in their courses: 51, 30, 30, 20, 25, 12, 18. What can we deduce?
What is the number of divisors of (a) 2^m and of (b) n = p₁ ⋅ p₂ ⋅ ... ⋅ p_k, where each p_i is a prime number, 1 ≤ i ≤ k, and ∀ i ≠ j: p_i ≠ p_j (i.e. in the prime number decomposition of n, no prime number occurs twice, for example n=30).
Modular arithmetic: Prove the fundamental property of the modular congruence using the definition of "congruent modulo m":

If x ≡ x' (mod m) and y ≡ y' (mod m), then also (x+y) ≡ (x'+y') (mod m), and (x⋅y) ≡ (x'⋅y') (mod m).

Note the correction from the previous ~~"x ≡ y (mod m) and x' ≡ y' (mod m)"~~. In your notes from the lecture, you should have it in the correct form.
In class, we proved a rule for deciding whether a number is divisible by 11, using modular arithmetic. Prove the rule for 3: A number is divisible by 3 if and only if the sum of its digits is divisble by 3.
Are these two drawings of the same graph? (see class notes) - Yes or no, prove your statement.
For G₃, the first graph from the previous exercise, what is the degree of each vertex? Which are the cliques and the independent sets in this graph?
Prove that these two graphs are different (non-isomorphic) - see class notes.
Show that in a graph with at least 2 vertices, there are always at least two vertices with the same degree.
Hint: Use the pidgeonhole principle.