Questions tagged [combinatorics]

Counting or enumerating elements in a set or other finite discrete structure.

Filter by
Sorted by
Tagged with
30
votes
3answers
10k views

Extending the birthday paradox to more than 2 people

In the traditional Birthday Paradox the question is "what are the chances that two or more people in a group of $n$ people share a birthday". I'm stuck on a problem which is an extension of this. ...
24
votes
5answers
4k views

What is wrong with this “naive” shuffling algorithm?

This is a follow-up to a Stackoverflow question about shuffling an array randomly. There are established algorithms (such as the Knuth-Fisher-Yates Shuffle) that one should use to shuffle an array, ...
18
votes
5answers
25k views

Probability of drawing a given word from a bag of letters in Scrabble

Suppose you had a bag with $n$ tiles, each with a letter on it. There are $n_A$ tiles with letter 'A', $n_B$ with 'B', and so on, and $n_*$ 'wildcard' tiles (we have $n = n_A + n_B + \ldots + n_Z + n_*...
18
votes
2answers
68k views

Simplify sum of combinations with same n, all possible values of k

Is there a way to simplify this equation? $$\dbinom{8}{1} + \dbinom{8}{2} + \dbinom{8}{3} + \dbinom{8}{4} + \dbinom{8}{5} + \dbinom{8}{6} + \dbinom{8}{7} + \dbinom{8}{8}$$ Or more generally, $$\...
16
votes
1answer
716 views

Maximum gap between samples drawn without replacement from a discrete uniform distribution

This problem is related to my lab's research in robotic coverage: Randomly draw $n$ numbers from the set $\{1,2,\ldots,m\}$ without replacement, and sort the numbers in ascending order. $1\le n\le m$...
14
votes
8answers
4k views

How many 2-letter words can you get from aabcccddef

(aa would be one of many, bb would not) I thought it would be 10!/8! But apparently I'm doing something wrong. Can anyone help me out because I'm stumped.
14
votes
7answers
3k views

Intuitively understand why the Poisson distribution is the limiting case of the binomial distribution

In "Data Analysis" by D. S. Sivia, there is a derivation of the Poisson distribution, from the binomial distribution. They argue that the Poisson distribution is the limiting case of the binomial ...
14
votes
4answers
1k views

Bias in jury selection?

A friend is representing a client on appeal, after a criminal trial in which it appears that jury selection was racially biased. The jury pool consisted of 30 people, in 4 racial groups. The ...
13
votes
3answers
13k views

How to resample in R without repeating permutations?

In R, if I set.seed(), and then use the sample function to randomize a list, can I guarantee I won't generate the same permutation? ie... ...
12
votes
2answers
3k views

Probability that Secret Santa arrangement will result in perfect pairings

So, we had Secret Santa at work. We're 8 people. We each took turns and pulled a small piece of paper from a bowl with a name on it. The only rule : If you pull your name, you have to put the piece ...
11
votes
4answers
11k views

Probability of finding a particular sequence of base pairs

Thinking about probability always makes me realize how bad I am at counting... Consider a sequence of $n$ base letters $A,\; T, \; C, \text{ and } G$, each equally likely to appear. What is the ...
11
votes
2answers
274 views

The “strongest password”

I have an app which is protected by a four-digit-PIN and the user got five attempts at logging in before the account is locked. Now, one of my customers wants to "strengthen" the security and ...
10
votes
3answers
4k views

What is the probability of n people from a list of m people being in a random selection of x people from a list of y people?

If I am selecting 232 people from a pool of 363 people without replacement what is the probability of 2 of a list of 12 specific people being in that selection? This is a random draw for an ultra ...
10
votes
3answers
1k views

What are the statistical methods I can use to find popular or common combinations of categorical variables?

I am doing a study on polydrug use. I have a data sets of 400 drug addicts, who each stated the drugs that they abuse. There are more than 10 drugs and hence there large possible combinations. I have ...
10
votes
2answers
1k views

Probability of five children in the same class having the same given name

On baby-naming forums, prospective parents repeat some version of their Fear of Jennifer all the time: "I don't want my child to be one of 5 in his class with his name." Thing is, no name comes even ...
10
votes
2answers
555 views

What is the distribution of the cardinality of the intersection of independent random samples without replacement?

$S$ is some set with $n\in\mathbb{N}$ elements, and $a_1,a_2,...,a_m$ are fixed positive integers less than or equal to $n$. With the elements of $S$ being equally likely, $m$ samples $L_1, L_2,...,...
9
votes
1answer
8k views

Simple combination/probability question based on string-length and possible-characters

Assuming "complete randomness" and given a string with a length of 20 characters where each character may be one of 62 possible characters: What are the total number of combinations possible? (...
9
votes
1answer
211 views

Why in latin squares the rows, treatments and columns are said to be orthogonal

I have always heard "orthogonal" in the area of geometry (also please note I am not a native English speaker). I do not understand the following for latin squares (a quote from a text book): ...
9
votes
1answer
275 views

Estimating number of balls by successively selecting a ball and marking it

Lets say I have N balls in a bag. On my first draw, I mark the ball and replace it in the bag. On my second draw, if I pick up a marked ball I return it to the bag. If, however I pick up a non-...
8
votes
3answers
1k views

You randomly select two distinct integers between 1 and 100. What is the probability that the larger number is exactly twice the smaller number?

I recently took a HackerRank test for a Data Science position and got this question wrong. I came to 1/200. Here's how: There are 50 combinations that will make ...
8
votes
2answers
1k views

Probability of letters occurring in order in a string

Suppose we have an alphabet containing $m+1$ symbols, $\{a, b, c, d, e,..., \$\}$, where $p = \Pr(a) = \Pr(b) =\cdots$, and $\Pr(\$) = 1 - (\Pr(a)+\Pr(b)+\cdots)=1-mp$. For a random string of length $...
8
votes
2answers
9k views

How can I obtain some of all possible combinations in R?

Sometimes I want to do an exact test by examining all possible combinations of the data to build an empirical distribution against which I can test my observed differences between means. To find the ...
8
votes
1answer
525 views

Schuette–Nesbitt formula

I was reading the article about the Schuette–Nesbitt formula, which is described as "a generalization of the inclusion–exclusion principle", which has both a combinatorial and probabilistic versions. ...
7
votes
1answer
585 views

Why does the likelihood function of a binomial distribution not include the combinatorics term? [duplicate]

So the likelihood function for a binomial distribution is: Why is the likelihood function above not multiplied by a combinatorics term: n! / (x! * (n - x)!) If the likelihood function is ...
7
votes
2answers
193 views

How many Americans, randomly chosen, are needed to have a 50% chance two live in the same or adjacent states?

Background I'm studying common coincidences and "near" coincidences that nevertheless (unduly) impress the average person. The below question is an extension of the famous Birthday problem, which ...
7
votes
4answers
815 views

Magic Urn Problem

ADDENDUM: First off, thank you all for your insightful answers to this weekend, fun problem, and especially Mark L Stone for his initial comment. I'm probably missing the point in some of the answers, ...
6
votes
2answers
590 views

Sum of binomial coefficients with increasing $n$

Is there any formula for calculating $$\binom{n}{1} + \binom{n+1}{2} + \binom{n+2}{3} + ... + \binom{n+m}{m+1}$$ I have tried iterative method but is there any constant time method exist.
6
votes
3answers
697 views

How many ways to make a straight flush in 7 card poker? (53 card deck with joker)

I can't seem to figure this one out. There are 53 cards in this deck, 1 joker that can assume any rank, choose from 7 cards. This is what I got: $$\binom{9}{1}\binom{4}{1}\binom{5}{4}\binom{46}{2}...
6
votes
1answer
869 views

Random permutation of a vector with a fixed expected sample correlation to the original?

Suppose you have an $n$-vector $X$. For a fixed real number, $r$ between $-1$ and $1$, can one generate a random permutation of the integers $1,2,\ldots,n$, call it $i_1,i_2,\ldots,i_n$ such that the ...
6
votes
1answer
690 views

Probability mass function of the sample mean

Suppose that $X_1,X_2,\ldots,X_n$ is a random sample from a distribution with probability function: $$p_X(x)=\begin{cases} 1/2 &x=-1,1 \\ 0 & \text{otherwise} \end{cases}$$ Now if we define ...
6
votes
2answers
3k views

Can the union (or) probability of many non-mutually exclusive events be calculated recursively?

I need to use the principle of inclusion/exclusion to calculate the "OR" probability of a large number of events $$ P( A_1 \cup A_2 \cup \dots \cup A_n ) $$ For two events the formula to use is (...
6
votes
2answers
733 views

Probability of independent events within a specified window

So I have an event that can occur on a daily basis with probabilty 1%. There is no dependence between days. Now I can calculate the probabality of the event occuring X times in Y days: ...
6
votes
1answer
146 views

Probability of getting $k$ answers correct in an exam with 4 and 2 questions on $N$ possible subjects?

The problem I'm stuck on a "recreational" problem. This is not homework. A student has to take an exam on $N$ possible subjects. The exam is split into two sections, $A$ and $B$. Section $A$ has 4 ...
5
votes
2answers
118 views

Distribution like hypergeometric distribution, but with false replacements

I'm trying to find probabilities for a scenario that works exactly like hypergeometric distribution, except that every time you make a draw, you replace it with a "failure"-object. So eventually you'd ...
5
votes
2answers
857 views

How to efficiently choose $n$ subset out of a set of $m$ many numbers, in a randomized uniform manner?

Problems: It is fairly simple: we have a list of numbers $x_1, x_2, \ldots,x_n,\ldots, x_m$. Our goal is to randomly and uniformly choose a subset of $n$ many numbers out of these. This means that, ...
5
votes
1answer
801 views

How many ways there are to add up 7 numbers to sum of 180?

Farmer has 7 pigs and 180 potatoes. How many combinations of distributing those 180 potatoes there are? Order does not matter. Each pig can get from zero to 180 potatoes, but all 7 pigs must get ...
5
votes
1answer
1k views

How is the exact permutation test procedure carried out: iterating over permutations or using combinations of one group?

I've tried to find an article that explains the procedure of permutation tests for the exhaustive sampling of all permutations (not the monte carlo method) and couldn't find a resource that was ...
5
votes
3answers
2k views

What is the chance that someone is dealt a suit in the game of Bridge?

In a game of Bridge, what is the probability that some player has a complete suit? (There are four players in a Bridge card game. A deck of Bridge cards consists of 52 cards arranged in four suits ...
5
votes
2answers
227 views

Finding optimal correspondences between objects given two square distance matrices

I would like to find the optimal correspondences between two systems of objects based on the distances between objects WITHIN the two systems. So, the input to the algorithm would be two square ...
5
votes
2answers
2k views

Expected number of collisions for balls and bins problem

$n$ number of balls are thrown randomly to $m$ number of bins, standing in a row. The balls are labeled as $1,2,3,....n$ and bins are also labeled as $1,2,3,...,m$. The probability of $i_{th}$ ball ...
5
votes
2answers
147 views

What is the probability of having a pair of doubles when throwing dice?

What is the probability of having a double (two dice will show the same number) when we throw 5 dice (all dice have 6 sides)? My calculations are: ...
5
votes
1answer
85 views

number of different events in a random sequence

I'm confronted with a probability problem that may have already been solved. I'm considering random sequences of m events. The number of possible events is n, and each type of event has the same ...
5
votes
1answer
121 views

Inclusion/exclusion with identical sets that become distinct

This question is motivated by Blitzstein & Hwang Problem 1.49, but differs (I believe) in some crucial ways and so does not have the same answer. It is not (presently) an active problem on any ...
5
votes
2answers
66 views

Combinations or Counting general formula

Assume you have 5 numbered bins and you have 2 red balls, 2 blue balls and 2 green balls (You can assume that there are equal number of red, blue and green balls). I am trying to derive a general ...
5
votes
1answer
534 views

Number of combinations with elements from different sets

Unfortunately I could neither find nor develop a closed formula, but I believe there is a simple solution for this problem. Could you please help me? Suppose that there are 4 different sets: Set A, ...
5
votes
1answer
751 views

How to calculate the chance of getting completely unbalanced groups? (with R)

I want to simulate or calculate probabilities of combinations of group membership for different sample sizes (e.g., n= 3, 4, 5, 10, or 100) for two groups (of the same sample size). Each outcome could ...
5
votes
1answer
105 views

Combinatorial explanation for $2n$th moment of standard normal distribution?

The $2n^\text{th}$ moment of the standard normal distribution $X \sim \text{N}(0, 1)$ is given by: $$\mathbb{E}(X^{2n}) = \frac{(2n)!}{2^n n!},$$ which is also the number of ways to divide $2n$ ...
5
votes
3answers
90 views

Confused about order in probability

A committee consists of five Mexicans, two Asians, three African Americans, and two Caucasians. A subcommittee of 4* is chosen at random. What is the probability that all the ethnic groups are ...
5
votes
1answer
1k views

Probability of a given password

A password consists of 4 alphabet letters and 4 numbers. Calculate the following two probabilities: $p_1$: the probability that the letters are all equal and that the numerical part contains one ...
5
votes
0answers
251 views

Combination of letters: some repeated letters

So I was looking for an answer on this assignment we have to program but I cannot find it anywhere. I'm a computer science student, not a statistics students. (And it isn't even for a statistics ...

1
2 3 4 5
9