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 [balls-in-bins]

For problems on the distribution of $m$ distinct or identical balls into $n$ distinct or identical bins, optionally with restrictions.

0
votes
0answers
33 views

Combinatorics: arranging $n$ balls in $k$ cell with condition

Im learning combinatorics, and I came across a question I couldn't find the answer to: I have $n$ identical balls and $k$ different cells, I want to find the number of ways to arrange the balls with ...
0
votes
1answer
22 views

Probability that the nth urn is empty

A total of $n$ balls are thrown to $m$ urns, each urn has the same probability of catching a ball. What is the probability that the $n$th urn is empty? What i've tried: i figured the probability of ...
0
votes
0answers
23 views

Probability of “no bin containing more than some number of balls” when randomly toss nlgn balls into n bins?

I am asked: Randomly tossing $nlg(n)$ balls into $n$ bins, find $C$ such that $\text{Pr}(\text{No bins containing more than } Clg(n) \text{ balls}) \ge 1-\frac{1}{n}$. I'm thinking that using ...
0
votes
0answers
41 views

Calculating expected value for X given a scenario

This question was given to me as a review for an upcoming exam: $12$ baseballs are dropped into $5$ empty bins. Let $X$ be the number of empty bins after dropping the balls. Calculate $\langle X \...
1
vote
1answer
47 views

How to solve this probability/combinatorics question about balls in bins

Below is the problem that I need to solve Suppose you blindly place five balls labeled A, B, C, D and E inside five bins labeled A, B, C, D and E. What are the chances that, in your selection, no ...
0
votes
1answer
36 views

Polya's scheme for two urns

I don't know why I can't solve this problem using Polya's method .$$$$ There are two boxes,one of which contains 5 black and 7 white marbles and the other have 2 black and 2 white marbles .randomly ...
2
votes
1answer
55 views

Expected draws to find $z$ of the same colored balls in $y$ urns

There are $y$ urns Each urn contains $x$ distinctly colored balls. The contents of each urn are identical to start out. You can choose an urn to draw from and draw without replacement, adding that ...
0
votes
3answers
71 views

In how many way we can arrange 4 books on 7 different shelves - with no specific demandings?

I was given an unconventional combinatorics question I was struggling with. Suppose we have 4 books and 7 different bookshelves. In how many ways the books can be arranged without loss of generality? ...
0
votes
2answers
35 views

Simple Urn problem doesn't fit with experiment

Given an urn with $n$ numbered balls $[n] = \{1,...,n \}$, one chooses with repetitions $m$ balls. What is the probability that the set of chosen balls $M$ contains a fixed set $S \subset [n]$ of size ...
0
votes
1answer
33 views

expected time for all balls to be put in urn 2 Ehrenfest model

I am trying to calculate the maximal hitting time of the Lazy Random Walk on the $n$-dimensional hypercube(I know it is $2^n$). I'm using the Ehrenfest urn model. Let $X_t$ be the number of balls in ...
0
votes
0answers
21 views

How do I solve this combinatoric/probability question regarding constrained allocation of asset.

I have $N$ bank account and $B$ USD savings. For $i$ in $1, 2, 3, ..., N$, the balance of bank account $i$, denoted as $b_i$, is subject to the constraint of $l_i\leq b_i \leq u_i$. The 1-year ...
4
votes
0answers
47 views

Probability of third ball drawn

Having a box containing 15 red and 7 blue balls. We want to draw 3 balls at random by these conditions on each draw: If the ball is red you set it aside If the ball is blue put it back in What is ...
5
votes
2answers
156 views

How many ways can n identical balls be distributed into k distinct boxes, such that at least one box is empty?

This is a problem in my combinatorics book that uses the principle of inclusion-exclusion. I can follow almost all of what is said, except the book says that if we consider $A_{i}$ to be the set of ...
1
vote
0answers
29 views

Infinite process balls in bins problem

Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the ...
2
votes
1answer
51 views

An urn contains $4$ red balls, $6$ green balls and $8$ blue balls. Probability with versus without putting the balls back

