Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
0answers
40 views

Calculate $\sum_{|S|=k}(n-|\cup S|)^m$ where $S$ is a subset of $X=\{\{a_1,a_2\},\{a_2,a_3\},\cdots,\{a_{n-1},a_n\},\{a_n,a_1\}\}$

Let $x_i=\{a_i,a_{i+1}\}\ (1 \leq i \leq n-1)$, $x_n=\{a_n,a_1\}$ and $X=\{x_1, \cdots, x_n\}$. Given $n,m$ and $k$, I'd like to ask how to calculate $\sum_{|S|=k}(n-|\cup S|)^m$ where $S$ is a subset ...
0
votes
0answers
16 views

Inclusion–exclusion principle in projective geometry

In the problems that I have to apply Grassmann in projective geometry, can I use the inclusion-exclusion principle? Consider the following problem: We consider three linear varieties of dimension ...
0
votes
1answer
42 views

How many numbers between $1 - 1000$ leave no remainder when divided by $4$ and when divided by $6$ but not when divided by $21$?

Numbers between $1 - 1000$ which leave no remainder when divided by $4$ and divided by $6$ but not by $21$? I tried $$\frac{1000}{12} = 83 - \frac{83}{21} = 83-3 = 80$$ Am I correct? Can someone ...
7
votes
2answers
181 views

Showing an alternating sum is positive

I am trying to prove the following for $n > 1$. $$\sum_{k=0}^n (-1)^k \binom{n}{k} \max\{0,n-2k\}^{n-1} > 0.$$ From numerical computations, this seems to be true, but I am struggling to find ...
0
votes
0answers
28 views

Principle of I/E: In how many ways can eight cakes be distributed among four kids if every kid receives at least one cake?

Eight cakes are distributed randomly among four kids. Use I/E to determine in how many of the possible distributions every kid receives at least $1$ cake. Hint: Define $A_i$ to be the set of ...
1
vote
2answers
73 views

Counting Surjections with Inclusion-Exclusion

Compute the number of surjective functions $f : [10] → [5]$ using the I/E principle. With Stirling numbers of the second kind, we can obtain the answer with the following way $S(10,5)5!$. How I can ...
0
votes
2answers
159 views

How many numbers from 0 to 99999 contain the digits 2, 5 and 8?

I have this problem: How many integers between 0 and 99999 contain the digits 2, 5 and 8? I've tried a lot, but I don't know how resolve it. P.S. The solution should be 4350.
0
votes
1answer
45 views

What is a k-wise intersection?

I am having a hard time visualizing and conceptualizing what a k-wise intersection is. I am guessing 3-wise intersection for 3 sets: $S_1,S_2,S_3$ would be $(S_1 {\cap}S_2{\cap}S_3)$ and 2-wise ...
2
votes
1answer
32 views

Calculate the expected value of the number of different digits

Question. $n$ is a $m$-digit number. ($m$ can start with zero.) Let $P(n)$ the number of different digits in $n$. What is the expected value of $P(n)$? (For example, $P(12341234)=4$.) My approach. ...
0
votes
1answer
22 views

Is my proof valid? Let $\{A_i\}_{i=0}^{i=n}$ a series of events such that $\forall i$ $P(A_i)=1$. Show that $\bigcap\limits_{0 \leq i \leq n}A_i=1$.

Let $\{A_i\}_{i=0}^{i=n}$ a series of events such that $\forall i$ $P(A_i)=1$. Show that $\bigcap\limits_{0 \leq i \leq n}A_i=1$. My attempt: Let $0\leq k\ne j\leq n$, so $P(A_j)=1, P(A_k)=1$. ...
1
vote
2answers
37 views

Selecting conditional states depending on previous states

I've seen a post which was started as a joke saying : "Well, Guess the code ?" (4 digit code) Apart from the joke , I was thinking , well , how many combinations do we have here , knowing that <...
0
votes
1answer
54 views

4 couples and 4 single people seated at 3 round tables

