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.

1
vote
2answers
56 views

An explicit “formula” for the prime counting function?

It is known that $\log(p_1),\cdots,\log(p_n)$ are linearly independet over $\mathbb{Q}$, where $p_i$ denotes the $i$-th prime. For a number $1 \le k \le n$ let $Log(k)$ denote the vector with respect ...
0
votes
1answer
38 views

Colouring the sides of a hexagon

If the walls of a hexagon shaped room are to be painted so that no two adjacent walls get painted the same colour, and there are 10 colours of paint to be chosen from, how many ways can the room be ...
1
vote
1answer
74 views

What is the probability that no 2 books from the same major will be placed next to each other?

4 mathematics, 3 physics, 2 chemistry (all distinct) books are supposed to arrange on a bookshelf randomly. What is the probability that no 2 books from the same major will be placed next to each ...
0
votes
1answer
28 views

Notation for “or” in inclusion-exclusion formula

Suppose that I have a set $A$ and I want to compute the probability that this set contains at least one of the elements $x_1,\dots, x_n$. In other words, $p(x_1 \in A \text{ or } \dots \text{ or } ...
0
votes
1answer
39 views

Positive Integers between 100 and 999 inclusive that are divisible by 3 but not by 4?

I've reviewed this question and a little stuck on the formula presented: Integers divisible by 4 but not by 3 and 16 and was hoping someone could provide some additional details as to the logic being ...
3
votes
2answers
66 views

How many permutations are there of M, M, A, A, A, T, T, E, I, K, so that no two consecutive letters are the same?

How many permutations are there of $$ M, M, A, A, A, T, T, E, I, K $$ so that there are no two consecutive letters are the same? I would use the Inclusion-exclusion principle where $$ A_{i} = \{ \...
3
votes
1answer
90 views

How to count all the solutions for $\sum\limits_{i=1}^{n} \frac{1}{2^{k_i}}= 1$ for $k_i\in \Bbb{N}$ and $n$ a fixed positive integer?

After reading this question, I would like to just count all solutions for: $$\frac{1}{2^{k_1}} + \frac{1}{2^{k_2}} + \frac{1}{2^{k_3}} + \dots + \frac{1}{2^{k_n}}=1$$ for $k_i\in \Bbb{N}$ (we can ...
0
votes
1answer
20 views

Reverse Inclusion - Exclusion Principle

The Inclusion-Exclusion Principle is usually expressed as a way of determining unions from intersections, i.e. $$\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2)$$ $$\...
-2
votes
1answer
27 views

Why does taking floored root of a natural number x give me all natural numbers up to x which are perfect squares,cubes,fifths etc.

Eg. The number of perfect squares from $1$ to $10^{10}$ is $\left(10^{10}\right)^{1/2}= 10^{5}$ Context:I got this question from this one: Count the number of integers in the range $1$ to $10^{10}$ ...
3
votes
0answers
38 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
12 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
31 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 ...
6
votes
2answers
153 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
26 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
30 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
78 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
39 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
23 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
21 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
46 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
28 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
59 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
100 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
57 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
52 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
59 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$...
0
votes
1answer
37 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
35 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 ...
2
votes
2answers
53 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
75 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
67 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
25 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
83 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
62 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
86 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
54 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
28 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
15 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
34 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
40 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
120 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
63 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
79 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
57 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
43 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,...