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.

learn more… | top users | synonyms

0
votes
1answer
52 views

How to interpret the Generalized Version of Inclusion-Exclusion Principle

This is a follow-up question on the previous post. Let's say there are $n$ properties which are numbered $1,\cdots,n$. And let $A$ be a set of elements which has some of these properties. Then the ...
5
votes
1answer
80 views

Counting square free numbers co-prime to $m$

Counting square free numbers $\le N$ is a classical problem which can be solved using inclusion-exclusion problem or using Möbius function (http://oeis.org/A071172). I want to count square free ...
0
votes
2answers
26 views

Student card handing Inclusion–exclusion principle

I got the following question and would very much appreciate any help with understanding it solution. "5 Student cards are handed to 5 students so that each student gets 1 student card, what is the ...
19
votes
4answers
193 views

Inclusion-exclusion-like fractional sum is positive?

Let $A_1,A_2,\ldots,A_n$ be finite nonempty sets. Is it true that $$\sum_{i=1}^n\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup ...
12
votes
4answers
390 views

How do I prove this combinatorial identity using inclusion and exclusion principle?

$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity ...
0
votes
2answers
52 views

Applying Inclusion-Exclusion principle

How to apply principle of inclusion-exclusion to this problem? Eight people enter an elevator at the first floor. The elevator discharges passengers on each successive floor until it empties on ...
1
vote
0answers
25 views

Product of Dependent Bernoulli variables

Let $B_{i,n}$ with $i=1,...,n$ be the triangular Bernoulli array defined as $$ B_{i+1,n} = B_{i,n}\,R_{i+1,n}+\left(1-R_{i+1,n}\right)\,F_{i+1,n}, $$ where $R_{i,n}$ and $F_{i,n}$ are iid Bernoulli ...
3
votes
1answer
115 views

A Generalized version of Inclusion-Exclusion Principle?

I recently read Doron Zeilberger's paper on Inclusion-Exclusion Principle. Let's say there are $n$ properties which are numbered $1,\cdots,n$. And let $A$ be a set of elements which has some of ...
14
votes
3answers
183 views

Count permutations of $\{1,2,…,7\}$ without 4 consecutive numbers - is there a smart, elegant way to do this?

Here's a problem I've solved: Count permutations of $\{1,2,...,7\}$ without 4 consecutive numbers (e.g. 1,2,3,4). So I did it kinda brute-force way - let $A_i$ be the set of permutations of $[7]$, ...
2
votes
0answers
26 views

What determines the number when excluding in Inclusion Exclusion problems

My question might be a bit poorly articulated as I am not sure what I'm asking is actually called. I am faced with an Exclusion/Inclusion problem that goes like this: You have $25$ identical cakes ...
0
votes
1answer
26 views

Calculating the probability of getting a full bucket in a hash table with open addressing

I have a problem where I'm trying to calculate the probability of getting a full bucket when I use a hash table with open addressing. What I have: A hash table with 128 buckets, each bucket can ...
2
votes
1answer
72 views

Integers divisible by 4 but not by 3 and 16

For $n \leq 1000$ I am interested in the integers who are divisible by 4 but not by 3 and 16. Say $a_i$ is the property that an integer is divisible by $i$. Inclusion-Exclusion gives us: \begin{align} ...
2
votes
1answer
32 views

Using Inclusion-Exclusion Principle to find number of ways to distribute envelopes

I have encountered this problem on a past paper: In how many ways can 675 identical envelopes be divided, in packages of 25, among four student groups so that each group gets at least 150, but no ...
3
votes
1answer
56 views

Inclusion-Exclusion: INTELLIGENT permutations

How many ways are there to arrange the letters in INTELLIGENT with at least two consecutive pairs of identical letters? I got an answer of ...
0
votes
1answer
57 views

number of ways to choose pairs of nonadjacent people from $2k$ people sitting in a circle

The following is problem 19 in Chapter 2 from Richard Stanley's Enumerative Combinatorics, vol. 1 (2nd ed.): Suppose that $2k$ persons are sitting in a circle. In how many ways can they form pairs if ...
0
votes
0answers
28 views

Given $d>8$ boxes and $n$ balls. . What is $P(A \cup B \cup C)$?

Given $d>8$ boxes and $n$ balls. Consider event $A$=boxes numbered $1,2,3,4$ receive 0 balls.$B=3,4,5,6$ receive 0 balls, $C=5,6,7,8$ receive zero balls. What is $P(A \cup B \cup C)$? ...
5
votes
0answers
71 views

Summation of a function

Let $n$ is a positive integer. $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ is the complete prime factorization of $n$. Let me define a function $f(n)$ $f(n) = p_1^{c_1}p_2^{c_2}...p_k^{c_k}$ where $c_k = ...
0
votes
1answer
28 views

What can you say about this set operation using principle of inclusion/exclusion

Given: A = [ Aaron features ], B = [Bob features], X = [all countries in Europe ] What must be true if: |A ∩ B ∩ X| = 1 Even though I don't see the relation between cardinality of sets, I ...
19
votes
5answers
491 views

In how many ways can $1000000$ be expressed as a product of five distinct positive integers?

I'm trying to solve the following problem: "In how many ways can the number $1000000$ be expressed as a product of five distinct positive integers?" Here is my attempt: Since $1000000 = 2^6 \cdot ...
1
vote
1answer
30 views

Inclusion Exclusion with 4 sets: How many integers between 1 and 100 are divisible by 2 or 3 or 5 or 7?

How many numbers between 1 and 100 are divisible by 2 or 3 or 5 or 7? The solution I had gives a different answer from what was provided, so I was wandering if anyone could tell me what mistake I ...
0
votes
0answers
42 views

inclusion–exclusion principle formula in probability for general case

For the system reliability analysis of complex systems, I'll use the formula below after a point in a custom computer code. I know that for the n=2 case, formula result is $P_1+P_2-P_1.P_2$ ($P$ : ...
0
votes
2answers
46 views

Prove the inclusion-exclusion formula

We just touched upon the inclusion-exclusion formula and I am confused on how to prove this: $|A ∪ B ∪ C| =|A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|$ We are given this hint: To do ...
0
votes
1answer
56 views

Number of permutations of $A=\{1,2,3,\dots,n\}$ such that $|x_i-x_j|\ne|i-j|$ of every $i,j\in A$

Let $B$ be the permutation of $A=\{1,2,3,\dots,n\}$ such that $|x_i-x_j|\ne|i-j|$ of every $i,j\in A$ where $x_k$ is $k-th$ element of $B$. How many different $B$ exist? On first sight it doesn't ...
1
vote
0answers
44 views

Inviting 4 friends out of 8 for a week such that each friend visits at least once

Dave is inviting 4 friends out of 8 for a week how many possibilities there are such that each friend visit at least once. Let's number the friends for brevity, 1 to 8. This is like asking how ...
0
votes
1answer
38 views

Probability of placement in a random ordering of integers (inclusion-exclusion rule)

Problem Let $a_1, ..., a_n$ be a random ordering of integers $1,...,n$. What is the probability that there exists no $1 \leq i \leq n$ such that $a_i = i$? Attempted solution For #1: let $A_i = ...
0
votes
2answers
33 views

Summation with Multiple Indices

How would the following summation work? $\sum_{r,s,t \ge 0_{r+s+t=n}} \binom{m_1}{r} \binom{m_2}{s} \binom{m_3}{t}$ How would you choose the value for the next integer in the series? For example, ...
1
vote
1answer
94 views

Inclusion-Exclusion question

A careless payroll clerk is placing employees’ paychecks into pre-labeled envelopes. The envelopes are sealed before the clerk realizes he didn’t match the names on the paychecks with the names on the ...
4
votes
1answer
49 views

Determine the number of ways for n couples to stand in a line so that no one stands beside his or partner (explanation for the answer)

I'm not quite sure if I'm understanding solution to following problem: "Determine the number of ways for n couples to stand in a line so that no one stands beside his or her partner." The general ...
4
votes
2answers
80 views

number of pairs formed from $2n$ people sitting in a circle

I am trying to understand the solution to the following problem: Suppose that $2n$ persons are sitting in a circle. In how many ways can they form $n$ pairs if no two adjacent persons can form a ...
1
vote
1answer
52 views

Question about probability theory inclusion/exclusion

So, I've been trying to teach myself probability theory, and I think I have the idea down, but I wanted to make sure I am on the right track. Thus, I was wondering if people here could confirm that I ...
0
votes
3answers
113 views

There are 5 students. Must form 3 teams and every team must have 2 students in common.

This is the problem. Suppose there are 5 students and we are trying to form 3 distinct scientific teams such that Every student must join into at least one team (no student should left without a ...
0
votes
1answer
66 views

Ways to distribute candies using inclusion/exclusion

I have 173 million pieces of candy. There are 5 students. In how many ways can this distribution be made, assuming that each student receives at least 1 million candies, Student B receives at most 10 ...
2
votes
1answer
77 views

How to extend the Inclusion Exclusion Principle to an XOR situation

For calculating the probability of the union of independent events, $P(A_1\cup A_2\cup A_3\cup A_4)$ one can use the Inclusion Exclusion principle: $$ \eqalign{ P\Bigl(\bigcup_{i=1}^n A_i\Bigr) = ...
1
vote
1answer
31 views

Number of ordered quadruples sets

I'm trying to tackle the following question, but got no clue how to do so (I know it is not very popular not showing any effort, but this time I really don't know what to do). Iv'e seen a solution ...
5
votes
1answer
69 views

If we are given that a list of $n$ numbers has $11,660$ derangements, what is the value of $n$?

The Full Question For the positive integers $1,2,3,\dots n-1,n$, there are $11,660$ where $1,2,3,4,5$ appear in the first five positions. What is the value of $n$? My Work First I considered all ...
0
votes
2answers
31 views

Simple combinatorics - inclusion and exclusion problem

There are 3 groups ${{A}_{1}},{{A}_{2}},{{A}_{3}}$ What we know about them : \begin{align} & |{{A}_{1}}|=|{{A}_{2}}|=|{{A}_{3}}|=n \\ & |{{A}_{1}}\cup {{A}_{3}}|=2n-q \\ & ...
0
votes
1answer
26 views

# of Numbers from 1 to 2400 which are divisible by (8 or 5) or not by 6

I need to apply the Principle of Inclusion-Exclusion here: Hence I get $$|A_8| + |A_5| + |\neg A_6| - |A_8 \cap A_5| - |A_8 \cap \neg A_6| - |\neg A_6 \cap A_5| + |A_8 \cap A_5 \cap \neg A_6|$$ I ...
1
vote
1answer
79 views

Understanding inclusion exclusion principle (with example question).

Hi here is a question that i solved with generating functions , and i try to solve the same question with the inclusion exclusion principle. Question: We have four type of balls - ...
1
vote
1answer
113 views

let s be a set with N elements and A1,…,A101 be 101 (possibly not disjoint) subsets of S

So the question I'm having problem with is the following: let s be a set with N elements and A1,...,A101 be 101 (possibly not disjoint) subsets of S with the following 5 properties: each elements ...
0
votes
1answer
104 views

How many lattice paths with step S and W are there that begin at (0,0), end at (-12,-12)

How many lattice paths with step $S$ and $W$ are there that begin at $(0,0)$, end at $(-12,-12)$ and do not go through any of the points $(-1,-4), \space (-5,-3), \space (-9,-11)$? I'm unsure of how ...
3
votes
1answer
125 views

Distribute $10$ distinct prizes to $4$ students

Inclusion Exclusion Used Theorem 8.1 The Question: In how many ways can one distribute $10$ distinct prizes to $4$ students with exactly $2$ students getting nothing. b) How many ways have at ...
0
votes
1answer
100 views

How Many Ways Can 3 x's 3 y's and 3 z's be arranged so that no consecutive triple of the same letter appears

My Question I want to know two things: is my solution correct, and is there another, more clever, way to solve it? My Solution There are a total of $\frac{9!}{3!3!3!}$ arrangements of $xxxyyyzzz$. ...
1
vote
3answers
309 views

Seating permutations for 10 people where 2 people always sit together and 2 people never sit together

We have to seat 10 people in a row. Condition: two people always sit together and two people never sit together. My attempt: Let the two people who always sit together be taken as 1 person for the ...
1
vote
1answer
45 views

Number of lists of given size with given max element value where K cells (possibly overlapping) can have only multiples of certain numbers

I have been trying to wrap my head around a problem. The problem is reduced form of a problem from a programming contest. I have been trying to apply inclusion-exclusion principle toward solving this, ...
3
votes
0answers
53 views

Can the principle of inclusion/exclusion be used to count elements in the intersection of a sequence of sets?

The principle of inclusion-exclusion (PIE) is often used to count the number of elements in a union of $n$ sets in terms of an alternating sum of their various intersections: $$ \left |\bigcup_{i \in ...
3
votes
2answers
66 views

Use the PIE to prove an identity

Use the PIE to prove, $n!{{n-1}\choose {k-1}} = \sum_{i=1}^k (-1)^{k-i} {k \choose i} \bar i^{n}, \ 1 \le k \le n$ Where, $\bar i^{n}= i(i+1)...(i+n-1)$ Edit Actually,I can solve it now. And it's ...
1
vote
1answer
80 views

Solving probability question using the inclusion exclusion principle

Question: $F$ is the set of all functions from a $n$-set to $B=\{a,b,c\}$. In a random experiment of selection of functions from $f$ assume that every $f\in F$ is equally likely. What is the ...
0
votes
1answer
25 views

No. of ways to shuffle a card

How many ways are there to shuffle N cards such that exactly one card is in the same position?(Assuming that initially the card no. 1 is in the first position,card no.2 is in the second position and ...
4
votes
1answer
88 views

Probability of $m$ out of $n$ rolls of a die being among the numbers $1,2,\ldots,m-1$, for some $m$.

Suppose I have a $k$ sided die with the numbers $1,2,\ldots,k$ on each side, and that I roll it $n$ times ($n<k$). What is the probability that there exists an $m\leq n$, so that $m$ of the $n$ ...
0
votes
1answer
60 views

Inclusion and Exclusion Principles

In a scientific study of 233 imaginary people, each eats at least one meal every day. Of these, 91 eat breakfast, 152 eat lunch and 177 eat dinner. Also, 190 eat either breakfast or 1 lunch, 205 eat ...