In how many ways can you seat the 12 people at 3 round tables such that: A) All couples are seated together. (the two members of each couple sit side-by-side) B) No couples sit together. I've ...
0
votes
1answer
32 views

Inclusion-Exclusion Number of Sets

Derive and prove a general formula for the number of elements which are in an odd number of the sets $A_1,A_2,...,A_n$, written in terms of $|A1|$, $|A2\cap A7|$, $|A3\cap A4\cap A9|$, etc., possibly ...
-2
votes
3answers
113 views

Probability Inclusion-Exclusion With 3 Events

The question is: An urn contains 4 balls: 1 white, 1 green, and 2 red. We draw 3 balls with replacement. Find the probability we did not see all three colors. I need to define the events as W= {white ...
5
votes
3answers
109 views

Number of ways to arrange word 'KBCKBCKBC'

The word 'KBCKBCKBC' is to be arranged in a row such that no word contains the pattern of KBC. $Attempt$ Event $A$=1st KBC is in the pattern, $B$=2nd KBC is in the pattern and similar is the event C....
2
votes
1answer
66 views

Number of permutation of $\{ 1, 2 \dots 2n\}$ with even fixpoints and relating this to derangements.

I am interested in determining $e_n$, the number of permutations of $\{ 1,2 \dots 2n\}$ where we allow even numbers to be fixed points, but where odd numbers are not allowed to be fixed points. This ...
0
votes
0answers
76 views

Inclusion-Exclusion Problem - derangement

Let $n ∈ \mathbb{N}$ be a natural number and $X$ a finite set with $n$ elements. Show that the number of permutations of $X$ such that no element stays in the same position is $$n!\sum_{k=0}^{n}\...
0
votes
1answer
67 views

Counting number of rearrangements in which no person has the same right neighbor [duplicate]

If $6$ people are standing up in queue for a picture, then in how many ways can they be re queued for the picture if no person has same right hand neighbor? Why is $6!/2$ wrong? (The answer is $309$...
1
vote
1answer
41 views

Number of ways for getting sum equal to s using inclusion-exclusion

I am trying very hard to understand following inclusion-exclusion problem but can't get it. It will be very helpful if someone can provide detail explanation. f(s) is number of ways of having sum ...
1
vote
0answers
27 views

PIE — # of students taking Spanish

A school with $100$ students offers French and Spanish as its language courses. Twice as many students are in the French class as the Spanish class. Three times as many students are in both classes as ...
1
vote
1answer
40 views

Counting with Principle of inclusion-exclusion

Let $n$ be a positive integer. Find the number of permutations of $ (1, 2,...,n)$ such that no number remains in its original place. Solution: To do this, first we are going to count the number of ...
3
votes
2answers
78 views

What is the probability that no cup is on a saucer of the same colour?

A tea set comprises four cups and saucers in four distinct colours. If the cups are placed at random on the saucers, what is the probability that no cup is on a saucer of the same colour? MY ATTEMPT ...
0
votes
0answers
86 views

In how many ways can letters in a word CALCULUS be rearranged

In how many ways can letters in a word CALCULUS be rearranged such that no 2 same letters stand next to each other. I’ve been thinking of Inclusion-Exclusion principle. Is there any different way to ...
0
votes
1answer
210 views

Number of ways of coloring n objects which are laid in a row with k colors such that the adjacent objects are of different colors

Given n objects, which are lying in a straight line next to each other, in how many ways we can color them with k colors (all must be painted) such that the adjacent boxes not of same colors. I can ...
1
vote
1answer
27 views

Given $a_1, a_2, \cdots, a_N$ such that $a_1+a_2+\cdots +a_N = S$ for some given $S$, find the number of ways such that someone is $\geq T$.

Given $a_1, a_2, \cdots, a_N$ such that $a_1+a_2+\cdots +a_N = S$ for some given $S$, find the number of ways such that someone is $\geq T$. The question is solved using Inclusion Exclusion in the ...
0
votes
0answers
110 views

A Question on the Inclusion-Exclusion Principle in Probability Theory

Let $n \geq 3$ be a fixed integer and consider an arbitrary set of the events $\{A_i, 1 \leq i \leq n \}$ in the same probability space. Consider the following two sums of probabilities: \begin{align} ...
4
votes
2answers
66 views

Derangements $p$ of $1,2,\dots,n,n+1$ such that $n+1$ doesn't go to $n$

Recall that the number or Derangements of $1,2,\dots,n$ is a permutation $p$ such that $p(i) \neq i$ for all $i$. We can express it with the recurrence $D_n=(n-1)(D_{n-1}+D_{n-2})$ or by the closed ...
0
votes
1answer
19 views

Inclusion exclusion principle counting

50 students traveled to Europe, last year. Of these, 12 visited Amsterdam, 13 went to Berlin, and 15 were in Copenhagen. Some visited two cities: 3 visited both Amsterdam and Berlin, 6 visited ...
2
votes
2answers
99 views

Number of one-one function from sets $A$ to $B$.

Let $A=\{1,2,3,4,5\}$ and $B=\{0,1,2,3,4,5\}$. Number of one-one function from $A$ to $B$ such that $f(1) \neq 0$ and $f(i)\neq i$ for $i={1,2,3,4,5}$ is _______ . So I know one one function means ...
2
votes
4answers
77 views

Prove that $(1-x)^n \leq 1 -xn+\frac{n(n-1)}{2}x^2$ when $0\leq x\leq 1$ and $n\geq2$

Reading a book I saw this inequality $$ (1-x)^n \leq 1 -xn+\frac{n(n-1)}{2}x^2 $$ when $0\leq x\leq 1$ and following the author it descended from the inclusion-exclusion principle. I don't understand ...
0
votes
2answers
29 views

Seating Arrangement with Derangement

A group of n students is assigned seats for each of two classes in the same classroom.How many ways can these seats be assigned if no student is assigned the same seat for both classes? Okay so this ...
1
vote
1answer
26 views

How many ways are there to divide n dancers into dance circles where in each circle num of dancers >=2?

Question:Be n\geq 2, how many ways are they to divide n dancers to circles so each circle has at least 2 dancers? I saw a similar question here but it was where order matter in the circles and ...
0
votes
2answers
16 views

Letters and Envelops problem

Consider a machine whose job is to place 100 letters into 100 envelops.The machine is defective and makes mistakes.What is the probability that in a group of 100 letters no letter is put into the ...
0
votes
1answer
37 views

Explanation of counting by Inclusion Exclusion

In my notes I have the following as an example for counting by inclusion exclusion. Let S be a set. Let $c_i(x)$ where $i=1,2,3,4....k$, be a statement that is either true or false for $x \in S$. ...
0
votes
1answer
34 views

Let 𝐴, 𝐵 and 𝐶 be sets. Prove formally that |𝐴 ∪ 𝐵 ∪ 𝐶| = |𝐴| + |𝐵| + |𝐶| − |𝐴 ∩ 𝐵| − |𝐴 ∩ 𝐶| − |𝐵 ∩ 𝐶| + |𝐴 ∩ 𝐵 ∩ 𝐶|

By using a Venn diagram we can see almost immediately that the cardinality of the members of the equality is in fact the same, however the exercise asks me to prove it formally and there is where my ...
1
vote
1answer
54 views

Inclusion Exclusion Principle with mixed lower and upper bounds

I know how to solve most types of these problems, but this one is a bit different. Problem: John is getting his friend some balloons for his birthday. He can have 4 types of colors (red, blue, ...
1
vote
1answer
126 views

Determine the number of integer solutions to $x_1 + x_2 + x_3 + x_4 = 19$, where $−5 \le x_i \le 10$ for all $1 \le i \le 4$

What I have so far: Goal: Using the inclusion exclusion I want to find $|\overline A_{1}\cap \overline A_{2} \cap \overline A_{3} \cap \overline A_{4}| = |U| - S_{1} + S_{2} - S_{3} + S_{4}$ $S_{k} ...
3
votes
2answers
68 views

$n$ guests, each guest brings a prize, how many ways may the prizes be given out so nobody gets the prize that they brought?

Each person attending a party has been asked to bring a prize. The person planning the party has arranged to give out exactly as many prizes as there are guests, but any person may win any number of ...
1
vote
1answer
108 views

Combinations of flowers using the counting method for integer partitions.

I have this problem to complete that wants to know how many combinations of flowers can there be in a bouquet of 25 flowers, such that: $r+c+d+t=25$ where $r=$roses, $c=$carnations, $d=$daisies and $...
1
vote
3answers
67 views

What is the number of arrangements in the word “EDUCATION” where vowels are never together?

I know the answer is $$ 4! P(5,5) $$ Because we can arrange the consonants amongst themselves in 4! ways and then independently insert the five vowels into the five spaces available. My question ...
1
vote
0answers
46 views

Inclusion exclusion and partition of a set - making sure I understand the concepts

If I may, I would like to verify my solution of a couple of homework questions, and by doing so asking a few questions about these topics. Let $X$ be a set of size $n$. How many distinct triplets $(A,...
1
vote
1answer
291 views

Counting ways to line up for a family photo.

Question: A family lines up for a photograph. In each of the following situations, how many ways are there for the family to line up so that the mother is next to at least one of her daughters? The ...
3
votes
2answers
231 views

For positive integers between 999 and 100 inclusive, how many contain the digit 5?

The question comes in two parts: For positive integers between 999 and 100 inclusive, how many contain the digit 5 at least once? For positive integers between 999 and 100 inclusive, how many contain ...
1
vote
2answers
74 views

Person with seven friends invites subset of three for one week

Suppose that a person with seven friends invites a different subset of three friends to dinner every night for one week (seven days). How many ways can this be done so that all friends are included at ...
2
votes
0answers
34 views

Ways to seat $n$ couples around a circular table with restriction [duplicate]

How many ways are there to seat $n$ couples around a circular table such that no couple sits next to each other? I know that since there are $n$ couples, there are $2n$ people. I need to use ...
3
votes
1answer
95 views

Combinatorics Question Involving Arranging Letters in INTELLIGENT with Restriction [duplicate]

How many ways are there to arrange the letters in INTELLIGENT with at least two consecutive pairs of identical letters? I know that we would use the inclusion exclusion principle here and that there ...
3
votes
1answer
54 views

Combinatorics Question Asking How Many Integer Solutions Given Different Restrictions

How many integer solutions of $x_1 + x_2 + x_3 + x_4 = 28$ are there with: (a) $0 ≤ x_i ≤ 12$? (b) $−10 ≤ x_i ≤ 20$? (c) $0 ≤ x_i, x_1 ≤ 6, x_2 ≤ 10, x_3 ≤ 15, x_4 ≤ 21$? \ \ My attempts (I was ...
2
votes
2answers
61 views

Doubt regarding two permutations and combinations problems

Here are two questions from permutations and combinations: There are 10 identical blankets. These are to be distributed among 4 (distinct) beggars. In how many ways can you do this so that each ...
1
vote
1answer
61 views

How many integer solutions of $x_1$ + $x_2$ + $x_3$ + $x_4$ = 28 are there with [duplicate]

How many integer solutions of $x_1$ + $x_2$ + $x_3$ + $x_4$ = 28 are there with (a) 0 ≤ $x_i$ ≤ 12? (b) −10 ≤ $x_i$ ≤ 20? (c) 0 ≤ $x_i$, $x_1$ ≤ 6, $x_2$ ≤ 10, $x_3$ ≤ 15, $x_4$ ≤ 21? I have tried....
0
votes
1answer
22 views

How to show $ \mathbb P(B \cap C) * \mathbb P(B\cup C)$?

Let B,C be events in a probability space. Show $ \mathbb P(B\cup C) \mathbb P(B\cap C) \leq \mathbb P(B) \mathbb P(C) $. My work: I started to use inclusion- exclusin principle on the left side, but ...