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

1
vote
1answer
62 views

A Closed Form Lower Bound Approximating $p_{n,m,s} = n![z^n]\left(\sum_{k=0}^s\frac{z^k}{k!}\right)^m$

Here, I found $p_{n,m,s} = n![z^n]\left(\sum_{k=0}^s\frac{z^k}{k!}\right)^m = \sum\limits_{\substack{k_1 + \cdots + k_m=n\\0\leq k_i \leq s}} \frac{n!}{k_1!\cdots k_m!}$ as the number of ways to ...
1
vote
1answer
43 views

Expected number of couples having same number

I have $n_1$ red balls in a box $A$. These balls are numbered from $1, \cdots n_1$. Let make a copy version of box $A$, called box $D$ (It means that the box $D$ will contain $n_1$ red balls from $1, \...
0
votes
2answers
40 views

Expected value of colors picked from basket

I have a basket with 4 balls with different colors. What is the expected value of distinct colors I can see after picking 4 times from bin. I return the ball back after each try. I tried computing ...
1
vote
0answers
31 views

Relation of relative numbers of (restricted) ways to distribute identical / distinct objects into distinct bins

If want to know if the following inequality holds for general values of $s \leq n \ll m$. $$\frac{C_0(n,m,s)}{C_0(n,m)} \leq \frac{p(n,m,s)}{m^n}$$ $C_0(n,m) = \binom{n+m-1}{m-1}$ is the number of ...
1
vote
0answers
18 views

Expected values of Cereal box - Linearity of expectation puzzle [duplicate]

A toy is randomly put in a given Cereal box as a promotional gift. There can be N different types of toys and each one can be of any type N (IID). (a) Find the expected number of cereal box one has to ...
2
votes
2answers
43 views

Picking a uniformly random subset of colored balls: moments of the discrepancy between colors?

Let $N \gg k\geq 1$, and $\gamma \in (0,1/2)$. I have a set of $N$ colored balls (3 colors in total), where $N$ is a multiple of $\gamma N$ are red; $\gamma N$ are blue; $(1-2\gamma)N$ are green. ...
-1
votes
2answers
77 views

Random Room changing in the Hilbert hotel. [closed]

Let's say you have a Hilbert's grand hotel full occupancy. Assign each occupant a new room select randomly without regard to whether the room is assigned to someone. i.e. empty rooms, multiple ...
4
votes
0answers
97 views

Probability of having at least $j$ collisions when tossing $m$ balls into $n$ bins

Suppose that we throw $m$ balls into $n$ bins uniformly and independantly at random. We consider collisions as distinct unordered pairs, e.g., if 3 balls are tossed in one bin, we count 3 collisions. ...
-1
votes
1answer
26 views

Expectation that the last bin is empty (balls and bins questions)

Say we have N balls and K bins. Let's call Y - The number of balls in the last bin. What is E(Y) ? I don't know that way to get E(Y), I think there is a way of finding it without using indicators.
5
votes
0answers
36 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
35 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}.$$ ...
0
votes
1answer
90 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 ...
0
votes
1answer
47 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
132 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 ...
1
vote
0answers
62 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
votes
1answer
47 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 not ...
2
votes
2answers
114 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
102 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
260 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
100 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 way,...
3
votes
1answer
141 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
105 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 \,\,\,\,\,\color{blue}{\bullet}\times5}...
0
votes
2answers
40 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
90 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
0answers
69 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 \text{polylog}(n)$...
1
vote
1answer
140 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 ...
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
28 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
113 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 to ...
0
votes
0answers
54 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
63 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
104 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
115 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
411 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
85 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, ...
0
votes
1answer
77 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
0answers
64 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 ...
1
vote
0answers
59 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
71 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
0answers
66 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
73 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 ...
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 ...
1
vote
1answer
69 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$ ...
10
votes
4answers
239 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
259 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 ...
3
votes
3answers
220 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 ...
0
votes
1answer
208 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 ...
-2
votes
1answer
187 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
93 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 ...