Questions tagged [inclusion-exclusion]

The inclusion-exclusion principle states that the number of elements in the union of two given sets is the sum of the number of elements in each set, minus the number of elements that are in both sets.

878 questions
208 views

Conditions for using inclusion/exclusion principle

Suppose I have $n+1$ sets of objects, $T_0,T_1,\dots,T_n$ and that I have $n$ mappings, $\alpha_1,\dots,\alpha_n$ such that $\alpha_i(T_j) \subseteq T_{j+1}$ for all $i=1,\dots,n$ and $j=0,\dots,n-1.$ ...
433 views

Basic inclusion exclusion problem - picking 24 balls out of four sets of 10 balls

This is probably a basic problem, but I'm having a really difficult time solving it. There are ten red balls, ten green balls, ten blue balls, and ten white balls. Balls of the same color are ...
502 views

People being seated around a table refusing to sit next to two other people

I was going to generalize an easy counting problem and I ended up not being able to solve it: In how many ways can $n$ people $1,\dots,n$ be seated around a round table if person $i$ refuses to ...
385 views

Combinatorics using constraints and ordered set

How would you find the number of combinations for a set of elements, where the elements have minimum and maximum values and the set is in lexicographic order. As an example: $a+b+c+d+e=635$, which ...
140 views

Finding $\dim(A_1 + A_2 +\cdots + A_n)$ [duplicate]

Possible Duplicate: The calculation of $\dim(U + V + W)$ Given a linear space $V$ and subspaces $A_i \subseteq V$ such that $1\leq i \leq n.$ To find $\dim(A_1 + A_2 +\cdots + A_n)$ it seems we ...
107 views

Counting travails

How many 7 digit numbers are there (no leading zero) in which the digits 6 & 9 occur together as 69 at least once. I am having difficulty in eliminating overcounting.
611 views

Is the Maclaurin series expansion of $\sin x$ related to the inclusion-exclusion principle?

When I see the alternating signs in the infinite series expansion of $\sin x$, I'm reminded of the inclusion-exclusion principle. Could there be any way to visualize it in such a way? Also, is there ...
379 views

Number of One to One functions such that $f(i)\neq i$

Given the sets $A=\{1,\dots,4\}$ and $B=\{1,\dots,7\}$ how many one to one functions are there from $A$ to $B$ such that $f(i)\neq i$ ? I used inclusion exclusion to first find the number of one to ...
102 views

Arranging 3 Rows of 4 letter as triplets with restrictions

Given the following matrix: $$\begin{bmatrix} a & b & c & d\\ e & f & g & h\\ i & j & k & l \end{bmatrix}$$ how many sets of 3 letter sets using all the ...
2k views

Number of 5 letter words over a 3 letter alphabet using each letter at least once

This is similar to my previous question, Number of 5 letter words over a 4 letter group using each letter at least once. The only difference is that there are 3 letters to choose from instead of 4. ...
969 views

Inclusion Exclusion vs. Generating Functions

To what extent are the Inclusion Exclusion principle and Generating Functions interchangeable? Is there a general principle? For instance, I asked the following question, Number of 5 letter words ...
9k views

100 Soldiers riddle

One of my friends found this riddle. There are 100 soldiers. 85 lose a left leg, 80 lose a right leg, 75 lose a left arm, 70 lose a right arm. What is the minimum number of soldiers losing all ...
1k views

Complex Poker Probabilities (Texas Hold 'Em)

I've got two questions: What’s the probability that someone else has a flush, given that you have a flush? Notes: - there are four people at the table - we don't know anything about the kind of ...
520 views

875 views

non-routine application of inclusion-exclusion

What are the circumstances when inclusion-exclusion can't be routinely applied, and some adjustments have to be made ? This question arises from a problem of finding the probability of getting a ...
389 views

Laguerre polynomials and inclusion-exclusion

Does anyone know a reference for the solution of the generalized derangement problem via Laguerre polynomials? The Wikipedia article here says that this is an application of inclusion-exclusion, but ...