Lecture Materials


Learning Goals

By the end of class, you should be more comfortable with the factorial function, permutations and combinations, and how to decide whether a problem statement is dealing with distinct or indistinct objects.

Reading

Combinatorics

Concept Check

https://www.gradescope.com/courses/226051/assignments/934322

Questions & Answers


Q: what do we mean by subset?

A1:  good question. A subset is a set with some of the elements in another set (but not all)


Q: like some ordered subset of any 6 digits?

A1:  yes!


Q: why did we divide by 4!?

A1:  Jerry wanted an expression for 10x9x8x7x6x5. That product isn't 10! because it is missing the 4x3x2x1. But if you divide 10! by 4! you get 10x9x8x7x6x5


Q: where can i find these slides?

A1:  http://web.stanford.edu/class/cs109/lectures/2-Combinatorics/


Q: How much working out would we need to show if given a problem like this on a problem set? Is it enough to just give the answer?

A1:  no! you should show your working. Enough that a TA can know you had the right idea if you get the number wrong


Q: do we have to put 1! ?

A1:  no :). Its just 1


Q: Jerry definitely said this and I missed it — we don’t need to include the 1! do we?

A1:  nope


Q: why did we multiply by 5

A1:  there are 5 choices for the digit that gets repeated


Q: why did we multiply 6!/2! by 5 again?

A1:  there are 5 choices for the digit that gets repeated (like are there 2 twos or 2 fours etc. there are 5 such digits)


Q: why did we multiply the 5 the 6!?

A1:  there are 5 choices for the digit that gets repeated


Q: What are the two steps in the permutation formula again? The product rule application isn’t quite clear

A1:  The two steps were particular to the passcode problem. The first step was chosing a digit which is duplicated. The second step is to use a permutation


Q: On the slide “sort semi-distinct objects”, can you elaborate on what the two steps are?

A1:  Slide 14? It says, the ways to make all permutations of objects, treating them as distinct, is to (a) get permutations of indistinct objects and then (b) to permute those indistinct objects. This is great because we can re-order these steps to come up with an equation for how to count permutations with indistinct objects


Q: How far in advance are the lecture slides put up on the website?

A1:  we put them up about 10-15 mins before lecture.


Q: 1 is just because we have 1 way to chose the 9th and 10th edition?

A1:  yes!


Q: why is it 1 times (4 choose 2)

A1:  can you clairfy?


Q: How did we get 4C1 again?

A1:  there are four non ross books from which you chose 1


Q: why did we subtract (4 chose 1)

A1:  there are four non-ross books and you need to chose one to go with the two-ross books (that makes a forbidden element)


Q: Why was the “forbidden” way to choose denoted as 4 choose 1? I am not sure where the 4 came from.

A1:  there are four non-ross books (6 - 2) and you need to chose one to go with the two-ross books (that makes a forbidden element)


Q: didnt follow the 4 choose 1 subtraction

A1:  there are four non-ross books (6 - 2) and you need to chose one to go with the two-ross books (that makes a forbidden element)


Q: for the sum rule, i was confused why 9th and 10th were “1 times (4 choose 2)”

A1:  there are four non-ross books (6 - 2) and you need to chose one to go with the two-ross books (that makes a forbidden element, a selection of three books with two ross ones)


