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) 2m and of (b) n = p1 ⋅ p2 ⋅ ... ⋅ pk, where each pi is a prime number, 1 ≤ i ≤ k, and ∀ i ≠ j: pi ≠ pj (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 G3, 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.