Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatorics]

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

0
votes
1answer
32 views

Probability of normal random variable yielding highest value among other normal variables

Let's say I have a competition with $N$ participants. Each participant yields a score that is normality distributed with unique means and unique variations. Each participant gets to post one score (we ...
1
vote
0answers
26 views

Probability of having a match in an existing database

Imagine you are an airport authority in CountryLand and you have two passenger types: human passengers and animals. There is no way for you to distinguish between human passengers and animals except ...
3
votes
0answers
57 views

Probability to be present in every subgroup

Assuming you randomly split a set of n elements in $y$ equally sized parts(each has $x$ elements). Now you have a subset of m elements in the set of n elements ($m> (y/2)$). What is the probability ...
0
votes
1answer
25 views

What is the probability that two samples from a source have no overlap?

I picked 29 results from a list of 429 results. I then picked a second group of 27 (with replacement) results from the same list of 429. There was no overlap between the two samples. What is the ...
0
votes
1answer
50 views

How to calculate number of solid color images on the screen of random pixel generator?

Is there a statistical formula/function to calculate number of basic geometric shapes on the displays of random pixel generator? Let's say we have a basic random pixel generator which has 10*10 ...
1
vote
0answers
21 views

Birthday problem extension to unequal probabilities and multiple collisions

Let $p_1, ... ,p_k$ denote the probabilities of drawing bin $1, .. ,k$, where $\sum_{i = 1}^{k} p_i= 1$. My question is if we draw $n$ times, how can I show that the probability of no bin being drawn $...
0
votes
0answers
18 views

How many pairwise combinations is possible?

I have a dataset regarding a natural language problem that am tackling with machine learning. My goal here is the generate training samples for one of the classes. I do this by doing pairwise ...
0
votes
2answers
30 views

Checking my combinatorics

