Tagged Questions

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.

22 views

85 views

How many integers $\leq N$ are divisible by $2,3$ but not divisible by their powers?

How many integers in the range $\leq N$ are divisible by both $2$ and $3$ but are not divisible by whole powers $>1$ of $2$ and $3$ i.e. not divisible by $2^2,3^2, 2^3,3^3, \ldots ?$ I hope by ...
18 views

Is Site Percolation with Bernoulli variables i.i.d. independent and identically distributed?

I cannot understand the identically distributed part in the i.i.d assumption. Consider a site percolation where each event is a Bernoulli variable. Does this mean ...
41 views

How many integers in $\{500,…,1000\}$ are not divisible by 3, 7 or 13?

I am wondering what the best way to approach this question is. I thought that I would calculate the number of integers that aren't divisible by 3, 7 or 13 in $\{1,2,...,1000\}$ as well as the number ...
54 views

Find the value of P(Y|X)

If $$P(X)=\frac{1}{4},$$ $$P(Y)=\frac{1}{3},$$ and $$P(X \cap Y) =\frac{1}{2}.$$ $$P(Y | X)= \frac{P(X \cap Y)}{P(X)}$$ But by using this formula, I got an incorrect answer. $1/3$ is the right ...
50 views

Is this equation true?

As the question states, does this equation hold true? $\sum_{j=0}^n \sum_{E \in {n \choose j}} (-1)^{|E|}(n-|E|)! = \sum_{j=0}^n(-1)^j(n-j)!{n \choose j}$ From what I understand, this holds true at ...
37 views

How many fix point free permutations of 5 elements are there? [duplicate]

I am trying to find out how many fix point free permutations of 5 elements there are. A permutation is fix point free, if $\pi (i) \neq i$. I am trying to solve this problem using the inclusion ...
104 views

How many positive integers from set $\{1,2…,10^{30}\}$ can't be represented as 2nd, 3rd, or 5th power of some positive integer?

An interesting problem I ran across. My guess is that it can be solved somehow using inclusion-exclusion principle. It would be a fun thing to learn how to do this, so I could use that knowledge in ...
210 views

Proving $\sum_{k=1}^{n}{(-1)^{k+1} {{n}\choose{k}}\frac{1}{k}=H_n}$

I've been trying to prove $$\sum_{k=1}^{n}{(-1)^{k+1} {{n}\choose{k}}\frac{1}{k}=H_n}$$ I've tried perturbation and inversion but still nothing. I've even tried expanding the sum to try and find ...
45 views

Counting GF($q=8$) matrices with a certain property

Let us denote by $\boldsymbol{v}_i$ the columns of an $m \times n$ GF($8$) matrix. The field elements are enumerated $\{0,1,2,...,q-1\}$. To define the arithmetic operations between field elements, we ...
94 views

Probability of choosing $n$ numbers from $\{1, \dots, 2n\}$ so that $n$ is 3rd in size

We uniformly randomly choose $n$ numbers out of $2n$ numbers from the group $\{1, \dots, 2n\}$ so that order matters and repetitions are allowed. What is the probability that $n$ is the $3^{\text{rd}}$...
53 views

How many strings of 12 lowercase letters with repetitions

Consider strings of 12 lowercase letters, such as aksdjmnuuyio. How many strings either are a repetition of 2 strings of 6, such as aksdjmaksdjm, or a repetition of three strings of 4, such as ...
32 views

Inclusion-exclusion formula and its alias names

I am reading Probability by A. N. Shiryaev. One of the problems refers to "inclusion-exclusion formulas", also known as Poincaré’s formulas, Poincaré’s theorems, Poincaré’s identities. One of my ...
32 views

Combined probability of hit in look up tables with some common index bits

Consider two tables A and B consisting of $l_a$ and $l_b$ counters respectively - $l_a$ and $l_b$ are powers of two and the counters are initialized to zero. Each table has its own index ...
153 views

Find the probability that a word with 15 letters (selected from P,T,I,N) does not contain TINT

If a word with 15 letters is formed at random using the letters P, T, I, N, find the probability that it does not contain the sequence TINT. (I just made up this problem.)
38 views

50 views

