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.
424
questions
3
votes
2answers
41 views
Probability of at least $2$ balls in random bin when distributing $K$ identical balls to $N$ distinct bins?
If we distribute $k$ identical balls to $n$ distinct bins, what is the probability a randomly selected bin will contain at least 2 balls, assuming all balls have a uniform probability of being placed ...
1
vote
0answers
33 views
Balls and bins - average vs best case scenario
Assume we have $3$ bins: bins $L_1, L_2, L_3$, in each bin, there are $3$ balls. Alice is picking one ball from each bin at random. The balls can be either white or black. Alice does not know how many ...
0
votes
0answers
41 views
Number of ways to put 4 balls ( white and black ) to 3 urns?
The urns are non-distinct. The balls are non-distinct ( there aren't numbers on it, but every ball have one color, so they are a little distinct - there is difference between black and white ball ).
I ...
0
votes
0answers
12 views
A “distributing redundantly” variation of the balls into bins problem.
We throw $n$ balls into $m$ bins, where $n \gg m$. If we repeat the experiment $s$ times, what will be the optimal value of $s$ so that any pair of such balls do not collide in at least one of the $s$ ...
5
votes
1answer
102 views
$n$ balls into $n$ urns until there is no empty urn.
We have $n$ balls and $n$ urns.
Step 1. Throw $n$ balls into $n$ urns randomly.
Check each urn and if there is more than one ball in an urn, choose only one and keep in the urn and remove all the ...
1
vote
0answers
47 views
Two types of $n$ Balls into $k$ Boxes
There are $n$ balls to distribute into $n/k$ boxes (each containing $k$ balls).
$x$ red balls and the rest white balls. ( $x < (n-k)/2$)
What is the probability/bound for having at least one box ...
0
votes
2answers
22 views
Expected value of pulling blue marble from sack on nth pull
I am doing a refresher for a work course and I'm a little stuck the question asks the following
You have a sack with 7 marbles inside 4 Blue and 3 Green
You draw all the marbles (without replacing ...
4
votes
1answer
25 views
Calculate empty labeled boxes in labeled boxes-balls problem
The problem is to count the number of times that K boxes are empty when n labeled balls are distributed into m labeled boxes. So, if we have n balls and m boxes, we have $m^{n}$ possibilities. I would ...
1
vote
1answer
59 views
We put $15$ balls into $5$ boxes. No box can contain more than $4$ balls. Prove that there are at least $3$ boxes, containing $3$ or more balls.
We put $15$ balls into $5$ boxes. No box can contain more than $4$ balls. Prove that there are at least $3$ boxes, containing $3$ or more balls.
I know this problem is crying to be solved by the ...
0
votes
1answer
20 views
Balls in a box, volume off smaller balls an bigger balls, will it change with same weight?
If I have $10$ pounds of stainless steel balls of $2$ inch, then together they have a (pack)volume. Will the (pack)volume change if I switch to $10$ pounds of stainless steel $4 $ inch balls?
(I think ...
0
votes
2answers
51 views
Variant of balls bin problem
I am stuck at the following variant of the balls bin problem.
The task is to count the number of ways of placing $n$ identical balls into $k$ ordered bins under the constraint: the bin number $i$ must ...
1
vote
2answers
39 views
Balls in boxes - proof correction
I have been thinking about the following problem:
How many ways can $50$ different balls be placed into $50$ different sized boxes if exactly $2$ boxes have to remain empty?
My approach was the ...
0
votes
1answer
60 views
Calculating probability of getting at least 3 red ball drawn from a bag having 6 red ball,5 blue,4 green in 5th attempt. [closed]
There are 6 red balls,5 blue balls,and 4 green balls in a bag. What is the probability of drawing at least 3 red ball in 5th attempt. Assume balls are drawn with replacement
I tried to use binomial ...
0
votes
1answer
38 views
How to find this probability with bags of balls?
I have two bags with different color of balls in it. In bag 1 there are 1 white ball and 3 black balls and in bag 2 there are 1 white ball and 2 black balls. I wanna know what is the probability for ...
0
votes
1answer
68 views
Every ball in different urn
We've got $n$ urns, I have to show that for some $c>0$ there are $c \sqrt{n}$ balls, that after putting them inside urns, probability that all the urns have at most 1 ball is equal or lower than $\...
1
vote
0answers
34 views
Counting methods
I would like to ask, if my intuitive understanding of how to count is correct. Please elaborate or correct me, if the below interpretation is not sound.
Should constructing a $r$-sample (unordered set)...
0
votes
1answer
50 views
Generating function for distributing $k$ indistinguishable elements into $n$ distinguishable bins such that each bin has even number of elements.
Generating function for distributing $k$ indistinguishable elements into $n$ distinguishable bins such that each bin has even number of elements.
So for the bins to have exactly even number of ...
0
votes
0answers
19 views
How many ways are there to arrange n balls into m numbered bins, if each ball is placed in a separate bin and balls are indistinguishable?
How many ways are there to arrange n balls into m numbered bins given that:
each ball is placed in a separate bin
balls are indistinguishable?
3
votes
2answers
37 views
Colored balls probability - color of remaining balls [closed]
A bowl contains 5 white and 8 black balls. We proceed to pick out balls one by one (without putting any back in the bowl) until only same-color balls remain in. What should I think to calculate the ...
2
votes
0answers
350 views
Finding “redundant” or “covered” vectors in a randomly sampled collection.
Fix integers $k,m,t > 0$. Say that I sample $w_1, \ldots, w_t$ uniformly and independently from $\{1,2,\ldots,m\}^k$. For each $i \in \{1,2,\ldots,t\}$, let $S_i = \{w_1,\ldots,w_t\}\setminus\{w_i\...
1
vote
1answer
68 views
In how many ways can I distribute $100$ identical balls into $6$ different boxes?
In how many ways can I distribute $100$ identical balls into $6$ different boxes so that no box is left empty and every box contains even number of elements?
Firstly, I placed $2$ balls in every box, ...
2
votes
1answer
71 views
Balls into bins question. Where is the mistake?
I am not able to figure out a loophole in my argument related to popular "Balls into bins" problem.
Suppose there are $m$ balls and $n$ bins. The $m$ balls are thrown independently and ...
0
votes
1answer
43 views
Probability of balls entering boxes
I had some troubles with the following exercise:
Randomly throw 5 balls into one of the 4 boxes. What is the probability that no boxes are empty?
I think the answer is P(A) = 4 * (5!/1!*1!*1!*2!) * (1/...
0
votes
3answers
98 views
Number of ways to distribute balls in three out of five boxes
Given 10 distinguishable balls and 5 distinguishable boxes (such that the boxes can be numbered 1 through 5):
How many ways are there to distribute the balls so that all the balls are strictly in the ...
1
vote
0answers
30 views
Help in counting the number of distributions, the random assignment of $r=7$ balls to $n=7$ cells
I am a beginner in Probability Theory. Upon reading and solving few problems from the first five chapters from Feller's - Introduction to Probability theory and applications book, I know that, every ...
2
votes
1answer
50 views
$8$ distinct balls are randomly distributed among $4$ boxes. What is the probability that each box has exactly two balls?
I made up an question in my head as to probability but i am not sure about the solution.
Question: There are $8$ distict balls and $4$ distinct boxes.An individual distributes the balls into boxes ...
0
votes
1answer
42 views
Isomorphism Between Counting Functions and Drawing Balls
I have a question regarding associations between different formulations of counting problems. My fundamental conception of such problems is as quantities of functions counted via the twelvefold way, ...
0
votes
1answer
24 views
Given fixed number of bins with equal capacity and variable number of items how many bins will I need?
I'm slightly embarrassed to ask this question as I feel that the answer might be exceedingly simple but I sat down to think about it and can't seem come up with a formula.
I have a fixed number of ...
0
votes
0answers
31 views
Lower bound for maximum load in $m$ balls into $n$ bins problem ($m \neq n$)
The lower bound for maximum load when randomly placing $n$ balls into $n$ bins is
known to be $\frac{ln(n)}{ln(ln(n))}$ and this lower bound fails to hold only with probability $\leq \frac{1}{n}$ for $...
1
vote
2answers
52 views
A box has 100 different balls. No of Balls that can be selected = 1 to 100. How many ways can we select?
A box have 100 balls. Each one is different. One boy can take atleast 1, atmost 100 balls. How many WAYS can he take balls ?
( clarification: Taking ball 1 then ball 2 = Taking ball 2 then ball 1 )
3
votes
1answer
127 views
Distribution of the maximum number of collisions
Given $n$ bins and $m$ balls, throw each ball into a bin that is chosen uniformly at random. Each throw is independent.
What is the distribution of the maximum number of collisions (i.e. maximum ...
2
votes
0answers
32 views
How many balls spill in expectation? (balls and bins)
Consider throwing $n$ balls uniformly into $k$ bins, each of capacity $c$.
Denoting by $X_i$ the number of balls thrown to bin $i$, I'm interested in understanding the quantity
$$S_{n,k,c}=\sum_{i=1}^...
1
vote
0answers
38 views
Balls and bins: Probability of picking the same color given different numbers of selected balls
A bin has $n$ balls. $b$ balls are black and $w$ balls are white. I pick randomly $k$ balls, where $k$ can be $1$, $2$ or $3$ with equal probability. What is the probability that all selected balls ...
4
votes
1answer
95 views
Distribution of highest numbered occupied box and number of balls therein?
Say we have $N$ boxes, numbered $1,2,...,N$.
We select $K$ numbers uniformly from $1,2,...,N$, and for each result we place one ball into the correspondingly numbered box.
We then select $L$ numbers ...
3
votes
1answer
72 views
expected number of balls needed to throw until one of the bins becomes full
Consider the problem of throwing balls uniformly at random into $q$ bins, each has capacity $q$. What is the expected number of balls we need to throw until one of the bins becomes full?
Clearly the ...
2
votes
1answer
58 views
What is wrong with my approach for CLRS 5.4-6 : Given n balls and n bins,find expected number of empty bins?
I am trying to find expected number of empty bins after n balls are tossed into n bins. And each toss is independent and equally likely to end up in any bin. Below is my approach.
My indicator ...
0
votes
0answers
56 views
Finding expected indegree of a node and expected number of nodes with indegree=0
With a single node $v_1$, at every step $t$ with $1 < t ā¤ n$, a single node $v_t$
is
added to the graph, together with a single outgoing edge; the destination of the edge is a
node chosen uniformly ...
0
votes
1answer
76 views
Show that when $n$ balls are thrown into $n^3$ cells, the chance that (at least) two balls will collide goes to zero as $n\to \infty$ [closed]
Show that when $n$ balls are thrown into $n^3$ cells, the chance that (at least) two balls will collide goes to zero, as a function of $n$:
$$\lim_{n\to \infty }P(\exists\, x,y:x,y\text{ collide})=0$...
0
votes
1answer
54 views
Why probabilies are not adding up to one? [closed]
I want to find the probability of certain cases of picking 4 cards from 12 cards. Let's say the type of cards are A, B, and C, and there are 4 duplications of each type. The set of cards S={4.A,4.B,4....
0
votes
0answers
28 views
N Balls in two urns
Let A and B tow urns containing both N balls numbered from $1$ to $N$.
1) We assume to extract casually one ball from A and one ball from B. What is the probability that they have the same number?
$...
1
vote
0answers
34 views
maximum load of balls and bins when $m \neq n$
When $m=n$, there is a classical result such that the maximum load would be $\theta(\frac{\ln n}{\ln \ln n})$. However, what happens when $m \neq n$? Say if $m = n^{0.5}$ or $m=n^{0.9}$, how can we ...
0
votes
3answers
45 views
Distributing balls into distinct boxes
So basically my question is this:
I have $30$ non distinct balls that I want to put inside $4$ distinct boxes. For every $1\le i\le 4$, the $"i"$ indexed box must at least have $i$ balls and at max $...
1
vote
1answer
74 views
Combinatorics - how many ways to divide balls in two groups
Suppose I have:
8 black balls
3 white balls
5 blue balls
how many ways there are to divide those balls into two different groups (note that there is no need to divide into two groups with even ...
1
vote
0answers
23 views
Placing balls of different colours into bins
I'm trying to prove the following statement:
Suppose that you have 25 balls to place into five different bins. 11 of the balls are red, while the other 14 are blue. Prove that no matter how the ...
2
votes
1answer
85 views
N*n*m distinguishable balls with m different colors
I recently asked the following question which is resolved:
n*m distinguishable balls with m different colors, the probability of randomly choosing k balls containing all balls from at least 2 ...
3
votes
2answers
121 views
n*m distinguishable balls with m different colors, the probability of randomly choosing k balls containing all balls from at least 2 different colors
Assume we have m groups of n balls and the balls in the same group have the same color. So there are m*n balls in total. Now, suppose we randomly choose k>(2*n) balls from the set of m*n balls. How ...
0
votes
0answers
25 views
Drawing balls out of two boxes [duplicate]
Suppose that on each turn it is equally likely to draw a ball out of box $A$ or box $B$. Each box contains $N$ balls. If you choose a box to draw a ball and notice that the box is empty then the round ...
1
vote
1answer
68 views
Estimate number of balls by picking a random bin
This is a tweak to the standard balls and bins problem where we (usually) come up with bounds on the max load or empty bins. I am interested in estimating $M$ when $M$ balls are (uniformly) thrown ...
1
vote
0answers
30 views
Balls in two sets of distinguishable boxes
I'm dealing with a physics problem right now that essentially boils down to a ball and box problem. I know that the distribution of N indistinguishable balls into k distinguishable boxes is given by ...
-1
votes
2answers
109 views
Balls in bins with limited capacity
There are $6$ bins and $15$ identical balls. The first $5$ bins can only contain $3$ balls whereas the last bin can contain $1$ ball. When a bin is full, no balls can be thrown into that bin(if a ball ...
