Stack Exchange Network

Stack Exchange network consists of 174 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.

4
votes
1answer
70 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
125 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
141 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
18 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
34 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
88 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
566 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
26 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
17 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
107 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
28 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
32 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
45 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
89 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
103 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 ...
0
votes
0answers
28 views

Weighted Urn Problem With Replacement Ending on Repeated Ball

Consider an urn with n different colored balls each with differing odds of being drawn. Balls are drawn with replacement. One draws from the urn and holds them in his hand until two of the same ...
1
vote
2answers
98 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
21 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
57 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
45 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
34 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
23 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
20 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
64 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
39 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
547 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) \...
3
votes
1answer
68 views

guessing a 4-digit access code

The company I work for shares a building with another company, so when we need to access that building, we use a 4-digit access code (which never changed in several years) for the main door, and then ...
1
vote
0answers
81 views

Optimal strategy for a combinatoric dice game

The game can be played at https://xcvd.github.io/dice-game/ The player gets 12 throws of 3 dice and chooses a grid to place these throws in (there are 6*6*6=216 possible throws). Each throw ...
0
votes
1answer
90 views

Find the probability that in a group of 23 people, exactly 3 people have birthdays on the same day [duplicate]

My approach was as follows, select 3 people from 23 and then assign any one of the 365 days, then assign the remaining 20 people any of the 364 days and divide it by the total possibilities, which ...
2
votes
1answer
83 views

How to calculate probability distribution of rolling n dice? (with a twist!)

I'm trying to work on a project in code that asks this question. I'm currently able to get the right answer by breaking it up, but I'm wondering if there's a mathematical formula I can address this ...
1
vote
0answers
40 views

How many possibilities to divide 12 elements into 4 buckets of 3 elements [closed]

Say we have possibilities: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 and 12 4 buckets that can contain 3 elements How may possibilities are there to divide the 12 elements over the 4 buckets (where each ...
3
votes
0answers
75 views

How many subsets have n values greater/lesser than values in remaining subset?

For example, given set of ten numbers: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Split into two equal-sized subsets. Multichoose calculates 252 configurations of subsets with 5 values (pick 5 from 10). Only ...
0
votes
1answer
19 views

Number of combinations for creating subsets including all items

Say I have n items. How can I find the amount of combinations possible of subset sets covering all items, when order does not matter. This is maybe badly worded, so allow me to give an example: ...
1
vote
1answer
41 views

How many vectors $(x_{1},x_{2},\cdots,x_{n})$ are there for which each $x_{i}$ is a positive integer?

How many vectors $(x_{1},x_{2}, \cdots ,x_{n})$ are there for which each $x_{i}$ is a positive integer such that $1 ≤ x_{i} ≤ k$ and $x_{1} < x_{2} < \cdots < x_{n}$? Assume that $k \ge n$. ...
0
votes
1answer
66 views

What is the statistical model to find probabilities of drawing certain cards in my card game?

There are four card types. Red, Blue, Green, and Black. From a deck of 20 cards (6 red, 6 blue, 6 green, and 2 black) you randomly draw 6 cards without replacement. I am trying to program a calculator ...
1
vote
1answer
41 views

Can all or most combinatoric optimization problems in Machine Learning be solved using Viterbi algorithm? [closed]

I am just scratching the surface of the topic but are there practical limitations even for Viterbi Algorithm? Also, are Viterbi Algorithm and dynamic programming equivalent?
0
votes
0answers
40 views

Coupon collectors variant: Probability of selecting exactly k unique marbles from a bag of n marbles given that you grab a random amount each time?

General case I have a bag of n marbles. I select a handful of marbles out of the bag x number of times. Each marble is equally probable to draw. Each time I select a handful, I mark them with a black ...
0
votes
1answer
70 views

How to optimize choosing a subset of members under aggregate constraints?

I'm looking for any algorithms or frameworks concerned with optimal selection of a subset of members of a set, subject to aggregate constraints placed on the heterogeneous features of the subset. I'm ...
3
votes
1answer
95 views

How to calculate the probability of picking a certain number of distinct marbles out of a bag, given a certain number of selections?

Imagine I have a bag of n labeled marbles. I would like to pick a single random marble out of the bag x number of times. Every time I pick a marble, I place it back in the bag. How do I calculate ...
2
votes
1answer
114 views

Expectation and Variance of Card Pairs

A 26 card deck containing 13 "hearts" and 13 "spades" is well-shuffled. Thirteen pairs are then dealt from the deck. A pair is a "match" if it contains 1 heart and 1 spade. Let N be the number of ...
0
votes
0answers
97 views

Finding Points of Inflection for a Specific Choose Function

If anyone could solve this puzzle, I would be incredibly thankful! Given a bell-shaped distribution of ways to choose r from constant number n, how do we find the two points of inflection? For ...