Q: why do we need to “chose one to go with the two-ross books (that makes a forbidden element”

A1:  there are four non-ross books (6 - 2) and you need to chose one to go with the two-ross books (that makes a forbidden element: 3 books, two of which are ross)


Q: For this question, what happens if the number of machines available is more than 13?

A1:  you would have a different top number in your binomial.


Q: why did we made it 6, 4 and 3 across the datacenters

A1:  Its part of the problem. Multinomials come up when you want to talk about the probability of something you have already observed. So imagine we observed 6,4,3 and we were curious: how many ways could that have happened?


Q: What exactly is the reasoning for the first expression arriving at the correct answer?

A1:  one way to put 13 elements into buckets with 6,4,3 requests is to permute all elements. the first 6 we say go to the first server, the next four go to the second etc


Q: would that give the same answers as: 13 choose 3 X 10 choose 4 X 6 choose 6?

A1:  i believe that is correct. Check if it comes out to the same number (and if it doesn’t… then lets talk more)


Q: Not exactly relavent, but—for the first problem set, are the numbers supposed to be pretty? Or are some of the probabilities going to look a little messy?

A1:  some might look messy


Q: Is it a coincidence that combination of r groups is the same calculation as permutations with some distinct?

A1:  not a coincidence. You could have come up with the bucketing by permutting… the saying the first 6 are in group A, the next four are in group B etc


Q: i.e., is (13/6)(7/4)(3/3) = (13/3)(10/4)(6/6), where (a/b) is a choose b?

A1:  I truly think this is the same. If you put it into the binomial formula I think you will get the same answer


Q: What's the mathematical definition of a combination again?

A1:  you have n objects, you want to choose k, the number of ways is n!/n!(n-k)!


Q: why wouldn’t japan be affected? wouldnt there be one less spot on the hash table for japan to be placed in ? r - 1?

A1:  allowing for multiple objects in each bucket


Q: Back to the multinimial coefficient problem, if we have more than 13 computers to be allocated (15, for example), but the number of machines for each datacenter stays the same (has sum of 13), we cannot use multinimial coefficient right? since they don’t add up to 15. In this case, what should we use to figure out the different ways of allocating the machines?

A1:  right! must add up to n, in this case 13


Q: ohh so madagascar and japan can be placed in the same bucket? because its a hash table?

A1:  yes!


Q: Are the servers distinguishable?

A1:  yes!


Q: what is meant by distinct and indistinct in the context of servers?

A1:  indistinct servers means that if you switched the requests to one, with requests to another, that doesn’t count as a new result. Distinct servers means that it would


Q: why are we making the objects and dividers distinct?

A1:  were going to derive the divider method. In the next step we will make the indistinct. Great question btw


Q: why are there 3 dividers and not 4?

A1:  There are four groups. You need three dividers to make four groups (because there is one on each end. fence post problem really)


Q: Is this called stars and bars in places online?

A1:  yes! Thats from Feller’s book


Q: Why do you add n and r-1 isntead of multiply?

A1:  because the total number of objects is the n objects and the (r-1) dividers. The total number is n + (r-1)


Q: What happens if you want the buckets to also be indistinct?

A1:  could divide by num buckets factorial (ie r!)


Q: why are we doing this with dividers and not with buckets?

A1:  the dividers sparate the buckets! Its the way that the equation for putting things into buckets was derived


Q: Is (n+r-1)C(r-1) equal to (n+r-1)C(n) ?

A1:  I believe so: n = (n+r-1) - (r - 1)


Q: wait dont we need to give 1$ increments?

A1:  thats right!


Q: but our c1 c2 c3 and c4 had 10 0 0 0 ?

A1:  by 1 million increments, they mean that everyhing is in multiples of millions… so 10 is £ 10m, a multiple of £1m


Q: what does the x1 + x2 + x3 + x4 = 10 equation represent?

A1:  it says you have four variables that sum to 10. In this problem we are talking about the ways of chosing the integer values of xi


Q: oh so we dont need to give money to companies 2-4? we gave the full 10 to company 1

A1:  yes!


Q: what does xi represent?

A1:  the “i”th variable :-)


Q: can you clarify what we mean by indistinct and distinct?

A1:  distinct means we would notice if we swapped the two. Indistinct means we would not


Q: can we go over again the 4 chose 1 from the earlier example again the forbidden strategy

A1:  live answered


Q: Is the concept check due today or just before the next lecture?

A1:  before fridays lecture


Q: the concept check is due before the following lecture right?

A1:  yes!


Q: Where are the links for OH? I only see the times on the calender, but no link.

A1:  we will add the links now. jerry will add his right away


Q: Can we take picutres of homework that we wrote down on paper to submit it on gradescope?

A1:  as long as its really easy to read for our TAs :)


Q: could we maybe look back at the “one number in the passcode gets repeated” question? still confused about the 5x part

A1:  live answered


Q: is inclusion-exclusion referring to the presence of forbidden cases?

A1:  basically yes!


Q: For the books & ross problem: why aren't we also subtracting the cases in which we chose only one of the ross books?

A1:  because thats not the constraint. the constraint is that you cant have both


Q: is it ok if we do the problem sets by hand?

A1:  sure! Just please write legibly


Q: the python for probabilty link on the website still has the dates from the fall (http://web.stanford.edu/class/cs109/handouts/python.html)

A1:  will fix. thanks maximino


Q: Do the explanations have to be in full sentences?

A1:  please! To the extent possible


Q: that makes so much more sense with the 5x, thank you

A1:  awesome


Q: how do we deal with only 4 distinct numbers in a 6 digit code

A1:  gets hard, because one number could be used 3 times, or two numbers could be used twice. Many cases…


Q: sorry would you mind explaining that one more time

A1:  live answered


Q: could someone explain the at least 3 million example again?

A1:  live answered