It's about distribution or arrangement of $m$ distinct or identical balls into $n$ distinct or identical bins with all possible combinations.

learn more… | top users | synonyms

4
votes
0answers
27 views

More elegant derivation of the shift in median bin occupancy

In answering Median of a multinomial variable, I found to my own surprise through a somewhat tedious calculation that the expected value of the median of the ball counts in $3$ bins into which $n$ ...
2
votes
0answers
32 views

$\mathbb{P}[X_1(k^\ast)] \leq \left( \frac{e}{k^\ast} \right)^{k^\ast} \frac{1}{1-e/k^\ast} \leq n^{-2}$ inequality is used to prove the theorem

In the book Randomized Algorithms from Motwani and Raghavan, it is stated in page 44 that $$\mathbb{P}[X_1(k^\ast)] \leq \left( \frac{e}{k^\ast} \right)^{k^\ast} \frac{1}{1-e/k^\ast} \leq n^{-2}.$$ ...
2
votes
1answer
108 views

Balls and bins question with nlogn balls and n bins.

The question: Suppose we randomly drop nlogn balls into n bins. Give an upper bound on the expectation of the maximum number of balls in any bin. How would this be done? I believe the answer is well ...
0
votes
1answer
66 views

Balls into bins

I have $n$ bins such that each bin may contain at most $2$ balls. we start inserting $k$ balls into the bins, by choosing randomly for each ball the bin to which it will be inserted. what is the ...
3
votes
3answers
198 views

Use the inclusion-exclusion principle to determine

Use the inclusion-exclusion principle to determine : (a) the number of ways there are to choose nineteen balls (identical apart from their colour) from a pile of red, blue, yellow and green balls if ...
1
vote
1answer
68 views

coefficient on $s^{14}$ in generating function

I have $(s+s^2+s^3+s^4+s^5+s^6)^7$, and I'm trying to find the coefficient on $s^{14}$. I've tried using the multinomial theorem, but that leads to the problem of finding all $k_1, k_2, \ldots , k_6$ ...
-1
votes
1answer
44 views

10 ( different ) people have the option of traveling to 20 ( different > ) destination with restrictions. [closed]

