Skip to main content

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.

Filter by
Sorted by
Tagged with
3 votes
2 answers
58 views

$(w_{1},w_{2},w_{3},\dots,w_{7})$ integers with $20\le w_{i} \le 22$ such that $\sum_{i=1}^{7}w_{i} = 148$

How many $(w_{1},w_{2},w_{3},\dots,w_{7})$ where each of the $w_{i}$'s are integers and $20\le w_{1},w_{2},w_{3},\dots,w_{7}\le 22$ such that they satisfy $$w_{1}+w_{2}+w_{3}+\dots+w_{7}=148$$ ATTEMPT ...
JAB's user avatar
  • 189
3 votes
1 answer
85 views

definition of cyclotomic polynomials

The $n$th cyclotomic polynomial can be expressed via the Mobius function as follows: $$\Phi_n(x) = \prod_{\substack{1\le d\le n\\d\mid n}}(x^d - 1)^{\mu(\frac{n}{d})}$$ In every reference I have ...
node196884's user avatar
0 votes
0 answers
44 views

Combinatorics questions, people in a row, i'th person not standing right to (i-1)th person [duplicate]

The question goes like: There are n people in a row, how many ways are there to rearrange them, such that for all $0 \le i \le n-1$, the people who stood in original (i+1)th place, is not standing ...
csmathstudent8's user avatar
0 votes
2 answers
43 views

Book of Proof chapter 3 section 7 (Inclusion-Exclusion Principle), exercise 4b. Need help finding the answer algebraically.

I've been stuck on Chapter 3 section 7 (Inclusion-Exclusion Principle) of the Book of Proof 3rd edition, in the exercises part, trying understand the logic behind the answer to question 4b: This ...
Kneff's user avatar
  • 1
2 votes
2 answers
127 views

Counting binary strings with $9$ ones and containing $11011$

I am currently trying to solve this problem: How many strings of 20 bits are there with exactly nine $1$s and containing at least one occurrence of $11011$ as a substring? I don't have problems with ...
Shicchan Zero's user avatar
0 votes
2 answers
51 views

How many different 8 characters passwords with 2 upper-case 2 digits 4 lower-case

A web-banking password is always 8 characters long and it always comprises two upper-case letters from the standard English alphabet, two digits, and four lower-case letters from the standard English ...
Mzq's user avatar
  • 254
0 votes
2 answers
54 views

At least two consecutive 'A's

How many permutations of A,A,A,B,B,C,C,D,D,D contain at least two consecutive 'A's? My attempt: The number of permutations with exactly two consecutive 'A's: $$ W(P_{AA})=\frac{9!}{1!2!2!3!}-2\cdot \...
Proper Illumination's user avatar
2 votes
3 answers
117 views

The number of ways $abcabcabc$ can be arranged so that no word contains the sequence $abc$

My approach is as follows: Total no. of permutations - abc appears once - twice - thrice $For \ 1 \ abc \ : \ $ We can arrange $ \ a,b,c,a,b,c \ $ (in $\frac{6!}{2!2!2!}$ ways),then subtract the ...
User's user avatar
  • 85
4 votes
0 answers
92 views

Find number of ways to arrange 1 to n in a line so that no two consecutive numbers are adjacent

Find number of ways to arrange $1$ to $n$ in a line so that no two consecutive numbers are adjacent. I know this is https://oeis.org/A002464 !! I tried it with inclusion exclusion and got the number ...
Makar's user avatar
  • 2,269
6 votes
1 answer
196 views

Inclusion-Exclusion confusion: Meeting exactly one friend in lunch time during a semester

From Trotter's Combinatorics Textbook, I was working on this problem from his Inclusion-Exclusion Chapter: A graduate student eats lunch in the campus food court every Tuesday over the course of a $...
Bob Marley's user avatar
4 votes
1 answer
68 views

Derangements of LEMMA with Inclusion/Exclusion

I'm trying to use Inclusion/Exclusion to find the number of derangements of $\text{LEMMA}$. Recall that a derangement of a word is an arrangement of the letters in which no letter is in the correct ...
HBH's user avatar
  • 63
1 vote
1 answer
44 views

find the number of ways to distribute 30 students into 6 classes where there is max 6 students per classroom

here is the full question: Use inclusion/exclusion to find the number of ways of distributing 30 students into six classrooms assuming that each classroom has a maximum capacity of six students. Let $...
sor3n's user avatar
  • 15
