Explore

Combinatorics and Probability

Approx. 21 hours to complete

Save Course

Go to Course

Course Summary

Learn Combinatorics and gain the ability to solve complex problems in mathematics, computer science, and other fields. This course covers the fundamental principles of combinatorics and their applications in real-world scenarios.

Key Learning Points

Develop a strong foundation in combinatorial analysis
Gain the ability to solve complex mathematical problems
Learn how to apply combinatorics in various fields such as computer science, statistics, and physics

Learning Outcomes

Develop a strong foundation in combinatorial analysis
Gain the ability to solve complex mathematical problems
Understand the applications of combinatorics in various fields

Prerequisites or good to have knowledge before taking this course

Basic knowledge of algebra
Familiarity with mathematical notation

Course Difficulty Level

Intermediate

Course Format

Online
Self-paced

Similar Courses

Discrete Mathematics and Analyzing Social Graphs
Introduction to Algorithms
Probability and Statistics

Related Education Paths

Notable People in This Field

Richard Stanley
Herbert Wilf

Related Books

Description

Counting is one of the basic mathematically related tasks we encounter on a day to day basis. The main question here is the following. If we need to count something, can we do anything better than just counting all objects one by one? Do we need to create a list of all phone numbers to ensure that there are enough phone numbers for everyone? Is there a way to tell that our algorithm will run in a reasonable time before implementing and actually running it? All these questions are addressed by a mathematical field called Combinatorics.

In this course we discuss most standard combinatorial settings that can help to answer questions of this type. We will especially concentrate on developing the ability to distinguish these settings in real life and algorithmic problems. This will help the learner to actually implement new knowledge. Apart from that we will discuss recursive technique for counting that is important for algorithmic implementations. One of the main `consumers’ of Combinatorics is Probability Theory. This area is connected with numerous sides of life, on one hand being an important concept in everyday life and on the other hand being an indispensable tool in such modern and important fields as Statistics and Machine Learning. In this course we will concentrate on providing the working knowledge of basics of probability and a good intuition in this area. The practice shows that such an intuition is not easy to develop. In the end of the course we will create a program that successfully plays a tricky and very counterintuitive dice game. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

Outline

Basic Counting
Why counting
Rule of Sum
How Not to Use the Rule of Sum
Convenient Language: Sets
Generalized Rule of Sum
Number of Paths
Rule of Product
Back to Recursive Counting
Number of Tuples
Licence Plates
Tuples with Restrictions
Permutations
Slides
Slides
Listing All Permutations
Slides
Rule of Sum in Programming
Numbers Divisible by 2 or 3
Operations with Sets
Generalized Rule of Sum
Puzzle: Number of Paths
Rule of Product in Programming
Applications of the Rule of Product
Number of passwords
Tuples
Counting with Restrictions

Binomial Coefficients
Previously on Combinatorics
Number of Games in a Tournament
Combinations
Pascal's Triangle
Symmetries
Row Sums
Binomial Theorem
Practice Counting
Generating Combinatorial Objects: Code
Slides
Slides
Slides
Number of Segments and Diagonals
Forming Sport Teams
Number of Iterations of Nested For Loops
Sum of the First Six Rows of Pascal's Triangle
Expanding (3a-2b)^k
Practice Counting

Advanced Counting
Review
Salad
Combinations with Repetitions
Distributing Assignments Among People
Distributing Candies Among Kids
Numbers with Fixed Sum of Digits
Numbers with Non-increasing Digits
Splitting into Working Groups
Salads
Slides
Slides
Salads
Combinations with Repetitions
Distributing Assignments Among People
Distributing Candies Among Kids
Numbers with Fixed Sum of Digits
Numbers with Non-increasing Digits
Splitting into Working Groups
Problems in Combinatorics

Probability
The Paradox of Probability Theory
Galton Board
Natural Sciences and Mathematics
Rolling Dice
More Probability Spaces
Not Equiprobable Outcomes
More About Finite Spaces
Mathematics for Prisoners
Not All Questions Make Sense
What Is Conditional Probability?
How Reliable Is The Test?
Bayes' Theorem
Conditional Probability: A Paradox
Past and Future
Independence
Monty Hall Paradox
`Our Position'
Concentration for Galton Board
Computing Probabilities for Two Dice
Computing Probabilities: More Examples
Fair Decisions and Imperfect Coins
Puzzle: Prisoner and King
Inclusion-Exclusion Formula
Computing Conditional Probabilities
Prisoner, King and Conditional Probabilities
More Conditional Probabilities
More About Independence
Monty Hall Gone Crazy

Random Variables
Random Variables
Average
Expectation
Linearity of Expectation
Birthday Problem
Expectation is Not All
From Expectation to Probability
Markov’s Inequality
Application to Algorithms
Average Value of a Dice Throw: Experiment
Slides
Slides
Dice Game Experiment
Slides
Slides
Random Variables
Average
Expectations
Linearity of Expectation
Bob’s Party
More Linearity
Average Income
Bob’s Party Revisited
Alice’s tests

Project: Dice Games
Dice Game
Playing the Game
Project Description
Experiment: Dice Game
Slides
Slides
Final Project: Dice Game

Summary of User Reviews

Read reviews for the Combinatorics course on Coursera. Students have described the course as comprehensive and well-structured. Many users appreciated the interactive problems and engaging lectures.

Key Aspect Users Liked About This Course

Many users thought the interactive problems and engaging lectures were a key aspect of the course.

Pros from User Reviews

Comprehensive and well-structured course material
Engaging lectures that keep students interested
Challenging problems that help students learn
Opportunities for peer interaction and discussion

Cons from User Reviews

Some users found the course to be too challenging
The pace of the course may be too fast for some students
Limited feedback from instructors
No certificate of completion for the free version of the course

Recommended for you

Probability for Statistics and Data Science

Probability for improved business decisions: Introduction, Combinatorics, Bayesian Inference, Distributions What most people don’t realize is that having a probabilistic mindset is much more important than knowing “absolute truths”....

Save Course

Delivery Problem

We’ll implement (in Python) together efficient programs for a problem needed by delivery companies all over the world millions times per day — the travelling salesman problem....

Save Course

Principles of Computing (Part 1)

This two-part course builds upon the programming skills that you learned in our Introduction to Interactive Programming in Python course. These skills underlie larger scale computational problem solving and programming....

Save Course