10 ( different ) people have the option of traveling to 20 ( different ) destination . On how many ways they can leave if we know that one can visit more destination ( the order of visits is ...
0
votes
1answer
81 views

Number of solutions of $x_1+x_2+\dots+x_k=n$ with $x_i\le r$

Let $n,k,r$ be positive integers. The number of all nonnegative solutions of the Diophantine Equation $x_1+x_2+\dots+x_k=n$ is $\binom{n+k-1}{n}$. Is there a general formula for the number of ...
0
votes
1answer
62 views

Combinations, when placing n objects into k boxes, each box has its own size and the order in them doesn't matter?

I have n objects and k boxes, each box has its own size. The arrangement of objects in a box doesn't matter. How many combinations are there, respectively the formula? Say we have 7 objects and 3 ...
1
vote
3answers
658 views

calculate all combination of indistinguishable objects

I am thinking a question of picking $k$ objects out of $n$($n>k$). But among the $n=4m$ objects, only $m$ distinguishable objects. For example, a deck of poker cards, total $n=52$ cards, but we ...
1
vote
1answer
703 views

Formula to get total combination possibilities

There are Num guys The sum of their ages is Tot The Age of every one of them is ...
1
vote
2answers
453 views

Throwing $k$ balls into $n$ bins.

I have the following question: Throwing $k$ balls into $n$ bins. What is the probability that exactly $z$ bins are not empty? I thought about something like: $$\Pr(z)=\frac{n! z^{k-z}}{n^k ...
1
vote
1answer
32 views

Find the number of unique paths, given a fixed set, that produce a given output.

I'm looking to find the probability of selecting a given number M given a set of N numbers in a bounded range (or potentially in several differently bounded ranges, but I'm starting simple). I'm ...
0
votes
1answer
44 views

$n$ users placed in cells randomly and independently and figure out the expected value

Suppose $n$ users placed in $m$ cells randomly and independently. Let $i$ belongs from $1$ to $n$, and each user $i$ wants to get file $f_i$. Now suppose each different users independently has file ...
1
vote
2answers
97 views

Putting m balls to n boxes (may empty)

Suppose m balls randomly and independently put into n boxes. A box can hold more than 1 ball. Then what is the expected number of empty boxes? What is the expected number of balls that in a box with ...
0
votes
2answers
344 views

Ball and bins & Coupon collector problem

If you know a coupon collector problem, you will know what I am talking about. But if you are not familiar with I will try to explain what is the coupon collector problem. I have $n$ bins. I throw ...
1
vote
0answers
56 views

Throwing balls into bins, where some of the bins are closed after one ball

My question is a variant of the balls-in-bins problem (similar to the coupon collector problem), where I'm interested in how many of the $n$ bins will be empty after throwing $k$ balls. As far as I ...
1
vote
3answers
78 views

flipping two coins when compared to a ball and bin situation?

so as i have understood the sample space for the toss of two coins is TT HH TH HT even if the two coins are absolutely the same we can color each one ...
1
vote
2answers
403 views

Probability of red ball i before any black ball

Assume we have $r$ red balls and $b$ black balls in a box and we remove one ball at a time without replacement. Red balls are labeled from $1$ to $r$. We want to calculate the probability a particular ...
2
votes
2answers
418 views

Probability of number of unique numbers in $37$ Roulette Wheel spins.

I was wondering if someone could help me answer the following question: Calculate the probability that in $37 $ consecutive spins of a roulette wheel (using an European Roulette wheel) you will have ...
2
votes
2answers
109 views

Baseball related problem (balls and boxes)

Thanks in advance for any help! So I am trying to figure out if the number of hits an inning of baseball is random, or if hits tend to come in bunches. To do this, I'm just using a fairly small ...
1
vote
0answers
99 views

Number of ways to write a tuple of positive integers as a sum of tuples with certain constraints

There are $N$ boxes into which we put $mn$ balls in $m$ steps, where in each step we insert $n$ balls, each of which goes into a different box. In how many ways can we do this so that box $B_i$, $1 ...
1
vote
2answers
250 views

What is the “standard balls-in-boxes” argument?

I came across a question recently that I did not know how to do. It included a solution, and basically the question boiled down to how many positive integers are there with 10 or less digits such that ...
0
votes
0answers
96 views

Combinatorial object and formula for n distinguishable balls in k distinguishable bins?

Balls and bins have labels; n >= k. Bins must have 1 or more balls, but balls can only be assigned once. For now, I will say all balls need to be assigned. In reading Wikipedia on the twelvefold ...
3
votes
1answer
99 views

Expected value for the number of tries to draw the black ball from the bag

We have a bag with $4$ white balls and $1$ black ball. We are drawing balls without replacement. Find expected value for the number of tries to draw the black ball from the bag. Progress. The ...
1
vote
3answers
95 views

The probability that each child gets at least one chocolate is?

5 different chocolates are to be distributed among 4 children.The probability that each child gets at least one chocolate is ? Total number of ways is $4^5$.Got that.After that what to do?
0
votes
4answers
48 views

Finding the probability function

Jug contains $8$ balls, $3$ are red and $5$ are blue.pulling out balls with no return intill the first blue ball comes out $\underline{\color{red}\bullet\times3 ...
0
votes
2answers
37 views

Intuitively, how many balls are in the bag?

You have a bag that contains all white balls, though you have no idea how many. You reach into the bag and pull out 10 white balls. Then, with the help of a red marker, you mark those 10 white balls ...
2
votes
1answer
73 views

Expected number of different colored balls in the same bin

Let's say I have $K$ bins and big jar of balls containing $X$ balls. The jar actually contains $W$ white balls and $B$ black balls. Now I'll extract one ball from the jar and throw in one of the $K$ ...
1
vote
1answer
133 views

Number of ways to place $n$ balls in $m$ bins such that no two balls are placed in the same or adjacent bins?

Assume $m$ distinct bins that are placed on a circle. Therefore, each bin has two neighbors that are its adjacents bins. What is the number of ways that one can place $n$ indistinguishable balls in ...
1
vote
0answers
64 views

Balls and Bins [Raab 1998 proof]

I cannot work out the proof in one of the steps. The following is copied from the original paper “Balls into Bins” — A Simple and Tight Analysis: The case when $n\log n \ll m \leq n ...
0
votes
1answer
40 views

Balls and Bins- Heavy Loaded Case: A Tight Formula

I have $m=10^6$ balls and $n=13\cdot 10^3$ bins. I need to know how I can calculate maximum load for each bin. I'm aware of [1], but it's to loose (e.g. max_load: $e\cdot m/n$. And in practice using ...
0
votes
0answers
27 views

Selecting point of reference when counting

When arranging people (A, B, C, D, E) in seats (1,2,3,4,5), why isn't it same to count with reference to seats eg. (number of people can sit in seat number 1) * (number of people can sit in seat ...
1
vote
2answers
96 views

a generic ball and urn problem

Generic ball and urn problem: If two balls are randomly placed in three urns, what are the chances the second urn is occupied? In the generic ball and urn problem, since the balls aren't stated ...
0
votes
0answers
48 views

I need a help to understand a paper about Balls and Bins and bins max load

I must declare that I have asked a similar question before but I did not get any answer. I do need a concrete example and formula allowing me to determine maximum number of balls in a bin with ...
0
votes
1answer
62 views

Bayes theorem. Conditional ball draws

You have a white ball in your hand and there is a ball in a black box that has a probability of 50% of being white. You put the white ball you are holding in the box and shake up the box. a. ...
0
votes
2answers
92 views

A tricky conditional probability question involving recursion

I've been trying to answer this question for the past few days, and I'm absolutely stuck. Without further ado, here's the mystery: We are given a pair of boxes. There are n red balls in box number 1, ...
1
vote
0answers
109 views

Balls and Bins- Hash Table: a Concrete Example

My question is related to this: http://cs.stackexchange.com/questions/49027/balanced-allocation-hash-table-overflow-probability/49030#49030 In [1,2], it is said that if we throw $n$ balls into ...
2
votes
1answer
322 views

Probability that none of 3 tennis balls chosen at random have been used before

There are 15 tennis balls in a box, of which 9 have not previously been used. 3 of these balls are randomly chosen, played with and then returned to the box. later, another 3 balls are randomly chosen ...
0
votes
1answer
75 views

Balls into bins, probability that $k$ of the bins has at least 2 balls

$n$ balls are thrown uniformly randomly into $m$ bins, I'd like to calculate the probability that exactly $k$ bins have at least 2 balls. This is of course doable using the multinomial distribution, ...
1
vote
0answers
59 views

Labeled balls and urns. Finding the probability for a specific pairing.

I was reading a text and came across this problem. The wording is a little terse so I'm not clear on why the result is true. Given N balls and N urns, all of which are labeled. The balls are ...
0
votes
0answers
54 views

Balls into bins with repelling balls and bins, probability 1 or more of a specified subset of bins is empty?

I have $N$ sets of differently colored balls, each set a distinct color and each set consisting of 3 balls. There are 9 bins. Balls are tossed and will land into bins uniformly randomly, except if ...
0
votes
1answer
59 views

Drawing balls from one of two boxes based on a coin toss

Two boxes, the first contains 3 red & 2 white balls. The second box contains 4 red & 7 white balls. A fair die is tossed. If the outcome is divisible by 2, a ball is drawn from the first box, ...
0
votes
1answer
654 views

If five numbered balls are taken at random, find probability that the second largest number is 8

An urn contains ten balls numbered $1$ through $10$. Five balls are drawn at random and without replacement. Find probability that the second largest number drawn will be $8$. The root of my ...
0
votes
0answers
62 views

Balls and Bins when #balls < #bins

I did some search on Balls and Bins problem. But I haven't found out any bounds when the number of balls ($m$) is less than the number of bins($n$). I am aware of the cases when $m \geq n$ so will ...
1
vote
1answer
63 views

Small o-notation in probability [Raab 1998 proof]

I need a clarification about the notation used in the main theorem of the proof "Balls into Bins" - A Simple and Tight Analysis The theorem states that: Let $M$ be the random variable that counts ...
10
votes
4answers
226 views

Expected value of size of subset

Given a set $S$ such that $|S|=n$, A random item is chosen randomly from $S$, and being appended to a new set $T$. This process is being repeated $n$ times (with repetition), what is the expected ...
2
votes
3answers
251 views

Number of ways of distributing balls into boxes

I know that the formula for counting the number of ways in which $n$ indistinguishable balls can be distributed into $k$ distinguishable boxes is $$\binom{n + k -1}{n}$$ but I am having a hard time ...
-2
votes
1answer
161 views

Probability of events after a random ball was moved from one box to another

One box contains 3 white and 6 black balls. A second box contains 5 white and 4 black balls. One ball is chosen at random from the 1st box and put into the 2nd box. Then a ball is randomly ...
0
votes
1answer
191 views

Total number of empty boxes

If you randomly put 18 balls into 10 boxes, what is the expected number of empty boxes? I tried the following: Let $X_{i} = {1}$ if i-th box is empty $X_{i} ={0}$ otherwise Then, let $Y$ be No. of ...