0 votes
1 answer
53 views

How is Principle of Inclusion-Exclusion (PIE) utilized in this solution?

I solved this problem using linearity of expectation but am trying to understand the above solution that uses the principle of inclusion exclusion. I'm struggling to understand how it is applied in ...
mk0219's user avatar
  • 178
2 votes
1 answer
62 views

Compute the probability that a hand of $13$ cards contains the ace and king of at least one suit?

Compute the probability that a hand of $13$ cards contains the ace and king of at least one suit? Approach 1 In my first approach I took all 8 cards of aces and kings aside and then made 4 group each ...
Abhishek Singh's user avatar
0 votes
0 answers
55 views

Using inclusion exclusion to find the number of ways to arrange a,a,a,b,b,b,c,c,c such that no adjacent letters are the same? [duplicate]

When trying to solve this problem I considered the principle of inclusion exclusion where the set U is the number of all possible arrangements, the set A is the number of arrangements that have "...
Math Undergrad Student's user avatar
0 votes
1 answer
47 views

How many four digit numbers (including leading zeros) have exactly one 8 and no digits appearing two times?

I am trying to best interpret this question. If I interpret this as no digit appears exactly two times then I used the inclusion exclusion principle: There are $4(9^3)$ four digit numbers that have ...
Math Undergrad Student's user avatar
1 vote
1 answer
40 views

Inclusion exclusion formula for Betti numbers

Let $K$ be simplicial complex with $K1$ and $K2$ such that $K1 \cup K_2 = K$. Does the following hold ? $$\beta_i (K) = \beta_i (K1) + \beta_i (K2) - \beta_i (K1 \cap K2) $$ $\beta_i$ is the i-th ...
Dino Cerimagic's user avatar
1 vote
0 answers
40 views

How many ways can a child take eleven pieces of candy from four types if the child does not take exactly two pieces of any type?

