Discrete Mathematics 2

<div><u><b>Discrete Mathematics 2</b></u></div><div><br></div><div>Mathematics from high school to university</div><div><br></div><div>S1. Introduction to the course</div><div>You will learn: about this course: its content and the optimal way of studying it together with the book.</div><div><br></div><div><span style="font-size: 1rem;">S2. Combinatorics: the art of counting, cont. from DM1</span></div><div>You will learn: a continuation of topics started in DM1 (permutations, variations, combinations; mathematical modelling), some new stuff (some problems left from DM1, counting functions, counting integer solutions to equations, a generalisation of the Inclusion-exclusion principle, counting derangements), and an introduction to some advanced topics (partitions, multinomial coefficients, Stirling numbers, Twelvefold Way); combinatorial problem solving.</div><div><br></div><div><br></div><div>S3. Combinatorial (and not only) proofs</div><div>You will learn: various types of proofs of binomial identities, including direct proofs, proofs by induction, proofs by telescoping sums, and combinatorial proofs; this topic was already started in DM1, but now you will see more of it.</div><div><br></div><div><span style="font-size: 1rem;">S4. A very brief introduction to (discrete) probability</span></div><div>You will learn: how Combinatorics can be applied for (discrete) Probability; this is not a formal course in Probability, just a demonstration of applications of some combinatorial methods for computing probabilities of events; some concepts (briefly) covered in the lectures: experiment, outcome, sample space, event, favourable event (all these were already covered in V9, here you get more examples involving coin toss, rolling dice, drawing balls from an urn, and playing poker), combining events (union and intersection of events), mutually exclusive events, complementary events, independent and dependent events, conditional probability, random variable and its expected value (just enough about it to fulfil the promise from V49 and V59).</div><div><br></div><div><span style="font-size: 1rem;">S5. An introduction to Number Theory</span></div><div>You will learn: divisibility, prime factorisation, finding primes (sieve of Eratosthenes), Euclid's algorithm for multiple purposes (finding the gcd [greatest common divisor] and lcm [least common multiple] of two natural numbers, solving Diophantine equations, and solving linear equations in modular arithmetic [in Section 6]), Euler's totient function, the sum-of-all-divisors formula, number representation in different position systems (decimal, binary, etc), converting numbers from decimal to other bases (and back). This is not a complete course in Number Theory (which is a huge branch of Maths!), just a basic introduction to some of its topics, the ones that are usually a part of DM courses.</div><div><br></div><div>S6. Modular arithmetic</div><div>You will learn: the basics of modular arithmetic: addition, subtraction, multiplication, raising to a power; properties of modular arithmetic; relation modulo n as an equivalence relation, equivalence classes and their representatives; tests for divisibility (by 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16); solving congruences, systems of congruences (with a reference to Chinese Remainder Theorem), linear equations, and systems of linear equations in Z_n for different numbers n; Fermat's Little Theorem with several proofs, one of them really exciting (combinatorial); Euler's Totient Theorem; some earlier problems are revisited and solved with new methods.</div><div><br></div><div><span style="font-size: 1rem;">S7. An introduction to algebraic structures</span></div><div>You will learn: you will get a glimpse into the wonderful world of Abstract Algebra, the domain of mathematics that studies structures such as groups, rings, fields, vector spaces, etc, their properties and relations between them; basic concepts such like binary operations on sets, their associativity and commutativity, neutral elements and inverse elements with respect to the operations; sets with two operations (rings, fields) and the property that binds these operations (distributivity), additive and multiplicative inverses; the concept of a subgroup; cyclic groups; direct (Cartesian) product of structures; groups of permutations and the geometrical interpretation of some of their subgroups; homomorphisms and isomorphisms between structures; Lagrange's Theorem; various examples and illustrations.</div><div><br></div><div><span style="font-size: 1rem;">Note: This is the second part of our trilogy in Discrete Mathematics. The following subjects will be covered in the next course: sequences (recurrences, generating functions, etc), an introduction to Graph Theory, chosen applications of Discrete Mathematics.</span></div><div><br></div><div>Make sure that you check with your professor what parts of the course you will need for your final 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.</div><div><br></div><div>A detailed description of the content of the course, with all the 222 videos and their titles, and with the texts of all the 412 problems solved during this course, is presented in the resource file</div><div><br></div><div>“001 List_of_all_Videos_and_Problems_Discrete_Mathematics_2.pdf”</div><div><br></div><div>under Video 1 ("Introduction to the course"). This content is also presented in Video 1.</div>

What you'll learn:

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