If we had to determine the probability of getting $3$ red balls $2$ green balls and $4$ blue balls after picking a ball, noting its color and putting it back it would be ${9\choose 3,2,4}\cdot({4\...
0
votes
3answers
58 views

placing 15 balls into 6 urns

There are $6$ urns indexed from $1$ to $6$. We place $15$ balls one by one randomly into the urns. What is the probability that the first urn stays empty? I found $\frac{19\choose4}{20\choose5}$ ...
0
votes
1answer
43 views

If 6 balls are randomly placed in 3 bins, what is the probability that each bin will have 2 balls?

I was working on probability problems and came across this. Can someone explain each step in detail how to get to the solution? Thanks so much.
-1
votes
1answer
105 views

which one is worse in terms of probability

There are 2N white balls and N red balls (all balls are same except for the color), to put into K different boxes, such that every box contains 3N/k balls. We say event A happens, if any box has more ...
1
vote
0answers
55 views

Balls and Bins - high probability bounds on the sum of squared loads

Consider throwing $m$ balls into $n$ bins uniformly at random, and let $X_i$ denote the number of balls that fall in bin $i$. Denote by $S=\sum_{i=1}^n X_i^2$ the sum of square loads on the bins. I ...
1
vote
0answers
54 views

Limited combination problem

Problem: Imagine you have N balls, that you want to put into M boxes. How many ways are there to put N balls into M boxes, if every box can store no more than K balls. For convinience, I named the ...
3
votes
1answer
106 views

Birthday problem variation with balls and bins

Balls are thrown randomly and uniformly into $n$ bins up until one bin has 3 balls. Let there be $T=T(n)$ be the number of throws we made until the occasion occurs. I am to assume $n$ is large ...
1
vote
1answer
47 views

Distributing colored balls into bins such that each bin is distinct.

Suppose I have $n = n_1 + n_2 + \dots + n_k$ balls of $k$ colors, with exactly $n_i \geq 1$ balls of color $i$. Balls that are the same color are indistinguishable. Additionally, we have $m$ ...
3
votes
2answers
85 views

Combinatorics - How many ways to partition an integer n into k bins with values 0 - 5 and restrictions

I have been struggling with this brain teaser for some time now. I looked at some combinatorics and partition equations but I can't find the one that captures the solution entirely. Frame I have a ...
0
votes
1answer
22 views

Number of times I will get b balls from the bag

I have 'n' identical balls and 'k' distinct bags. So total number of ways I can put balls with no restriction in bags is ${k+n-1 \choose k-1}$. So I want to know the number of times there were exactly ...
6
votes
5answers
353 views

Arranging $n$ balls in $k$ bins so that $m$ consecutive bins are empty

This question is inspired by the following problem: Randomly place seven balls into ten bins, with no bin containing more than one ball. What is the probability that there will be (at least) two ...
2
votes
0answers
48 views

Coupon Collector's Problem and Balls in Bins Variant

Consider a variant of the traditional coupon collector's problem. There're $n$ kinds of coupons and there's a $1 \times n$ grid. Each grid corresponds to one kind of coupon. Once picking a coupon, we ...
0
votes
0answers
35 views

Occupancy distribution for batched allocations?

I've searched here and in my limited collection of combinatorics books for a solution to this with no luck. Say I have $b$ bins labeled $1$...$b$. A process selects $k$<=$b$ integers from $[1,b]$ ...
5
votes
1answer
78 views

Conditional probability (urns and balls)

From an urn, containing 6 white and 12 black balls, one takes balls randomly one by one until the second white ball appears. What is the probability that: 1) second white ball appears on the second ...
4
votes
2answers
59 views

Number of urns with more than K balls inside

I have a probability problem that I have simplified down to the following: Given M balls that are thrown randomly (uniformly) into N urns, what is the expected number of urns that have more than K ...
0
votes
1answer
105 views

Balls in bins: Prove that the probability that there is some bins of $k+1$ or more balls is at most $\frac n{k^2}$

(Using Chebyshev's inequality and Union bound) Suppose that we throw $n$ balls into n bins uniformly at random. Let $k≥\sqrt n$ be a positive integer Show that with probability at least $1-\frac n{k^...
1
vote
1answer
44 views

Expected Number and Size of Contiguously Filled Bins

I'm pondering on this problem which I made up, so am not sure what the right answer is. Suppose we throw $n$ balls uniformly at random into $N$ bins. Let's call a sequence of contiguous non-empty ...
0
votes
0answers
67 views

Power of 2 choices balls and bins - Expected number of empty bins

I am looking at the standard balls and bins example and more precisely to the expected number of empty bins. Given $n$ balls and $n$ bins, we throw balls into bins sequentially uniformly at random. So ...
0
votes
0answers
24 views

Number of empty bins in multinomial distribution

Suppose I have a discrete probability distribution over $N$ bins $\bigl (p_i > 0; \; \sum_{i=1}^N p_i = 1 \bigr)$, and I have drawn $M$ samples from it. Question 1: What is the expected value of ...
0
votes
1answer
30 views

8-element permutations of a multiset {3:0,1:1,1:3,1:5,1:8,1:9} with the restriction 0 is not allowed in left or rightmost position

I am lost in how to approach this problem due to the wording: Count the number of distinct 8-digit numbers that may be made by permuting the multi-set: $$MS:=\{0:3,1:1,3:1,5:1,8:1,9:1\}$$ ...
1
vote
2answers
161 views

What is the probability that the second blue ball is drawn on the eleventh draw?

An urn contains $10$ white, $9$ black, $8$ red and $3$ blue balls. Balls are drawn one by one at random from the urn until $2$ blue balls are obtained. Find the probability of drawing the second blue ...
0
votes
1answer
42 views

Probability in permutation of balls

There are $n$ balls, of which $r$ balls are red and $(n-r)$ balls are blue. If we select $d$ balls at random (without replacement), what is the probability we select $rd/n$ red balls? In the ...
0
votes
0answers
70 views

To find the maximum load on a N bin problem.

Consider a scenario, where we have $n$ different colored balls ($C_1, C_2 ... C_n$). Each colored ball ($C_{i}$) contains at least one or more instances of it ($1 \leq |C_i| \leq N$). Where $N$ is ...
1
vote
0answers
60 views

Concentration bound around the mean for balls-in-bins

I have been thinking of the following problem. Suppose I throw $n$ balls into $m$ bins, each bin selected uniformly at random. Let $B _i$ $(i=1,2,\dots,m)$ denote the number of balls that land in bin $...
2
votes
2answers
60 views

Can we model the number of increasing words as ball-and-urn problem?

Let the ball-and-urn problem be defined as follows: How many ways can one distribute $k$ [in]distinguishable balls into $n$ [in]distinguishable urns? Let the problem of increasing words be defined ...
0
votes
1answer
76 views

Probability distribution of X(balls and bins)

There are 3 red, 9 green balls in the box. We pick them randomly without returning. When take out red ball for the first time we stop. X-discrete distributed variable, where we have the number of ...
1
vote
1answer
61 views

Probability of 4 balls in one of 80 bins after 26 throws [closed]

This relates to a stock problem: I have a product with 80 sizes, the stock level of each size is 3, I forecast 26 customers per week so what is the probability I will run out of stock of at least one ...
2
votes
1answer
80 views

Distinguishable groups of balls into distinguishable boxes with constraints

We have $E$ balls of $N$ colors. Let's call $e_i$ the number of balls of color $i$ (of course across group balls are distinguishable while within a color they are not). We can split these balls among $...
0
votes
0answers
25 views

Expectation over sets of bins with unequal capacities

Take two sets of bins; Set $A$ contains $M$ bins, each of unequal capacities $a_i$, $i \in \{1,..,M\}$. Set $B$ contains $N$ bins, each of unequal capacities $b_j$, $j \in \{1,..,N\}$. Constrain equal ...
1
vote
1answer
70 views

Distribute red and blue balls into bins. P(No two red balls in a bin)

Let $n, k, m \in \mathbb{N}$ with $k < n$, $m \leq n$ and $n$ mod $m$ = 0. $n$ is a number of balls where $k$ are red, the rest is blue. $m$ is a number of bins. Now the balls will be randomly ...
0
votes
1answer
35 views

Balls and boxes - probability

I consider the following sceneriou. Three balls enter the box, $B_1, B_2, B_3$, the balls are independent and identical. Next, we draw the balls from the box, one after another, waiting an exponential ...
1
vote
1answer
79 views

$2 n$ balls are randomly thrown into $k$ bins. What is the probability that they land in at most $n$ bins?

Consider randomly throwing $2 n$ balls into $k$ bins. I'm looking to upper bound the probability that at most $n$ bins are not empty. How big does $k$ have to be for the probability of the event to ...
1
vote
2answers
127 views

I throw 750 red and 250 blue balls into 10 bins. What is the probability no bin is over 1/3 blue?

We have $1000$ balls, $750$ red and $250$ blue. We distribute them uniformly at random into $10$ bins. What is the probability none of these bins is at least $1/3$ blue? More generally I'd like to ...
0
votes
3answers
46 views

Basic combinatorics: In how many ways can we arrange $4$ different balls in $4$ identical boxes?

I stumbled upon a question I can not manage to answer. In how many ways can we arrange $4$ different balls in $4$ identical boxes? I do know there is no importance to the order they're set up so its ...
2
votes
1answer
23 views

count of 4 digits number with odd digits with sum 16

Let $abcd$ be a 4 digit number and $a,b,c,d$ are all odd digits (1,3,5,7,9). We want to find count of such numbers that $a+b+c+d =16$. In the book in which I found this question, the answers was: $...
1
vote
1answer
207 views

Balls and Bins (Find no of balls)

How many balls do you need to throw randomly into n bins so that the probability that none of the bins is empty is at least 1/100? I am trying to solve this question by first finding the expected no ...