# Given n, what m maximizes the number of expected consecutive integer ranges for all permutations (n, m)?

I was recently running tests to get items to drop randomly in an old-school computer RPG. I wanted to verify that all items in a range, say, 1-80 would drop in a certain dungeon. But I couldn't do things all at once.

After one test run with the 80-item dungeon, here might be example output from my array of item drops:

Items dropping in D: 1-5, 7-12, 15-21, ...., 73-80

In other words, my program doesn't just print out "yes no yes no" but lumps together a range of consecutive numbers that randomly turned up, where a range is defined as any set of $$x \ge 1$$ continuous integers that have been rolled. So 1 alone would count as a range, and so would 40-78.

I noticed that this expanded for a while, then it shrank. But I'm curious what m would give the maximum number of ranges. This necessitates a formula for the expected number of ranges in terms of $$m$$ and $$n$$, and I have to admit I don't know where to start there. Obviously I could run Monte Carlo simulations to give a guess, but I'm interested in the general formula/derivation.

• A side question would be, what would give the longest text output? For instance, if the output was like 01, 02-03, 06-11, 14, (etc.) how would weighting by range size affect n as a function of m? – aschultz Feb 14 at 8:10
• – hilberts_drinking_problem Feb 14 at 8:54

Following the derivation described here, we can obtain an explicit probability of getting $$k$$ intervals when selecting $$m$$ out of $$n$$ available objects by extracting coefficients of the following generating function:

$$\frac{1-w+uw}{(1-z)(1-w)-uwz}$$

Here, $$w$$ counts objects that do appear, $$z$$ counts the objects that don't and $$u$$ counts runs/intervals.

Using Mathematica, we can explicitly compute the expected number of runs for n=numItems and a given m as follows:

numItems = 30;
f[z_, w_, u_] := (1 - w + u*w)/((1 - z) (1 - w) - u*w*z);
countNRuns[m_, r_] :=
SeriesCoefficient[
f[z, w, u], {z, 0, numItems - m}, {w, 0, m}, {u, 0, r}];
expectedRuns[m_] :=
N[Sum[r*countNRuns[m, r], {r, 0, m}]/Binomial[numItems, m]];
DiscretePlot[expectedRuns[m], {m, 0, numItems}]


yielding the following for n=30: Explicit computation for large $$n$$ is costly, but it seems that the maximal number of runs is achieved when the number of selected items if approximately $$n/2 = 40$$.