Can thus be calculated mathematically (runs in a balls into boxes scenario)?

Question

Say I have a line of $b$ boxes in a row labeled $1, 2 ,..., b$.

Each box can hold 1 ball only.

I partition the line of boxes into blocks of varying sizes, with the number of singlets, doubles, triples, etc. given.

For example, I might have 10 boxes in a line partitioned as

${ \{1\},\{2\},\{3,4\},\{5,6,7\},\{8,9,10\}}$

Giving 2 singlets, 1 double, and 2 triples.

I now place $n<=b$ indistinguishable balls uniformly randomly into available boxes.

Given $n$ and the partitioning, what is the probability that one or more of the blocks of size >=2 has a run of 2 or more balls (that is, some two adjacent boxes both in the same block both contain a ball)?

I've resorted to simulation to get my results, can this be done combinatorially?

Answer 1

There are $\binom{b}n$ ways to place $n$ balls into the $b$ boxes, ignoring the question of runs.

Suppose that there are $B$ blocks and the length of the $i$th block is $L_i$.

Then the number of ways to place $n$ balls, without any runs in a block, is the coefficient of $x^n$ in: $$\prod_{i=1}^B{\large\sum_{j=0}^{\lceil L_i/2\rceil}}\binom{L_i+1-j}{j}x^j$$

That means that a block of length $1$ is represented by $(1+x)$, a block of length $2$ is represented by $(1+2x)$, a block of length $3$ by $(1+3x+x^2)$, a block of length $4$ by $(1+4x+3x^2)$, etc.

In the given example, the resulting polynomial is $$(1+x)^2(1+2x)(1+3x+x^2)^2\\=1+10x+40x^2+82x^3+92x^4+56x^5+17x^6+2x^7$$

The coefficient of $x^5$ is $56$; thus if $5$ balls are placed, the chance that there are no runs is $$\frac{56}{\binom{10}5}=\frac29$$and the chance of at least one run is $1$ minus that number, or $\frac79$.

Answer 2

(Too long for a comment)

When I'm going over the combinatorics problems on this site they contain up to $4$ or so variables: "In how many ways can you put $m$ balls into $n$ boxes such that no box contains a number of balls which is divisible by $r$?" This means that each instance of such a problem requires forwarding up to $4$ or so integers. A great number of these problems have a satisfying "general solution".

Now your problem is not of this kind. You have the two variables $b$ and $n$ allright. But an individual instance of the problem requires in addition the forwarding of a rather complex structure,namely a general partition of $n$. When, e.g., $n=17$ then there are $297$ partitions, difficult to overview in a systematic way.

What I want to express is the following: It is very unlikely that you will find a general algorithm that takes $b$ and a partition of $n$ as input and produces the number of allocations containing no two consecutive occupied boxes in the same part of the partition.