practice problems pending

1. How many ways to distribute 10 different balls into 3 different bags such that none of the bags is empty?
S1.

Distinct objects/distinct buckets => PIE(Principle of Inclusion Exclusion)

Step 1: Total cases: 3^10 since each ball can go into any of the bags.
Step 2: Subtract those cases where one bag is empty: 3C1 to choose one bag. And now each ball has 2 options: 2^10.
So total 3*2^10 cases need to be subtracted to account for one empty bucket.

In step 2 consider what happens in detail:
When we made one bucket empty, 10 balls have to go into 2 buckets: 2^10.
This also includes the cases when all the balls go to one bucket.

So considering empty bucket1 also considers the cases where bucket 1 and 2 are both empty.
Similarly when we consider bucket2 as empty we are also considering the case where both bucket 1 and 2 are empty.

Essentially we are double subtracting the cases where 2 buckets are empty.

So we need to add them back.
3C2 to choose 2 buckets to remain empty.
Now each ball has only one bucket to go to: 1^10

Final:
3^10 - 2*2^10 + 3*1^10 = 55980

------------------------------
Let's see this on a smaller example.
4 balls 3 buckets.
Method 1:
If none of the buckets is empty we have to group them like 2,1,1
For e.g. AB, C, D
So 4C2 ways.

Now 3! ways to arrange those groups.
Answer 6*6 = 36

Using PIE:
3^4 - 3*2^4 + 3*1^4 = 81 - 48 + 3 = 36.

So it works.

-------------------
Just to expand upon this:
1. Distinct objects/ Distinct buckets: PIE
2. Identical objects/ Distinct buckets: Stars and bars
3. Identical objects/ Identical buckets: Integer partition problem(No formula as such, manually do)
4. Distinct objects/ Identical buckets: Again no formula(Something to do with Sterling number)

Let's see case 3.
5 identical objects into 3 identical buckets.
Now each bucket may or may not be empty.
If empty allowed:
5
4+1
3+2
3+1+1
2+2+1
If empty now allowed only last 2 will be considered.
So essentially integer partition problem.

Case 4.
Distinct objects/identical buckets.
What if we flip them and apply stars and bars in reverse.

So objects A,B,C,D,E become distinct buckets and the buckets become identical objects.
So essentially we are counting solutions for:
A+B+C+D+E = 3
Let's consider one of the solutions: A = 3, rest all = 0.
That would mean that object A got placed into 3 different buckets! Wrong, right?
Similarly consider A=B=C=1, D=E=0 it means D,E didn't get any buckets which is not allowed.

So flipping stars and bars won't work here.
This is actually solved by Sterling number of second kind.

So this won't work.

Let's first solve for the case when no bucket can be empty.
As we noted in case 3, there are only 2 such ways.
3,1,1
2,2,1

For 3,1,1 and distinct objects we need to choose 3 from 5 and rest 2 simply remain as is: 5C3 = 10
For 2,2,1: 5C2*3C2/2!, why divide by 2!, because the buckets are identical. = 15
Total: 25

If the empty buckets are allowed:
Case 1: No empty buckets: 25
Case 2: 2 empty buckets: 1 (all go into 1 bucket)
Case 3: 1 empty bucket: 
4+1 => 5C4 = 5
3+2 => 5C3 = 10
Total: 15
Answer: 25+1+15 = 41