Prove expression for N using inclusion-exclusion principle

• GwtBc
In summary, the conversation discusses the use of the inclusion-exclusion principle to find the probability of at least one color not being used in a set of events. The formula for this probability is 1-(1/N)^N, where N represents the number of colors. The conversation also explores the use of this formula in finding the probability of using all N colors in a particular coloring scenario. The conversation concludes by mentioning a potential error in the calculation of this probability, which was later resolved.
GwtBc
Homework Statement
A little girl is painting on a blank paper. She has N colors available to her. Each time she selects one of these colors with replacement to draw with. Each trial is independent.

(There are some ensuing questions but eventually the following problem is posed:)

Suppose there are n=N trials and ##E_i## is the event that the color i is not used. By using the inclusion-exclusion principle on ##\cup_{1 \leq i \leq N}E_i## prove the following identity:

$$N! = \sum_{k=0}^{N} (-1)^k \binom{N}{k} (N-k)^N$$
Relevant Equations
Inclusion-exclusion principle is given by:

$$Pr(A_1 \cup A_2 ... \cup A_n) = \sum Pr(A_i) - \sum_{i<j} Pr(A_i \cap A_j) + ... + (-1)^{n-1} Pr(A_1 \cap A_2 ... \cap A_n)$$
Well ##\cup_{i} E_i## is just the event that at least one color is not used, so its probability is given by ##1- (1/N)^N##. Now if I is a subset of {1,...,N} where ##\left | I \right | = l## then ##Pr(\cap_{i\in I} E_i) = (1-l/N)^N## (I'm guessing this is where I'm making a mistake?). So then we will have for example that

$$\sum_{1\leq i < j < s < m \leq N} Pr(E_i\cap E_j \cap E_s \cap E_m) = \binom{N}{4} (1-4/N)^N$$

But when I plug these values into the inclusion exclusion for ##\cup E_i##, I get the required expression but with 1 on the LHS instead of ##N!##. It's possible to prove the identity using induction, but that's not the question and also not getting this out means there's something wrong with the probabilities I'm using which is worrying.

Thanks in advance for the help.

you might have to use combinatoric arguments
the ##N!## on lhs represents that all the N colours need to be placed in the N trial hence N!
now you need to inclusion exclusion principle to obtain the right hand side ie find the number of ways it is possible to colour using every colour. so in this context it is
##
\binom N 0 N^N - |E_1 \cup E_2 \cup ... \cup E_N|
##
and since if you use every colour it has to equal N! the two expression are equivalent( i think , i might be wrong)

I think I figured out my error which was that ## Pr(\cup_i E_i) = 1- (1/N)^N##. This probability is in fact equal to ## 1 - N!/N^N## since there are N! orders of picking all the different colors. Now the expression comes out nicely.

I do believe this was @timetraveller123 's idea as well.

timetraveller123

1. What is the inclusion-exclusion principle?

The inclusion-exclusion principle is a counting technique used in combinatorics to calculate the size of a set that is a union of other sets. It allows us to find the size of a set by subtracting the sizes of its subsets and adding back the sizes of their intersections.

2. How is the inclusion-exclusion principle used to prove expressions for N?

The inclusion-exclusion principle can be used to prove expressions for N by breaking down a complex set into smaller, more manageable subsets and using the principle to calculate their sizes. These sizes can then be combined using the inclusion-exclusion principle to find the size of the original set, which is represented by N in the expression.

3. Can the inclusion-exclusion principle be used for any type of set?

Yes, the inclusion-exclusion principle can be applied to any finite set, as long as the subsets and their intersections can be counted. It can also be used for infinite sets as long as they can be represented as the union of countable subsets.

4. Are there any limitations to using the inclusion-exclusion principle?

One limitation of the inclusion-exclusion principle is that it can become very complex and time-consuming when applied to sets with a large number of subsets. It also assumes that the subsets are mutually exclusive, meaning they do not have any elements in common.

5. Can the inclusion-exclusion principle be used in other areas of mathematics?

Yes, the inclusion-exclusion principle has applications in various areas of mathematics, such as probability theory, statistics, and graph theory. It is a fundamental counting technique that is widely used in combinatorics to solve problems related to counting and probability.

• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
15
Views
2K
• Calculus and Beyond Homework Help
Replies
6
Views
1K
• Math Proof Training and Practice
Replies
5
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
18
Views
2K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
1K
• Linear and Abstract Algebra
Replies
2
Views
1K