I solved this problem for an assignment and my solution was (using the principle of inclusion exclusion): $$ N(U) - N(A \cup B \cup C \cup D) = {4+11-1 \choose 11} - \left[ 4 {3+9-1 \choose 9} - 6 {2+...
Math Undergrad Student's user avatar
2 votes
0 answers
68 views

Application of the Principle of Inclusion/Exclusion and the Binomial Theorem in Combinatorial Proofs [closed]

Consider a set $Z=X \cup Y$, where $X=\left\{x_1, \ldots, x_n\right\}$ is a set of blue elements and $Y=$ $\left\{y_1, \ldots, y_m\right\}$ is a set of red elements. (a) How many subsets of $Z$ ...
Allison's user avatar
  • 195
1 vote
1 answer
70 views

Derangements for couples in a round table

Question: Let ( m(n) ) denote the number of ways of seating ( n ) married couples around a circle such that no husband sits next to his wife. Then, the remainder obtained on dividing ( m(5) ) by ( 5 ) ...
OpateItZOpatoOpate's user avatar
2 votes
1 answer
36 views

Sanity Check Streak of Head's

You have a biased coin with probability $\frac{1}{3}$ of heads. If you flip the coin 10 times, what is the probability of having 8 or more heads in a row? I tried doing this question two ways, using ...
John Li's user avatar
  • 157
0 votes
1 answer
57 views

Total permutations for n-married couples

Let A(n) denote the number of ways of seating n-married couples, around a circle, such that men and women sit alternately, and no husband sits next to his wife. Then Compute A(5): I tried applying ...
OpateItZOpatoOpate's user avatar
0 votes
0 answers
58 views

Probability that a jar with 200 jelly beans with 40 colors has at least one of every color.

I am trying to calculate the probability that a jar with 200 jelly beans and 40 possible jelly bean colors does not feature all colors at least 1 time. I am aware of the way to solve this using ...
romanowski's user avatar
2 votes
1 answer
45 views

Counting the amount of injective functions with restriction

First I will say that the exact same question has been uploaded to the site already few years ago but it seems no final answer were given there. Let $$X = \{a,b,c\}, \quad Y = \{1,2,3,4,5,6,7\}.$$ I ...
Dor's user avatar
  • 21
2 votes
0 answers
55 views

Is my solution to count the integer solutions for a linear inequality with bounds correct?

I'm working on a problem where I need to count the number of integer solutions for the inequality $10 \leq x_1 + x_2 + x_3 + x_4 \leq 19$, given that each $x_i$ (for $i = 1$ to $4$) is bounded by $-5 \...
IvanKM's user avatar
  • 31
1 vote
1 answer
52 views

Understanding the Inclusion/Exclusion Principle

Problem: A renovation of an arena proposes to give the seats colors from a color scheme with $5$ different colors. In each row, all $5$ colors must be used at least once. In how many different ways ...
Thai Sartell's user avatar
0 votes
2 answers
53 views

No adjacent empty boxes with PIE

*PIE = inclusion-exclusion How many ways are there to distribute 10 balls into 5 distinct boxes such that no two adjacent boxes are empty? Note: the same question statement. I believe the question ...
zxayn's user avatar
  • 127
1 vote
1 answer
33 views

a probability question on ball choosing from an urn

In a box there are $b$ black, $w$ white, and $r$ red balls. We choose $n$ balls from the box with replacement where $n\leq \min(b,w,r)$. Find the probability that we get at least 2 black balls and at ...
Probability student's user avatar
0 votes
0 answers
35 views

Probability of system working using conditional probabilities

A system consists of components 1, 2, 3, and 4 that work with probability p1, p2, p3, and p4 respectively. The signal can only pass through a component if it is working. The components are independent ...
entewurzel's user avatar
2 votes
1 answer
81 views

In how many ways can 25 students form 5 groups of 5 such that no group consists of students with the same year of birth?

There are $25$ distinguishable students in total. They can be arranged in groups of $5$ such that every group has a unique year of birth shared among all the members of the group (meaning there are $5$...
HEISENBERG9871's user avatar
3 votes
2 answers
106 views

Number of words with $3n$ letters where no $3$ consecutive letters are the same

This is similar to this question, and I wanted to apply the technique of inclusion-exclusion to see if I understand it. I try to explain as many details as possible in my reasoning, and I would like ...
pyridoxal_trigeminus's user avatar
4 votes
2 answers
85 views

Feasibility of Meeting Patterns in Combinatorial Lunch Gatherings

I encountered a problem in Applied Combinatorics as detailed here which presents an intriguing scenario: Over a 15-week semester, a graduate student has lunch in the campus food court every Tuesday, ...
LeafGlowPath's user avatar
  • 7,243
1 vote
1 answer
61 views

What’s the chance that at least one room has students all from the same grade level?

Additional Info: 24 students in a Zoom Meeting that has 4 breakout rooms. Each breakout room has 6 students. Additionally there are 6 students belonging to each of the 4 grade levels. I want the ...
Roger Lawrence's user avatar
0 votes
1 answer
65 views

Distribution of the size of the union of repeated random draws

I have $d$ items (say numbers 1 to $d$). I would like to uniformly randomly sample $k$ items out of $d$, without replacement. Suppose I do such draws independently $n$ times. I now want to take the ...
kzliu's user avatar
  • 3
0 votes
1 answer
144 views

Arrange INDEPENDENCE such that no vowels occur together.

Find the number of arrangements of the word INDEPENDENCE such that no vowels occur together, I tried to solve this with 2 approaches, however, I am not able to get the answer my textbook gives... I ...
L A's user avatar
  • 3
2 votes
1 answer
104 views

Question about the proof of the Inclusion–exclusion principle (In this book, the author calls it the Poincare's formula)

This is from the book Exercises in Integration by Claude George, page 37 This is an exercise that wants us to prove the so called "Poincare's formula" and this is the solution that the book ...
G.t.g.h's user avatar
  • 161
0 votes
0 answers
125 views

Counting argument for an alternating sum identity $\sum_{b=0}^{\binom{a}{c}}(-1)^{b+1}f(a,b,c)=(-1)^{a+c}\binom{a-1}{c-1}$

Let $f(a,b,c)$ be the number of ways of writing a set of size $a$ as a union of $b$ distinct subsets of size $c$. I've noticed that $$\sum_{b=0}^{\binom{a}{c}}(-1)^{b+1}f(a,b,c)=(-1)^{a+c}\binom{a-1}{...
Jacob's user avatar
  • 2,407
0 votes
0 answers
29 views

Combination of N elements when number of remaining elements decreases by some factor

I have following elements (in this example I have 12 elements, but generally it can be any set of 3, 12, 27, 48, 75, 108... elements conforming to $3 * m^2$ where $m\in N$): $$A_1a_1, A_1b_1, A_2a_2, ...
Bojan Vukasovic's user avatar
0 votes
0 answers
42 views

We have 3 times 'A', 4 times 'Y' and 5 times 'Z'. Count the number of strings that there are no consecutive same characters [duplicate]

So I need to find the number of strings with 3 times 'A', 4 times 'Y' and 5 times 'Z' such that there are no consecutive same characters. I was thinking from all strings to substract those with &...
Peter Staudt's user avatar
2 votes
2 answers
133 views

How many numbers between 10 and 100 are divisible by 3 but not 2 nor 7?

My working: Let $|M_3|$ denote the number of integers between 10 and 100 that divides 3. So we have $$|M_3|= \lfloor \frac{100}{3} \rfloor-3=30$$, and similarly, $$|M_2|=\lfloor \frac{100}{2}\rfloor-...
Holland Davis's user avatar
0 votes
0 answers
73 views

How to use Generating Functions to solve the problem: Number of bit strings of length four do not have two consecutive 1s

I read this QA answer and has problems about how it is solved. The above referenced post's problem is: How many bit strings of length four do not have two consecutive 1s? Since generating function is ...
An5Drama's user avatar
  • 416
0 votes
2 answers
61 views

How many numbers between 1 and 900 cannot be divided by 4, 5 or 6

I'm trying to find total amount of numbers between 1 and 900 that is not dividable by 4, 5 or 6. For example, number 16 is not part of the total because 16 is dividable with 4. I use inclusion and ...
user avatar
0 votes
0 answers
155 views

Inequality of inclusion-exclusion terms

While analyzing the properties of an algorithm I am working on, I came up with the following inequality of inclusion-exclusion terms. Let $0 \leq i \leq j < k$ be natural numbers. Then, I want to ...
Tobias's user avatar
  • 15
1 vote
0 answers
35 views

What is the exact probability of rolling every possible result on an a-sided die at least b times each after rolling c times?

I have found answers to similar, much simpler questions on this site before (such as here How do you calculate probability of rolling all faces of a die after n number of rolls?), but can't find ...
Izzhov's user avatar
  • 223
1 vote
2 answers
51 views

Practical illustration of the inclusion-exclusion principle

I am currently doing a combinations problem that has two parts. Part A: There are $26$ uppercase letters in the alphabet (A, B, C ... Z). How many $20$-letter words contain the subword 'DOWNTIME' ...
Rayyan Khan's user avatar
0 votes
1 answer
234 views

In how many ways $n$ balls can be given to $k$ children so that no child gets more than $3$ balls when balls are distinct/identical?

In how many ways $n$ balls can be given to $k$ children so that no child gets more than $3$ balls when balls are a) balls are distinct b) balls are identical I am trying to solve this problem using ...
Zek's user avatar
  • 309
0 votes
1 answer
467 views

What is the probability that a positive integer not exceeding 100 selected at random is divisible by 5 or 7?

Q: What is the probability that a positive integer not exceeding 100 selected at random is divisible by $5$ or $7$? Choosing a number from $1$ to $100$ divisible by $5$ is $\frac{5}{100} = \frac{1}{20}...
Funlamb's user avatar
  • 133
0 votes
0 answers
48 views

Is there a limit to the use of the Inclusion-exclusion principle for probability?

I'm scratching my head over this probability problem - can you help me figure out where I'm going wrong? The problem states: $P(A) = P(B) = P(C) = 0.25;$ $P(\color{red}{B}C) = 0;$ $P(AB) = P(AC) = 0....
Thinker Sun's user avatar
0 votes
0 answers
126 views

Number of ways of organising objects (which are in distinct groups) in a line with constraints on segments.

Given $n$ objects split into $K$ groups with respective sizes $h_k = \{h_1, h_2, \dots , h_K\}$, where $\sum h_k = n $, and given $\beta$ boundary points: How many ways are there of organising the ...
Sam Smith's user avatar
1 vote
1 answer
64 views

How many permutations of set are there with 4 fixed points?

Given the set of numbers $A = \left \{ 1, 2, 3, 4, 5, 6, 7, 8 \right \}$. How many permutations leave exactly four numbers fixed? I've considered this as a solution... but then I stumbled upon a ...
runtotherescue's user avatar

1
2 3 4 5
31