I have the follow two questions : How many sequences $a_1,a_2,...,a_n$ in length $k$ so $a_i \in \{1,2,3,4....,n\}$ satisfy : 1) $a_1<a_2<....<a_k$ while $(a_{i+1} \neq a_i+1)$ 2) $a_1 \... 1answer 32 views Problem on Inclusion & Exclusion Principle Book has the following & solution to it too, pls clear my confusion: On rainy day , five gentlemen A, B, C,D, E attend a party after leaving their umbrellas in a checkroom. After the party is ... 1answer 41 views Probability - Combinations I am having big problems with this exercise: There are$n$customers and$k$types of products and number$i$, where$n \ge k \ge i$. I have to find the probability of the situation where ... 1answer 26 views How to get this complementary form of derangement written in a Wikipedia article? In this article, how do they get the complementary form of $$\Big|S\setminus\bigcup_{i=1}^{n}A_i\Big|=\sum_{k=0}^{n}(-1)^k\binom{n}{k}\alpha_k$$ from $$\Big|\bigcup_{i=1}^{n}A_i\Big|=\sum_{k=1}^{n}(... 1answer 45 views Related problem to covering a circle with random arcs I have a problem setup wherein we have (the following are all integers) a sequence of length G, and N reads of length L. I'm interested in the problem where we consider the sequence to be ... 3answers 88 views Inclusion–Exclusion Identical Computers Problem Find the number of ways to distribute 19 identical computers to four schools, if School A must get at least three, School B must get at least two and at most five, School C get at most four, and ... 0answers 42 views Using the Inclusion-Exclusion Principle I'm having some trouble with the following homework problem: Given that A_1, A_2, ..., A_n are some collection of subsets of S, and no element of S lies in more than two of these sets, write an ... 2answers 56 views Combinatorics - Number of Paths in a Grid with a Hole Given a 12\times12 grid with a hole of 4\times4 in its middle, how many short paths (right or up only) are there from (0,0) to (12,12). I tried using inclusion-exclusion by counting the ... 1answer 102 views Probability that duplicates are still in the deck after X card drawn Deck has 30 cards, out of which 5 cards have duplicates (20 cards are unique, 5 cards have 2 copies each). If you draw X cards from the deck (without returning), what is the probability that there ... 1answer 56 views How many 5 card poker hands contain at least 1 red and 1 black card? How many 5 card poker hands contain at least 1 red and 1 black card? I used inclusion-exclusion to calculate my answer. The number of total poker card hands are:$$52\choose 5$$I have 26 red ... 2answers 44 views Minimizing the intersection of three sets Let the sets A,B,C which are all subsets of a larger set N. If N(A), N(B), N(C), N are the populations respectively, then i need to find the minimum value of the population of their intersection ... 2answers 56 views The inclusion and exclusion criteria I've learned that in probability course, in the exercise we are asked to prove that: given n sets A_1,\ldots,A_n,$$ \left|\bigcup_i A_i\right| \ge \sum_i|A_i| - \sum_{i\ne j}|A_i\cap A_j|\;.$$... 1answer 69 views Luis Suarez goalscoring record. Problem: The 2013-14 season was a short-lived ray of hope in an otherwise long dark night for the world’s greatest football team. The team played 38 league games and the main contributing ... 1answer 64 views How many ways to arrange these gifts? (Inclusion-exclusion\derangement) Each one of 30 people has bought 2 identical presents for the poor (every person's gifts are different from everyone else's). All the gifts were put in a large bag. In turns, 30 poor people ... 2answers 99 views Inclusion - Exclusion Problem - Suppose that a person with seven friends… Can someone please explain to me how to approach this problem: Suppose that a person with seven friends invites a subset of three friends to dinner every night for one week (seven days). How many ... 1answer 80 views How many ways are there to order a subset of 30 such tickets with the constraint that each of the eight musicals appears on at least one ticket? There are 8 Broadway musicals and they offer a special three-night package (Friday, Saturday, Sunday nights) where one can order one ticket that is good for 3 different musicals on successive nights (... 1answer 28 views Chances for 3 6-sided die and 2 8-sided die to have a sum of 12 If 5 dice are rolled, 3 6-sided die and 2 8-sided die, how do I come up with the chances that the sum will be 12? I've figured that there are 13824 total combinations, but can't figure out ... 0answers 14 views Calculating the number of permutations that do not have at least one set of duplicate elements adjacent. Ok, so I've got a set of elements, some are duplicates but each are considered unique as far as set-making goes. I need to find how many permutations exist that do not put two of the duplicates next ... 1answer 40 views Probability of chosen urns being filled after randomly throwed 2 balls k times We have n urns. Repeat next process k times: choose 2 distinct urns, throw ball into each. What is the probability of choosing 2 urns with at least 1 ball in it? (e.g. we have 8 urns. Then choose 3 ... 2answers 150 views Prove an identity in a Combinatorics method It is a combinatorics proof. Anyone has any idea on how to prove$$\sum \limits_{i=0}^{l} \sum\limits_{j=0}^i (-1)^j {m-i\choose m-l} {n \choose j}{m-n \choose i-j} = 2^l {m-n \choose l}\;$$We ... 3answers 133 views How many$5$-digit numbers (including leading$0$'s) are there with no digit appearing exactly$2$times? How many$5$-digit numbers (including leading$0$'s) are there with no digit appearing exactly$2$times? The solution is supposed to be derived using Inclusion-Exclusion. Here is my attempt at a ... 2answers 46 views What is probability that out of the first half on N objects, none will be matched with their own label? The problem: We have N (even) objects ordered$o_1 ... o_N$, each having their own label. The labels are reassigned to the objects randomly. What is the probability that that neither of the first$N/...
Suppose $A$ a linear transformation and $A^+$ its Moore-Penrose pseudoinverse. At this stage of the derivation in a book I am using as a reference, the operator $AA^+$ is known to be an orthogonal ...