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

0
votes
1answer
31 views

Birthday paradox derivation: different approach

I usually use randomization in algorithms so I am familiar with basics of probability but nothing much advanced. I have gone through the derivation for Birthday Paradox (Cormen et al) and decided to ...
0
votes
1answer
62 views

Distinguishable balls in two types of indistinguishable boxes

The problem is to count the number of ways to distribute $n$ distinguishable balls in $k$ boxes, where $k-s$ boxes are indistinguishable between each other and the remaining boxes $k - (k-s)$ are ...
4
votes
1answer
80 views

How many ways can you put 8 red, 6 green and 7 blue balls in 4 indistinguishable bins?

Assume all balls with the same color are indistinguishable. The order in which balls are put in a bin does not matter. No bins are allowed to have the same distribution of balls! For example, this ...
0
votes
1answer
41 views

k different numbers, choose n numbers from them where repetition is allowed. [closed]

Suppose I have k different no.s. Each number is available any number of time. Now I want to have n no.s. (so, obviously I can select any no.s from those k for any no. of time). How many ways are there ...
1
vote
0answers
35 views

Expansion for r-associated Stirling numbers of the second kind

I am looking for a paper or guidance for expanding the r-associated Stirling numbers of the second kind $S_r(n,k)$. $S_r(n,k)$ is the number of ways to partition a set of n objects into k subsets, ...
6
votes
2answers
93 views

Are “Balls in Bins” and “Stars and bars” the same?

I want to know that if Balls in Bins and Stars n Bars problems in combinatorics are similar? Can we reduce one into other? How? How can they be mapped to each other?
0
votes
0answers
72 views

Standard problem of Balls and Bins

A general classification of balls and boxes problems in combinatorics in 12 ways. There are 12 categories since 1. Balls may be distinguishable or indistinguishable; 2. Boxes may be distinguishable or ...
1
vote
1answer
71 views

About the distribution of balls in bins

Suppose we have $n$ balls and $n$ bins, and consider the following process: at stage $k$, we throw $\ln{n}$ balls into the bins, independently at random. We stop after $n/\ln{n}$ stages, when all ...
6
votes
1answer
336 views

$m$ balls into $n$ urns

Assume that there are $m$ balls and $n$ urns with $m\gt n$. Each ball is thrown randomly and uniformly into urns. That is, each ball goes into each urn with probability $\dfrac1n$. What is the ...
1
vote
1answer
106 views

Is this probabilistic balls-and-bins problem well-defined and is my solution correct?

Problem definition: There are $n$ bins, labeled with $1, 2, \ldots, n$. Let $X_i$ be a random variable denoting the number of balls contained in the $i$-th bin. The collection of random variables ...
4
votes
1answer
226 views

$n$ balls are thrown randomly into $k$ bins - how many are empty?

A large number of variants of this question were already asked here, including these - one, two, which are close, but none seem to answer my question. Assume that $n$ balls are thrown randomly and ...
1
vote
2answers
194 views

Probability of $10$ random balls filling $7$ bins. Does indistinguishability matter?

I saw this solution to a problem in my textbook: The problem is we have $10$ indistinguishable balls and $7$ distinguishable bins. What is the probability of having at least one ball in each bin? ...
1
vote
2answers
44 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 ...
0
votes
0answers
30 views

Birthday paradox in choosing random identifiers

If I have a network which has $n$ nodes and every node has an identifier. I want to find what is a sufficient value of $l$, which describes length of identifier, such that every node has different ...
7
votes
3answers
3k views

If n balls are thrown into k bins, what is the probability that every bin gets at least one ball?

If $n$ balls are thrown into $k$ bins (uniformly at random and independently), what is the probability that every bin gets at least one ball? i.e. If we write $X$ for the number of empty bins, what ...
0
votes
2answers
98 views
0
votes
0answers
45 views

Urn problem (possibly a coupon collectors problem)

