Intereting Posts

Continued fraction for some integrals by Ramanujan
Find all integer solutions to $7595x + 1023y=124$
Difference between Deformation Retraction and Retraction
Prove the inequality: $\frac{a}{c+a-b}+\frac{b}{a+b-c}+\frac{c}{b+c-a}\ge{3}$
Testing whether an element of a tensor product of modules is zero
Proof of exchange principle in set theory
Are Linear Transformations Always Second Order Tensors?
how the Kronecker product is a tensor product?
Derivative at x=0 of piecewise funtion
Find maximum divisors of a number in range
What is a complex inner product space “really”?
Integer squares of the form $x^4+x^3+x^2+x+1$
Finding the intervals where $f(x)=\frac{1}{|x-2|}-x$ is monotonous
Let $f$ be a function such that every point of discontinuity is a removable discontinuity. Prove that $g(x)= \lim_{y\to x}f(y)$ is continuous.
Best practice book for calculus

I’ve been working on this all day long. Here’s what I’ve done until now.The denominator is easy. It’s $n^{2n}$. I compute the numerator as follows.

All $n$ bins have at least one ball = $n$ bins must have one of the $2n$ balls each + the remaining $n$ balls are placed in any of the bins in any fashion.

Now I solve the first part. $n$ balls can be chosen out of $2n$ balls in $\binom{2n}{n}$ ways, and they can be placed in $n!$ ways in the $n$ bins. Hence multiplying them yields $(n+1)(n+2)\cdots(2n)$.

- Venn diagram for conditional probability property of Independent Events
- Hard Integral $\frac{1}{(1+x^2+y^2+z^2)^2}$
- Distribution of dot product?
- Deriving the mean of the Geometric Distribution
- Probability of at least one king and at least one ace when 5 cards are lifted from a deck?
- Interpretation for the determinant of a stochastic matrix?

I have no clue how to proceed with the second part. Please help. Also please correct if I am wrong in the way I’ve proceeded so far.

- Kelly criterion with more than two outcomes
- How to comprehend $E(X) = \int_0^\infty {P(X > x)dx} $ and $E(X) = \sum\limits_{n = 1}^\infty {P\{ X \ge n\} }$ for positive variable $X$?
- Random Variable Inequality
- Why do knowers of Bayes's Theorem still commit the Base Rate Fallacy?
- Cauchy Schwarz inequality for random vectors
- Does variance do any good to gambling game makers?
- Prove $E=E]$
- Expected number of steps in a random walk with a boundary
- Monty hall problem with leftmost goat selection.
- Probability Of Union/Intersection Of Two Events

The approach that you started on is a good one. The “total” count was right, but the count of the “favourable” cases was not. Let us generalize slightly. We throw $m$ (numbered) balls, one at a time, at a line of $x$ (numbered) buckets, and ask for the probability that none of the buckets ends up empty.

There are $x^m$ outcomes, all *equally likely*. We now need to count the number of outcomes for which none of the buckets is empty. There is unfortunately *no known closed form* for this number.

However, the number of ways of dividing a set of $m$ elements into $x$ non-empty subsets has a *name*. It is the *Stirling number of the second kind*. One common notation is $S(m,x)$. Another looks like a binomial coefficient symbol, with $\{\}$ instead of $()$.

So (by definition) we can divide our set of $m$ objects into $x$ non-empty subsets in $S(m,x)$ ways. For every such division, we can assign these subsets to the buckets, one subset to each bucket, in $x!$ ways. This gives us a total of $x!S(m,x)$ ways, and our probability is therefore

$$\frac{x!S(m,x)}{x^m}.$$

For your particular problem, let $m=2n$ and $x=n$.

There is no known closed form for $S(m,x)$. Perhaps there is a closed form for the special case $S(2n,n)$ that you need. I do not see one immediately, but have not thought enough about it.

There are nice *recurrences* for the Stirling numbers of the second kind. We can also get pleasant expressions for them as *sums*, by using the principle of inclusion/exclusion. To give you a beginning on that, we start counting the number of ways to have no bucket empty.

There are $x^m$ ways to distribute the balls. How many have bucket $i$ empty? Clearly $(x-1)^m$. Which bucket will be empty can be chosen in $\binom{x}{1}$ ways. So as a first step to our count, we arrive at $x^m-\binom{x}{1}(x-1)^m$.

However, we have subtracted too much, since the cases where $i$ is empty and $j$ is empty have been subtracted twice from $x^m$. So for every (unordered) pair $i$, $j$, we must add back the $(x-2)^m$ assignments in which buckets $i$ and $j$ are empty. This gives us the new estimate $x^m-\binom{x}{1}(x-1)^m+\binom{x}{2}(x-2)^m$.

However, we have added back one too many times all the cases where $3$ of the buckets are empty. Continue. We end up with an attractive sum, that has no known closed form, and that is of course a close relative of $S(m,x)$.

**Remark:** Unfortunately, for the probability model in which each ball is equally likely to end up in any bucket, with independence between balls, a “Stars and Bars” approach won’t work. Yes, we can get a count of the number of ways to distribute $m$ identical balls between $x$ buckets. We can also get a count of the number of ways to distribute so that no bucket is empty. But then we run into a **fatal** complication. The different ways to distribute $m$ identical balls among $x$ buckets are **not** equally likely.

Consider stars and bars as a tool for dealing with these sorts of problems.

- Hardy's Inequality for Integrals
- Limit of integral – part 2
- Embedding manifolds of constant curvature in manifolds of other curvatures
- Difference between variables, parameters and constants
- To show that Fermat number $F_{5}$ is divisible by $641$.
- If a lottery has 300 tickets, shouldn't I win every 300 times I play
- An nth-order ODE has n linearly independent solutions
- Unity in Partial Ring of Quotients $Q(R, T)$
- for which values of $p$ integral $\int_{\Omega}\frac{1}{|x|^p}$ exists?
- If n is such that every element $(\mathbb{Z}/n\mathbb{Z})^{*}$ is a root of $x^2-1$. Prove that $n$ divides 24.
- Does the series $ \sum\limits_{n=1}^{\infty} \frac{1}{n^{1 + |\sin(n)|}} $ converge or diverge?
- Problem : Permutation and Combination : In how many ways can we divide 12 students in groups of fours.
- Dimension of $\text{Hom}(U,V)$
- The Degree of Zero Polynomial.
- Tensors = matrices + covariance/contravariance?