Questions tagged [combinatorics]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
44 views

Estimate the number unique elements in a finite sample space via a finite sample without replacement

I have a pool of $N$ items. I know that there are $c$ distinct types of items in $N$ and the distribution of the distinct types is uniform, i.e. if I sample 1 item from the pool its chance of ...
1
vote
2answers
175 views

Algorithms for solving combinatorial complexity problems in machine learning?

Many machine learning problems have combinatorial complexity. For example, in part-of-speech (POS) tagging in NLP, the goal is to predict one of possible $T$ tags for every word in a sentence of ...
2
votes
1answer
195 views

What is the probability for an N-char string to appear in an M-length random string?

Link shortening service bit.ly allows you to, as you might expect, shorten URLs. URLs get shortened using a 7-character string. The alphabet of this string consists of a-z, A-Z and 0-9. Today, Dutch ...
0
votes
0answers
34 views

What is wrong with this self-made array shuffling algorithm? [duplicate]

I'm aware of the established array-shuffling algorithms, such as Knuth-Fisher-Yates. I'm interested in proving (or disproving) that my self-made shuffling algorithm is broken. It seems to be the ...
0
votes
0answers
126 views

Covariance matrix of combinations of independent normal distributions

I have a basket $X$ of items to choose from. Each $x_i$ is a normally distributed random variable $x_i \sim\mathcal{N}(\mu_i, \sigma_i^2)$. Each $x_i$ is independent and uncorrelated from every other ...
1
vote
1answer
63 views

Probability of n columns of an array being identical

I'm trying to calculate the probability that p (or more) columns, of an n x m matrix, each ...
5
votes
2answers
114 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 ...
4
votes
1answer
933 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 ...
1
vote
0answers
231 views

Conditional combinations and permutations to identify sequences and patterns in R

I want to identify repeated behavioural patterns in a trader's account. The trader will typically transfer funds into his account denominated in a particular asset, buy and sell different assets, then ...
0
votes
1answer
47 views

How many possible combinations of this stage given its a n * n grid?

Lets say you have n x n grid, and each square on the grid is either black or white. How many different combinations of this grid can exist? I figured 9! would be for the grid, but I don't know how to ...
0
votes
1answer
78 views

all combinations of a vector of probabilities

I'm sure this is a simple problem, but I haven't been able to get to the bottom of it. I have a vector of probabilities, e.g. (P1, P2, P3). I'm trying to get the probability of each combination, e.g. ...
2
votes
1answer
50 views

Is there a closed form for sum of chooses?

Is there a closed form for $\sum_{i=a}^{b}\frac{{{i} \choose{n}}^2}{i}$?
3
votes
0answers
40 views

Summation of combinations up to $r-1$ terms

I am trying to come up with a simplified expression for $$\sum_{k=r}^{n}\binom{n}{k}$$ Choosing $x=y=1$ in Binomial theorem, I have $$2^n = \sum_{k=0}^{n}\binom{n}{k}$$ $$2^n = \sum_{k=0}^{r-1}\binom{...
0
votes
1answer
42 views

Probability of pipetting X number of cells in a solution

I had a biology friend ask me this question: Suppose I had 50 ml of solution in which exactly five red blood cells that are individually suspended (i.e., not sticking to each other). If I collect 2 ...
1
vote
0answers
125 views

Formula for dropping 2 dice (non-brute force)

This is a follow up from my previous question: Formula for dropping dice (non-brute force) which asked how to determine the statistics for dropping the lowest die but now I'm asking how to determine ...
0
votes
0answers
135 views

Matching columns across matrices

Say I have two or more matrices. The number of rows and columns are same across matrices. But the matrices are not necessarily square. ...
2
votes
0answers
19 views

Multicomparison Test of Independent Events

I can explain more if needed, but simply I have a strand of DNA and I want know some aggregate probability of the observed phenomenon being due to chance. As an example I have something like this: <...
0
votes
1answer
14 views

Given 9 tiles, each can contain {0, 1, 2} how many states?

I know my question is simple, but I'm struggling to find an answer. Given 9 inputs that could be either 0, 1 and 2, I was wondering how can I calculate the number of total different states possible. ...
3
votes
1answer
128 views

Sum of k most extreme values

I have $n$ balls, which I put independently and at random into $\ell$ bins or urns. I then look at the $k$ bins with the most balls inside and count the total number $S$ of balls in these bins. What ...
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.
2
votes
2answers
158 views

Grouping large groups into smaller groups while keeping people together

Let's say we have a grouping of people as such: ...
0
votes
0answers
66 views

Combining predictions with errors

If i were to try to combine two predictions, such as: Test 1: $70\% \pm 10\%$ sure that $x$ is between $1.5$ and $2.5$ Test 2: $65\% \pm 10\%$ sure that $x$ is between $1.5$ and $2.5$ combination ...
4
votes
1answer
92 views

Number of distinct scatterplots among $p$ variables

In Chapter 2 Section 2.1.4 of An Introduction to Statistical Learning (James et al, 2013), the assertion is made that "...if there are p variables in our data set, then p(p-1)/2 distinct scatter plots ...
2
votes
0answers
39 views

What is the probability of an observation with a given level of similarity, across a set of attributes, to any individual in a known population?

I'm attempting to identify individuals sampled from a known set, using observations of the attributes I know for the individuals. I have an algorithm to find the closest match already; what I'm ...
2
votes
1answer
685 views

Calculate all possible combinations and obtain overall distribution

Consider 4 regions, each region got a range of numbers associated - say these are population estimates from different studies (see reproducible example). I'd like to establish all possible ...
7
votes
2answers
192 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 ...
5
votes
3answers
1k 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 ...
3
votes
1answer
111 views

The Defective Lock Problem

It appears the solutions to my problem are the Binomial Coefficients, as seen above Suppose a combination lock with 2 dials exists, where each dial has 2 settings (for example, 0 and 1, but any two ...
2
votes
1answer
126 views

Balancing out in an orthogonal design

A definition of orthogonality in the context of statistics is An experimental design is orthogonal if the effects of any factor balance out (sum to zero) across the effects of the other factors. ...
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): ...
0
votes
2answers
76 views

Basic combinatorics for rule learning

This is supposed to be a rather rudimentary combinatorics problem, however, I can't seem to wrap my head around it. The Problem There are 40 distinct items, one person can pick (up to) 3 items. To ...
1
vote
1answer
57 views

Ball picking with a few twists

Suppose I had a finite number of balls, say a total of $k$, where $k$ is a multiple of $6$. Each ball belongs to one of $n$ different groups, by color. If I know the number of balls that belong to ...
1
vote
0answers
19 views

What is the probability of a given permutation if I have individual probabilities of each item in reference to another?

I have 4 results represented by A, B, C and D I have the probabilities for whether each result will be greater than the other: P(A>B): 86.6% P(A>C): 80.4% P(A>D): 72.6% P(B>C): 57.4% P(B>D): 41....
4
votes
3answers
85 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 ...
3
votes
2answers
79 views

Mini Poker Hole Cards

Playing with 16 cards. 4 A, 4 K, 4 Q, and 4 J; Deal 8 2 card hands. Notice all cards are dealt. Number of 2 card hands $\binom{16}{2} = 120$ Of the 120 there are 6 paired Q and 24 unpaired ...
6
votes
3answers
669 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}...
1
vote
1answer
65 views