In an urn with 10 different coloured balls (each colour has an equal chance to be selected, let's say m balls of each colour). Can I find the mean number of draws to : Have one colour from 10 ...
1
vote
2answers
111 views

Put B balls in C containers. How many combinations have box(es) with exactly 2 balls?

Assume that we have B balls (all the same) and C numbered containers (distinguishable). We want to calculate how many of the total combinations contain exactly 1 container with 2 balls, exactly 2 ...
0
votes
0answers
83 views

Let us assume that m balls are thrown independently at random into n bins.

Let us assume that $m$ balls are thrown independently at random into $n$ bins. Let $X$ denote the number of bins that contain afterwards exactly one ball. I want calculate $Pr(X=0) $ In literature I ...
1
vote
0answers
89 views

n bins, m balls and m>n: Probability of at least r bin containing exactly k balls.When bins are numeret from 1…n and ball is equale.

I want to calculate this probability .In this question $N$ bins, $m$ balls: Probability of any bin containing *exactly* $k$ balls. calculate this but I can not understand this calculation.To be more ...
1
vote
0answers
53 views

Probability of drawing balls with different colours

In a jar of balls with different colours, can we find a general probability distribution of having n distinct colours with N number of balls grabbed ? Assuming that any colours have an equal chance to ...
2
votes
2answers
123 views

A Question on distribution numbers

This is a question from the book Combinatorics -a problem oriented approach which states: Q.1 Find the no. of distributions of a set of distinct balls into a set of distinct boxes, if no boxes can ...
0
votes
0answers
91 views

balls in bins — waiting time until $k$ bins are occupied

Consider the classic balls in bins problem: we throw balls one by one into $n$ bins independently and uniformly. Define $\tau(k)$ for $1 \le k \le n$ to be the number of balls we have thrown until $k$ ...
0
votes
1answer
984 views

Number of ways to distribute identical balls into identical bins

I have a question which I expected to be quite famous and common, yet I haven't found much... How many ways are there to distribute $k$ identical balls into $n$ identical bins? For example $(k, ...
0
votes
1answer
252 views

r identical objects into n distinct boxes

The question says that there are r identical balls to be placed in n boxes s.t. $r\geq n$ .How many ways are there such that each box contains atleast one object?The solution is $n+r-n-1\choose n-1$. ...
0
votes
1answer
111 views

r distinct objects into n distinct boxes ( ordering of objects in each box matters)

I have a question and solution as well ,but I don't understand it: If r distinct objects are to be distributed into n distinct boxes each box can hold any number of objects and the ordering of objects ...
1
vote
2answers
142 views

Probability of assigning balls into buckets, where each bucket has a certain capacity.

I'll start with a specific example of what I am trying to solve: I have eight balls to be randomly placed into four buckets. Buckets #1-3 have the capacity of 2, 2, 3 respectively, while bucket #4 ...
0
votes
2answers
48 views

Probability that the first $2$ balls are white, given that the sample contains exactly $6$ white balls

An urn contains $30$ white and $15$ black balls. If $10$ balls are drawn without replacement, find the probability that the first $2$ balls are white, given that the sample contains exactly $6$ ...
2
votes
2answers
137 views

If I randomly throw 10,000 balls to 4,000 buckets, what is the probability that at least one bucket contains more than 10 balls?

If I randomly throw 10,000 balls to 4,000 buckets, what is the probability that at least one bucket contains more than 10 balls? I don't know how to even approach this. A rough number is also ...
1
vote
0answers
32 views

Distribution of maximum/minimum proportion in a sampling process

I am facing something that can be explained as a balls & urns problem. Suppose you have $B$ black and $W$ white balls inside an urn. They are randomly chosen, one by one, without replacement, and ...
1
vote
0answers
77 views

Occupancy distribution bounds for $k$ balls in $m$ bins

Suppose we throw $k$ (distinct) balls into $m$ (distinct) bins, and let $B$ count the number of non-empty bins. I am interested in lower bounds on $B$. More precisely, I wish to bound from above the ...
5
votes
1answer
142 views

Probability of drawing a run of a specific color from an urn with two colors of balls

I was sent a puzzle involving an urn with 128 white balls and 288 black. If the balls are drawn without replacement until the urn is exhausted, what is the probability that a sequence of 10 or more ...
3
votes
1answer
51 views

Expected total number of balls in all bins after throwing balls uniformly randomly to bins that have limited capacity

Consider throwing $n$ balls uniformly randomly to $L$ bins. Each bin has capacity $G$, meaning that if a ball is threw to a bin that already has $G$ balls in it, the ball is discarded. Is that ...
2
votes
3answers
491 views

We throwing $m$ balls to $n$ cells…

We throwing $m$ balls to $n$ cells randomly... At each cell can be more then one ball, or (of course) it can still empty. What is the expectation of the empty cells? I'd like to get any help! Thank ...
0
votes
1answer
107 views

Expected number of bins with more than one ball

Suppose that $n$ balls are randomly thrown into $N$ bins. We can compute the expected number of bins that contain at least one ball as $E(X) = N(1 - (1 - 1/N)^n)$. Now, suppose that instead we are ...
33
votes
3answers
6k views

Making 400k random choices from 400k samples seems to always end up with 63% distinct choices, why?

I have a very simple simulation program, the sequence is: Create an array of 400k elements Use a PRNG to pick an index, and mark the element (repeat 400k times) Count number of marked elements. An ...
1
vote
1answer
85 views

Is there a fast, reasonably accurate estimator for multinomial PDF?

I am working on a balls in boxes kind of problem, where the probability of a ball ending up in a certain box varies by box, that is, each box has some probability P of getting any ball, all together ...
0
votes
2answers
109 views

How many positive integer solutions are there to the inequality $x_1+x_2+…+x_r\le n$?

The original problem is there are $r$ identical boxes and $n$ identical balls. Every box is nonempty. Then how many ways of putting balls in boxes? It is equivalent to the problem of finding ...
2
votes
3answers
88 views

Find the probability that the $4$th ball removed from the box is white

A box has $10$ balls, $6$ of which are black and $4$ of which are white. $3$ balls are removed from the box, their color unnoted. Find the probability that a fourth ball removed from the box is ...
1
vote
1answer
69 views

Expectation time for at least 2 balls in each bin

Given $N$ bins and an unlimited number of balls, to be assigned one ball per time unit to a uniformly random bin. What is the expected time to achieve at least 2 balls in every bin? From a previous ...
0
votes
1answer
217 views

$N$ bins, $m$ balls: Probability of any bin containing *exactly* $k$ balls.

This is an extension to question 821984: Given $N$ balls independently distributed randomly among $m$ bins, what is the probability that at least one bin gets exactly $k$ balls? And is this ...
1
vote
1answer
159 views

$n$ balls into $k$ baskets, $n \geq k$, no empty baskets

I have $n$ balls and throw them into $k$ baskets. None of $k$ baskets should be empty. Which means each basket has at least one ball. Balls and baskets are not distinguishable. What is the number ...
2
votes
3answers
143 views

Constrained combinations of balls in jars

Not sure how to solve the following problem. Imagine we have balls of $n$ different colors. There are $m$ balls of each color, so in total we have $nm$ number of balls. The question is how many ...
0
votes
3answers
62 views

Count all events for k distinguishable items in n distinguishable bins

I want to count all the possible cases that I can distribute k distinguishable items in n distinguishable bins, for example for 3 items and 2 bins I have the next n^k the possible cases are: I ...
1
vote
1answer
48 views

What is the probability of picking $4$ balls out from the two bins?

Assume there are $2$ bins (bin $a$ and bin $b$ ), and each bin contains $n$ indistinguishable balls with $n>10$. The probability of picking $k$ ball from each bin is $p_k$, ($k\ge 0$). Then what is ...
1
vote
1answer
104 views

Combinatorics with balls and bins with constraint

I have $90$ identical balls to distribute among $64$ distinguishable bins. Each must get at least 1 ball, after that the distribution over the remaining $26$ does not matter. I know I first have to ...
2
votes
2answers
89 views

probability that given n balls and 60 urns no urn has more than 1 ball

A carnival game is set up so that a ball put into play has an equal chance of landing in any of 60 different slots. The operator of the game allows you to choose any number of balls and put them all ...
1
vote
0answers
76 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 ...
1
vote
2answers
79 views

Inclusion/Exclusion Principle for indistinguishable balls into two different types of boxes

The problem asks me how to distribute n balls into h boxes where each must get at least 1 n and t boxes where each can be left empty What I have, and where I seem to have stalled is how to ...
5
votes
3answers
990 views

Expected max load with $n$ balls in $n$ bins?

If you throw $n$ balls into $n$ bins uniformly and independently at random, let $X$ be the number of balls in the bin with the largest number of balls in it. Is there an elementary way to ...