Balls in boxes and multisets 2 - Binomial coefficients, continued. Inclusion and exclusion formula. | Coursera

Explore all of Coursera

Browse
Top Courses
Log In
Join for Free

Balls in boxes and multisets 2

Loading...

Introduction to Enumerative Combinatorics

National Research University Higher School of Economics

4.7 (95 ratings) | 7.9K Students Enrolled

Enroll for Free

Enumerative combinatorics deals with finite sets and their cardinalities. In other words, a typical problem of enumerative combinatorics is to find the number of ways a certain pattern can be formed. In the first part of our course we will be dealing with elementary combinatorial objects and notions: permutations, combinations, compositions, Fibonacci and Catalan numbers etc. In the second part of the course we introduce the notion of generating functions and use it to study recurrence relations and partition numbers. The course is mostly self-contained. However, some acquaintance with basic linear algebra and analysis (including Taylor series expansion) may be very helpful. Do you have technical problems? Write to us: coursera@hse.ru

Reviews

4.7 (95 ratings)

5 stars
80%
4 stars
14%
3 stars
3%
1 star
3%

SS

Apr 11, 2020

i loved the course thanks to the\n\nNational Research University Higher School of Economics

CX

Feb 12, 2018

by far the best math course I had (and I've taken many) on coursera

From the lesson

Binomial coefficients, continued. Inclusion and exclusion formula.

In the first part of this lecture we will see more applications of binomial coefficients, in particular, their appearance in counting multisets. The second part is devoted to the principle of inclusion and exclusion: a technique which allows us to find the number of elements in the union of several sets, given the cardinalities of all of their intersections. We discuss its applications to various combinatorial problem, including the computation of the number of permutations without fixed points (the derangement problem).

The cab driver problem17:26

Balls in boxes and multisets 110:20

Balls in boxes and multisets 26:04

Integer compositions11:21

Principle of inclusion and exclusion: two examples12:36

Principle of inclusion and exclusion: general statement9:59

The derangement problem19:22

Taught By

Evgeny Smirnov
Associate Professor

Try the Course for Free

Transcript

[MUSIC] So we want to find the number of k element model sets of the sets with n elements or which is the same number of putting k balls inside n boxes. To find this number, let us reinterpret this problem in a slightly different way. Suppose we have such a configuration of balls and boxes. Let us represent it as follows by a sequence of defined objects while circles will represent balls and vertical bars, which will separate boxes. So the space to the left of the first bar is the first box, then suppose we're going from left to right. And at first, we're not looking at the first bar bounding the lead box from the left and we see one ball inside the first box. And then we'll put a bar which separates the first and the second boxes and then we put another, there are no balls inside the second box and we put a separator between the second and the third box. So, we'll put a bar here an then there are three balls inside the third box. And then there is a bar separator between the third and the fourth box. And finally, there is one ball in the last, the right most box. So we get a configuration of, k balls, And instead of n boxes, we get n minus 1 separator bars. So this, this picture innately determines the configuration of balls inside boxes. So, we need to compute the number of such configurations and this is the standard problem involving binomial coefficients. Namely, we have k plus n-1 objects called balls or bars. And out of these, we need to select k which corresponds to balls. Or equivalently, we need to select n-1 corresponding to bars. So, configurations, Of balls in boxes. Correspond to configuration of, Bars and balls. And there are k+n-1 objects. And out of these, k are balls and n-1 are bars. So, the number of such configurations is, k+n-1 choose k, out of k+n-1 objects. We need to pick those which correspond to balls. We get a theorem. Theorem, k balls can be put, Into n boxes, In n+k-1, choose k, ways. Equivalently, The number of k-element multisets. In an n-element set is n+k-1, choose k. And right now, we will discuss another version of this problem about compositions of integer number into positive integer assignments. [MUSIC]

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera

About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government
For Campus
Coronavirus Response

Community

Learners
Partners
Developers
Beta Testers
Translators
Blog
Tech Blog

More

Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates

Mobile App

© 2020 Coursera Inc. All rights reserved.