I am modelling a flash memory system where 0.3 requests are writes (and so take 100 cycles to complete) and 0.7 are read-only (and so take 50). The system can handle 4 requests at once (the ...
2
votes
1answer
29 views

Probability of drawing different items from a subset with replacement

I'm trying to generalize a game mechanic, to understand the probability that the game developers are giving us, but this went over my head. The mechanic is: draw 10 items from a bag of 33 items each ...
0
votes
0answers
26 views

finding the 'best' set

I came across this simple looking but puzzling question recently. There is a set of N tuples given [(a1,b1), ..., (aN, bN)], where a are real numbers and b are positive real numbers. We need to choose ...
0
votes
0answers
27 views

Approximating Binary Target Vectors using Machine-Learned Boolean Functions of Logical Statements

I was wondering if there exist any ML algorithms for finding the "best possible" Boolean function whose output will approximate a binary target vector. My data consist of roughly 100k observations (...
4
votes
1answer
100 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 ...
1
vote
0answers
16 views

Probability of recurrence of the same two numbers in two consecutive lottery drawings

Given lottery game 6 out of 49, I would like to know how high the probability of recurrence of the same two numbers (i.e. 6 and 12) in two consecutive lottery drawings is. In this Wikipedia article I ...
2
votes
1answer
76 views

Probability you end up at the origin after taking $2n$ steps?

Starting at the origin on the line we take a step of unit to the left or to the right with probability $\frac12$. We do this repeatedly with independent steps. If we take $2n$ steps, what is the ...
0
votes
1answer
32 views

Combinatorics with colored balls [closed]

Seven blue and four red balls are to be arranged in order. How many ways can this be done if (1) The blue balls are distinguishable (e.g. numbered) as are the red balls. (2) Blue balls are ...
0
votes
1answer
41 views

Random Variables and Probability

So I encountered this problem while I was studying for exam. However, I cannot wrap my head around the solution that the answer key provided. The problem goes like this: Bob watches cars that pass ...
4
votes
1answer
73 views

Have 40 people at 4 tables: how to switch tables so that the minimum number of people possible are sitting with someone at their original table

Just a few simple premises: 40 people, 10 people per table At some point you want every one to switch tables, and have a few people as possible sitting at a table with someone they sat with the ...
2
votes
2answers
127 views

Calculating a MLE for the combinatorial probability distribution: $\sum_k p^k(1-p)^{N-j-k}\binom{N-j}{k} \cdot(1-p)^{i-k}p^{j-i+k}\binom{j}{i-k}$

I have a relatively complicated discrete probability distribution: $$\begin{aligned} P(i;j) &= \sum_k p^k(1-p)^{N-j-k}\binom{N-j}{k}\cdot(1-p)^{i-k}p^{j-i+k}\binom{j}{i-k} \\ &= \frac{p^j}{p^...
1
vote
0answers
142 views

Probability of sum of sequences of integers

Let K be a positive integer.Suppose that the integers 1,2,3,...,3k+1are written down in random order.What is the probability that at no time during this process, the sum of the integers that have been ...
1
vote
1answer
27 views

Joint probability function of discrete variable (combinatorics)

There's a box with three types of objects: A, B, and C There are 6 of A, 8 of B, and 10 of C. At random, we remove four objects from the box I'm trying to find the joint probability $P(x, y)$ where $...
0
votes
1answer
19 views

Finding number of seating arrangements

This is the question I got in Purdue University's Probability course available on YouTube: I don't understand they wrote 24 possible outcomes . Outcomes are just 5: 5 people in 5 seats. ...
0
votes
1answer
22 views

How many ways are there to place 2 types of objects in n (that varies) spots?

First time posting, all help appreciated. I'm trying to figure out the number of ways to arrange items in spots. The complication is that the number of spots changes with the type of items put in them....
2
votes
1answer
35 views

Bridge Hand Probabilities

Each of the 4 players in the game of bridge get dealt 13 cards. One player and his partner can see they hold 8 of the heart cards so they know that the 2 remaining hands they can't see hold the ...
2
votes
0answers
31 views

What is the name of this test for the probability of differences between lists and is it valid?

And are there any better methods? In a 1969 book about investing, the author Burton P. Fabricand describes a method for assessing the effectiveness of a stock picker. Ask the picker to provide a list ...
3
votes
1answer
93 views

Different ways of counting the same combination

What’s wrong with this reasoning: How many different ways to pick a team of 3 from 4 people? ${4 \choose 3}$ Alternative way of counting is to choose a team of 2 from the 4 first (${4 \choose 2}$ ...
0
votes
0answers
44 views

Realisation of at least one event among N events

Two dice are thrown r times. I want to find the probability $p_r$ that each of the six combinations (1,1),...,(6,6)appears at least once. My Answer:-$p_r=6*(1-(\frac{35}{36})^r)-15*(1-(\frac{34}{36})^...
2
votes
3answers
567 views

Coin Tossings probability

I want to find the probability that in ten tossings a coin falls heads at least five times in succession. Is there any formula to compute this probability? Answer provided is $\frac{7}{2^6}$
0
votes
0answers
27 views

Predicting a combination

Question Suppose we have a training set of families. Where each family is defined as such… Family: A list of integers. Each integer is the age of one of the family members. (e.g. with a 45 year ...
0
votes
0answers
18 views

Optimizing a sequence of events on a variable conditional on the event

I'm trying to understand how I would approach a problem aiming to optimize a sequence of events to maximize another variable. For example, say I start selling a t-shirt at multiple stores, where each ...
2
votes
1answer
117 views

Feller shoe-matching problem

This problem have been taken from the book' An Introduction to Probability Theory and Its Applications' by Williams Feller(1906-1970) Note:- Assume in each case that all possible arrangements have ...
0
votes
1answer
29 views

Randomly choose 50% of n things, but only 1% of specific k things implies what?

Summary: If you randomly choose 50% of n entities total, but it turns out you only chose 1% of k specific pre-chosen entities, does that imply n is likely to be much larger than k? I'm trying to use ...
1
vote
1answer
44 views

Probability of single entry originating from same individual

If I have a bag with n balls of k colors (equal number of each color), and I draw x balls (with replacement), what is the chance of getting two of the same color? I tried to simplify but not sure if ...
2
votes
1answer
36 views

Difference between permutations and combinations

Ok, I know this question has been asked a thousand times. I do understand that permutations mean that order matters where combinations not. I know there's more to it, like what we are counting and the ...
1
vote
0answers
46 views

Probability that 3 out of 4 sets have non-empty intersection

I have $4$ randomly sampled subsets from population set $S = \{1,2,...,100\}$. Each subset has size $24$. What is the probability that at least one element is common among $3$ out of $4$ subsets?
5
votes
2answers
55 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 ...
0
votes
1answer
106 views

Does an approximation exist between the Cumulative Binomial Distribution and the probability of combinations?

Suppose that we have two disjoint subsets $A$ and $B$ of $Z$. Both $A$ and $B$ have a large number of elements each. We want to compute the probability of picking $k$ elements from $A$ e $B$, with ...
1
vote
1answer
108 views

Why do we use ${n\choose k}$ for a binomial distribution instead of ${n+k-1\choose k}$?

I am trying to get my head around this. In my understanding a binomial distribution uses replacement and ${n\choose k}$ precisely states that there's no repetition and that's not the case with a coin ...
1
vote
2answers
107 views

Probability of substring inside string of coin-tosses

Let's say we flip a coin $N=100$ times and get "HTHTHTHHHTHHHHTTHTT...HHT". What is the probability that se letter combination "HHHHH" occurs at least once in this string of $100$ letters? If not a ...
1
vote
1answer
30 views

finding expected value when a set is given and a subset of size n is chosen

I found an interesting coding challenge on pramp by a friend but I couldn't do it in time. Anyhow, it says given a set { 3,14,7,22,29,33} and random 3 element subset is generated each time and its ...
2
votes
0answers
68 views

Probability of a contingency table with given marginals

In Fisher's exact test we consider all contingency tables $(n_{ij})_{i,j=0,1}$ consistent with given marginals $(n_{0.},n_{1.},n_{.0},n_{.1})$, where $\sum_i n_{i.}=\sum_j n_{.j}=N$. Each table has ...
0
votes
0answers
10 views

Number of ways to distribute n not necessarily distinct objects into r identical boxes?

I'm wondering about the number of ways of distributing n (not necessarily distinct objects) into r identical boxes. I tried using Stirling and bell numbers to calculate the result which works ...
2
votes
1answer
49 views

Number of combinations when swapping two sets with some elements in both

This question is closely related to this other one: I have two sets and I want to know the number of possibilities I can do with the elements of these two sets. As a possibility I mean changing ...
1
vote
1answer
36 views

Permutation and counting techinques

A bookshelf has 15 books. in how many ways can 4 books be removed such that no two adjacent books are chosen? I started to solve the question by saying that the first book can be slected in 15 ways, ...
0
votes
1answer
26 views

Negative Binomial Coefficients -nCk = (n+k-1)Ck

I am unable to understand that why $\binom{-n}{k} = \binom{n+k-1}{k}.$ Please help me in understanding this.
0
votes
0answers
21 views

Distributing elements over multiple buckets of a varying size

If one has b buckets that each have a size of b_i and one has to place n elements in the buckets. How can I mathematically described the amount of different permutations the elements can be placed in ...
3
votes
1answer
72 views

Coupon Collection Random Sum [closed]

I have a problem which involves the standard coupon collector's problem to find a probability density from the generating convolution. I start by defining the problem and a few basic statistics. Let ...
1
vote
1answer
41 views

Problems involving Conditional Probabilities and/or Combination

In a poker hand consisting of 5 cards, find the probability of holding 3 aces. Solution A: $$\frac{^{4}C_3 \times\ ^{48}C_2}{^{52}C_5}$$ Solution B (Does not work): $$\frac{4}{52}\times\frac{3}{51}...
-1
votes
1answer
23 views

Variance from sampling from a collection of marbles

Suppose I have $N$ marbles, $k$ of which are black. Let $X$ be the number of black marbles obtained from randomly choosing $M$ ($\leq N$) marbles. What is the variance of $X$? Obviously if $M=N$ then ...
1
vote
0answers
33 views

Arrange features in a table that minimizes covariance

I have a dataset of vectors represented by a $n_{rows} \times n_{cols}$ matrix $M$. Each row is a vector and each column is a feature. There are $n_{cols} = n \times n$ features. We use the sample ...
1
vote
1answer
721 views

Python library for combinatorial optimization

I've been recently working with a combinatorial optimization problem defined as follows. Given two sets of items, A and B, select the best combination of these items given a scoring function $f(A,B) \...