Discrete Mathematics 2

A total of almost 66 hours of lectures

This is the second part of our series of three courses in Discrete Mathematics. It contains combinatorics, an introduction to discrete probability, elementary number theory, modular arithmetic, and an introduction to algebraic structures. 

Image precalculus part 1


Prerequisites

High-school maths, mainly arithmetics, some trigonometry. Discrete Mathematics 1 (or equivalent: logic, sets, functions, relations, proof techniques, basic combinatorics).


Curriculum

Make sure that you check with your professor what parts of the course you will need for your exam. Such things vary from country to country, from university to university, and they can even vary from year to year at the same university.

Discrete Mathematics 2

h

Get the outline

A detailed list of all the lectures in part 2 of the course, including which theorems will be discussed and which problems will be solved. If you are looking for a particular kind of problem or a particular concept, this is where you should look first.

Get Discrete Mathematics 2: basic notions on Udemy

When you buy the course on Udemy, you get access to it for life. There is just a one-time fee. The prices do vary a lot on Udemy, but if you use our link by clicking on this panel, you will get the best current price. See also our page on “coupon codes” in the menu (the current code is TPOT_MAR26).

Course Objectives & Outcomes

Z
How to solve problems in chosen Discrete-Mathematics topics (illustrated with 412 solved problems) and why these methods work, with step-by-step explanations.
Z
More combinatorial topics, including counting multisets (method by sticks and stones) and a generalisation of the Inclusion-exclusion principle (two versions).
Z
Various types of proofs of binomial identities: direct proofs, using the Binomial Theorem, induction proofs, proofs by telescoping sums, combinatorial proofs.
Z
Some basic concepts in Probability: experiment, outcome, sample space, event, favourable event.
Z
Independent and dependent events, conditional probability.
Z
Basic concept in Number Theory: prime and composite numbers, divisibility, gcd (greatest common divisor) and lcm (least common multiple), quotient, remainder.
Z
The sum-of-all-divisors formula (based on prime factorisation).
Z
Number representation in different positional systems (decimal, binary, etc).
Z
Various properties of modular arithmetic; solving simple congruence equations.
Z
Fermat’s Little Theorem with four proofs (one of which really delightful).
Z
A basic introduction to main algebraic structures (groups, rings, fields, vector spaces) with some nice examples using the theory from S5 and S6.
Z
The concepts of a subgroup and a cyclic group with some arithmetic and geometric examples.
Z
Invertible elements in Z_n; the fields Z_p with addition and multiplication modulo p; the group of units U_n.
Z
Lagrange’s Theorem at the end of the course puts together many elements of DM: groups, number theory, equivalence relations, and partitions of sets.
Z
Some geometric examples (dihedral groups: isometries of an equilateral triangle and isometries of a square).
Z
Combinatorics, continuation from DM1: permutations, variations (with and without repetitions), combinations; some problems formulated (but not solved) in DM1.
Z
An introduction to some advanced topics: partitions of sets, multinomial coefficients, Stirling numbers, and the Twelvefold-Way group of problems.
Z
A very brief introduction to (discrete) probability, with some typical examples of experiments like tossing a coin, and rolling dice; probability in poker.
Z
Combining events (union and intersection of events), mutually exclusive events, complementary event.
Z
Random variable and its expected value (just enough for the Secretary problem).
Z
Euclid’s algorithm for multiple purpose (finding the gcd and lcm, solving Diophantine equations, and solving linear equations in modular arithmetic [S6], etc).
Z
Euler’s totient function (number of natural numbers less than n, relatively prime with n).
Z
Modular arithmetic, counting modulo n, an introduction to the rings Z_n.
Z
Tests for divisibility (by 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16).
Z
Euler’s Totient Theorem as a generalisation of Fermat’s Little Theorem.
Z
Examples of associative and commutative binary operations defined on different sets, also some examples of operations not having these properties.
Z
The concept of homomorphism and isomorphism with some examples; properties of homomorphisms; isomorphic groups.
Z
An introduction to (symmetric) groups of permutations and their subgroups; multiplication of permutations.
Z
Direct product of a number of rings Z_n and a natural isomorphism between this ring and Z_N: a preparation for the Chinese Remainder Theorem (planned for DM3).
Z
The course contains a bunch of really fun (maths-competition style) problems, mainly in Section 6.