Balls and urns with constraints: no runs of adjacent balls, urns contain only 1 ball.

Question

Here's the question: Given some number of identical balls $1 < n\leq \frac{u}{2}$, how many ways can you distribute them into a line of urns $u$ such that no two adjacent urns contain balls, and each urn may contain only 1 ball.

Alternatively: given the same constraints on $n$, what is the probability that the urns will contain a run of at least 2 adjacent balls (the real problem I'm trying to solve).

My attempt thus far:

The way to compute the ways we can order the balls is a combination $u\choose{n}$, since the balls are indistinguishable. The first part of the problem may be an easier (or harder formulation) but I tried to tackle it with the understanding that I could use the following setup:

$$\frac{{u\choose{n}} - part1}{u\choose n}$$

Where part1 is the solution to the first question. So, this reads: the total number of ways to arrange the balls - all the ways the balls are completely separated from each other, divided by all the configurations, to give me the probability I wanted as the solution for part 2.

I think I'm on the right track here for solving part1, but I can't confirm it's correct. I think it's just ${u-n+1}\choose{n}$. My (shaky) justification is that to guarantee there are no runs of adjacent balls, I must position the balls in a limited set of spaces, and this limit seemed right, though I'm unsure how to demonstrate it. I've done some empirical tests which seem to confirm it, and it looks like it works even for edge cases of only 1 ball (returns 0% probability), but I could seriously use a cross-check here.

All in all, my final function is the following:

$$\frac{{u\choose{n}} - {u-n+1\choose{n}} }{u\choose n}$$

And here's some Julia code that I used to "verify" it:

#Recursively checks a list for consecutive 1s, returns a list of all instances.
has_consec(x)= 
length(x) > 1 ? vcat(x[1] == x[2] && x[1]==1, has_consec(x[2:end])) : return []

#filters a list of all the unique permutations of my list 
#(the combinations function is funky in julia for some reason) 
#by making sure there are no consecutive 1s, gets the length of the final list.

emp_test(n,y)=length(
filter(x->!any(has_consec(x)),
unique(
collect(
permutations(
vcat(repeat([1],y),repeat([0],n-y)
))))))
```

Answer 1

Your answer are correct.

Imagine that you have n urns with $1$ ball each kept separately.

Then you have $u-n \geq n$ empty urns, with $u-n+1$ spaces including the two ends where the filled urns can be inserted without being adjacent,

Thus P(no two urns with balls adjacent) $=\dfrac{\binom{u-n+1}{n}}{\binom{u}{n}}$

and P(at least two urns with balls ajacent) $= 1- \dfrac{\binom{u-n+1}{n}}{\binom{u}{n}}$

Answer 2

This is simply a Stars and Bars problem.
First, see this article and then see this article.

Killing two birds with one stone, the probability is $$\frac{N}{\binom{u}{n}}. \tag1 $$

In (1) above, the denominator refers to the number of ways of selecting the $n$ urns, sampling without replacement, where the order that the urns are selected is deemed not relevant.

First, I will enumerate $N$, then I will explain it.

$$N = \binom{u - n + 1}{n}.\tag2 $$

This matches your computation.

A basic result of Stars and Bars theory is that the number of non-negative integer solutions to

• $x_1 + x_2 + \cdots + x_k = n$
• $x_1, \cdots, x_k \in \Bbb{Z_{\geq 0}}$

is $$ \binom{n + k - 1}{k - 1}.\tag3 $$

Consider the linear row of $u$ urns. The $n$ urns that each have $1$ ball break the row into $(n+1)$ regions. There is a bijection between each satisfying way of placing the $n$ balls and the number of solutions, with constraints to the following:

• $\displaystyle x_1 + x_2 + \cdots + x_{n+1} = u - n.$

• $\displaystyle x_2, \cdots, x_n \in \Bbb{Z^+}.$

• $\displaystyle x_1,x_{n+1} \in \Bbb{Z_{\geq 0}}$

The idea is that the variables $x_1, \cdots, x_{n+1}$ represent how many spaces there are between any two urns with a ball in them.

Since there are $u$ urns and $n$ balls, there are $(u - n)$ empty urns, which I am construing as empty spaces.

The requirement that $x_2, \cdots, x_{n}$ are required to be positive integers is equivalent to the requirement that no two of the $(n)$ urns that contain a ball can be right next to each other.

The tolerance of $x_1, x_{n+1} = 0$ is explained by the idea that the urns at the beginning and end of the row are allowed to have a ball in them, without violating the constraint that no two consecutive urns can have a ball in them.

So, you can introduce the change of variables:

$y_i = x_i - 1 ~: i \in \{2,3,\cdots,n\}.$

So, the desired enumeration of $N$ is the number of non-negative integer solutions to

$x_1 + y_2 + y_3 + \cdots + y_n + x_{n+1} = (u - n) - (n-1).$

In accordance with (3) above, the enumeration is

$$\binom{(u - n) - (n-1) + n}{n} = \binom{u - n + 1}{n}. \tag4 $$

(2) and (4) above match.