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
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
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
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. ...
0
votes
1answer
48 views

Probability of having K cigarettes in one of the 2 packs of cigarettes

We have 2 packs of cigarettes, N cigarettes in each of the pack. We keep taking out a cigarette from those packs randomly, until one of the packs gets empty. How much is probability that the other ...
0
votes
1answer
43 views

Given $d>8$ boxes and $n$ balls. . What is $P(A \cup B \cup C)$?

Given $d>8$ boxes and $n$ balls. Consider event $A$=boxes numbered $1,2,3,4$ receive 0 balls.$B=3,4,5,6$ receive 0 balls, $C=5,6,7,8$ receive zero balls. What is $P(A \cup B \cup C)$? Attempt: ...
3
votes
1answer
166 views

Ways to distribute $25$ distinct balls to $40$ bins with constraints

How many ways there are to distribute $25$ distinct balls to $40$ bins such that: At least one bin will have more than one ball. One and only one bin (not predetermined) will hold exactly 10 ...
-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}.$$ ...
2
votes
1answer
112 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
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 ...
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 ...
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$ ...
-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 ...
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 ...
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
3answers
716 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
709 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
471 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 (n-z)!},$...
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
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 ...
0
votes
2answers
362 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
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
vote
3answers
82 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
407 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
431 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
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
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 ...
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)$...
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 $...