How do you measure how “typical” a set of events are?

Given a set of events and their probability of occuring, where they all add to 1. Edit: the set of events can be of any size, the example below is only A and B with 50/50 probabilities for simplicity ...
4
votes
2answers
90 views

Total number of ways 10 books can be arranged if 4 specific books may not be together?

I am trying to solve this albeit probably juvenile combination/permutation type question. A person has 10 books, of which four are fiction books. How many ways can the 10 books be arranged so that ...
4
votes
1answer
88 views

Probability of 0% correct choices [duplicate]

If I have 12 boxes, in order of #1 to #12, and I close my eyes and stick a known label (A to L) on a random box, what is the probability that I get zero correct labels on the corresponding boxes? In ...
2
votes
2answers
68 views

Combination/Permutation Dilemma

This is probably quite a straight forward one - but still struggling to get my head around it. To explain my problem: In my work, I'm trying to put subjects into groups of 4 for a second round of an ...
1
vote
1answer
76 views

What's wrong with probability/combinatorics solution?

I was playing a game of cards with some friends and wondered : What's the probability of drawing 4 cards from a normal 52 card deck with all different ranks? I figured out 3 ways of achieving the ...
2
votes
1answer
581 views

Computing number of people with the same name and date of birth based on sample data

A country has a population of 40 000 000 people. I have a sample with data for 1 500 000 people from this country. In this sample 1.9% of people have a "pair" (one or more) with the same first name, ...
4
votes
1answer
128 views

Unconventional optimization over the space of combinations $C(N,n)$

I have an unconventional optimization problem. At least for me. PROBLEM: $$ \max_{c \in C(N,n)} F(c) $$ where: $C(N,n)$ is the space of the combinations of $n$ objects, out of $N$; $F: C(N,n) \...
0
votes
1answer
18 views

How many neighbor-swaps does it take to undo a random shuffle of N items?

Suppose you have an ordered deck of $N$ items, $e_1, e_2, ... e_N$ and you randomly shuffle them. On average, how many neighbor-swaps does it take to get back to the ordered deck? For example: $N=3$....
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 ...
1
vote
0answers
76 views

Pairwise independence and joint independence of events

I found the following problem in the book The Theory of Probability: Explorations and Applications by Santosh S. Venkatesh. Consider the sample space comprised of all $k!$ permutations of the ...
0
votes
1answer
63 views

Probabilty to have y balls in bin A if N balls where distributed in X bins

I've N=1000 balls and X=20 bins. I distribute them randomly in these 20 bins. Let's say I've y=100 balls in one of the bins (let's say bin y). What is the probability to have y=100 balls in this bin. ...
16
votes
1answer
674 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$...
1
vote
0answers
44 views

Number of combination for a password

If a password can be anything from 00A0000A to 99Z9999Z is it right to say that the number of possibilities is ? ...
3
votes
0answers
82 views

How to maximize the odds of getting a selection correct given a shuffled deck of cards?

Here's the situation: You are playing a game, in which the object of this game is to obtain the highest score possible. You have a list or array of values from 1 to 100 (we will visualize these as a ...

1 2 3
4
5
8