Articles of inclusion exclusion

Find the number of seven-letter words that use letters from the set $\{\alpha,\beta,\gamma,\delta, \epsilon\}$…

Find the number of seven-letter words that use letters from the set $\{\alpha,\beta,\gamma,\delta, \epsilon\}$ and contain at least one each of $\alpha$, $\beta$, and $\gamma$. My attempt: using inclusion/exclusion Let A denotes $\alpha$ is missing, B denotes $\beta$ is missing, and C denotes $\gamma$ is missing. Then, $$\begin{aligned}|A\cup B\cup C|&=|A|+|B|+|C|-(|AB|+|AC|+|BC|)+|ABC|\\ &= 2^7+2^7+2^7-(1+1+1)-0\\ &= 381\end{aligned}$$ $|U|= […]

Counting the number of permutations of a binary multiset that have >=1 partitions all ones?

Given a multiset $S$ of $O$ ones and $Z$ zeros, I’d like to count the number of permutations of $S$ that when partitioned into length $T$ segments have at least one segment that is all ones. ($T$ must of course divide $O+Z$). For example, given the multiset $\{1,1,1,1,1,0,0,0,0,0,0,0,0,0,0\}$ with 5 ones and 10 zeros, the […]

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. However, I’ve run into a problem. Using inclusion exclusion I get: $3^5 – 3 \cdot 2^5 + […]

Number of ways to distribute five red balls and five blues balls into 3 distinct boxes with no empty boxes allowed

Find the number of distributions of five red balls and five blues balls into 3 distinct boxes with no empty boxes allowed so I know if I have just 5 identical balls and 3 distinct boxes, the answer would be $\binom{7}{2}$ but because i have another set of 5 balls, I’m unsure how to proceed […]

find the number of five digit combinations from the set ${1,2,3,4,5}$ where some digits occur at least three times

So to solve this, I started with the total and subtract where some digit occurs only once or twice. Total = $5^5$ Digits are only used once $= 5! = 120$ Digits occur twice: I’m starting to think this is where the inclusion exclusion comes into play because as lulu pointed out, AABCD can occur […]

Use PIE to count the number of $6$-multisets of $$ in which no digit occurs more than twice.

This is one of a set of several problems in my book I am having difficulty not just solving, but also understanding the provided solutions. The given answer is $462 – 336 + 15 = 141.$ I’ll try and see where the terms of the equality above come from. $[6] = \{1, 2, 3, 4, […]

Permutations with no two adjacent numbers being equal

I have been struggeling for some time with the following exercise from a book in discrete mathematics. It is an inclusion-exclusion principle exercise. How many permutations of 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 are there in which no two adjacent numbers are equal? I have come thus far: Let S be […]

Counting permutations of binary string where all ones within some distance?

Given a binary string consisting of $O$ ones and $Z$ zeros, I’d like to count the number of permutations of that string where all of the ones are within a window (consecutive positions) of length $L$. For example, with 5 ones and 6 zeros, there are 81 permutations where the ones are all within $l=7$ […]

Inclusion Exclusion and lcm

I would like to show that for any positive integers $d_1, \dots, d_r$ one has $$ \sum_{i=1}^r (-1)^{i+1}\biggl( \sum_{1\leq k_1 < \dots < k_i \leq r} \gcd(d_{k_1}, \dots , d_{k_i})\biggr) ~\leq~ \prod_{i=1}^r\biggl( \prod_{1\leq k_1 < \dots < k_i \leq r} \gcd(d_{k_1}, \dots , d_{k_i}) \biggl)^{(-1)^{i+1}}. $$ Note that the rhs of the upper inequality is […]

Counting permutations with given condition

I need to find number of permutations $p$ of set $\lbrace 1,2,3, \ldots, n \rbrace$ such for all $i$ $p_{i+1} \neq p_i + 1$. I think that inclusion-exclusion principle would be useful. Let $A_k$ be set of all permutation that for every permutation $a$ in this set $a_{k+1} \neq a_k + 1$. So our answer […]