6
$\begingroup$

This question is inspired by the following problem:

Randomly place seven balls into ten bins, with no bin containing more than one ball. What is the probability that there will be (at least) two consecutive bins that are empty?

Note that this is not a circular arrangement, although that could make for an interesting (if simpler) question. The actual question I have is the same as the one above, but with the numbers written in emphasized text generalized as positive integers $n$, $k$, and $m$, respectively.

Question:

Randomly place $n$ balls into $k$ bins, with no bin containing more than one ball. What is the probability that there will be (at least) $m$ consecutive bins that are empty?

I suspect that this is a known counting problem (as framed, or through some equivalent rephrase), so I include a reference-request tag. An original solution would, of course, be welcome as well!

As in an already included answer: Specific cases (e.g., $m=2$) would be helpful, too.

$\endgroup$
  • $\begingroup$ This sounds like a pretty straightforward counting problem if you use inclusion-exclusion. However, it doesn't seem to me that there is a nice general closed form expression. $\endgroup$ – platty Dec 10 '18 at 23:40
  • 1
    $\begingroup$ @platty I would appreciate a "straightforward counting" answer! $\endgroup$ – Benjamin Dickman Dec 10 '18 at 23:40
  • 1
    $\begingroup$ On second thought, it does seem more complicated. The question I was familiar with assumed a bound $m \geq n/2$, from which straightforward PIE suffices. But in the general case, it doesn't seem like a nice closed form should be reasonable -- there are too many cases of differently-sized intersections to handle. $\endgroup$ – platty Dec 10 '18 at 23:58
1
$\begingroup$

We show the probability $p_m(k,n)$ to randomly place $n$ balls into $k$ bins with no bin containing more than one ball, so that at least $m$ consecutive bins are empty is \begin{align*} \color{blue}{p_m(k,n)=\binom{k}{n}^{-1}\sum_{j=1}^{\lfloor k/m\rfloor}\binom{k-mj}{n}\binom{n+1}{j}(-1)^{j+1}}\tag{0} \end{align*}

In order to do so we consider the binary alphabet $V=\{0,1\}$ and decode empty bins with $0$ and bins where a ball is placed with $1$.

  • We are looking for the number $g_m(k,n)$ of binary words of length $k$ which contain $n$ $1$'s and runs of $0$ with length at most $m-1$. The number of wanted words is \begin{align*} f_m(k,n)=\binom{k}{n}-g_m(k,n) \end{align*}
  • Since there is a total of $\binom{k}{n}$ binary words of length $k$ with $n$ $1$'s, the probability $p_m(k,n)$ is \begin{align*} p_m(k,n)=\binom{k}{n}^{-1}f_m(k,n) \end{align*}

Words with no consecutive equal characters at all are called Smirnov or Carlitz words. See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.

A generating function for the number of Smirnov words over a binary alphabet is given by \begin{align*} \left(1-\frac{2z}{1+z}\right)^{-1}\tag{1} \end{align*}

We replace occurrences of $0$ in a Smirnov word by one up to $m-1$ zeros to generate strings having runs of $0$ with length less than $m$. \begin{align*}\ z\longrightarrow z+z^2+\cdots+z^{m-1}=\frac{z\left(1-z^{m-1}\right)}{1-z}\tag{2} \end{align*}

Since there are no restrictions to the length of runs of $1$'s we replace occurrences of $1$'s in a Smirnov word by one or more $1$s. \begin{align*}\ z\longrightarrow z+z^2+\cdots=\frac{z}{1-z}\tag{3} \end{align*}

We substitue (2) and (3) in (1). Since we want to keep track of the number of zeros we put $tz$ instead of $z$ in (2). We obtain

\begin{align*} \left(1- \frac{\frac{tz\left(1-(tz)^{m-1}\right)}{1-tz}}{1+\frac{tz\left(1-(tz)^{m-1}\right)}{1-tz}}-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1} &=\frac{1-(tz)^m}{1-z(1+t-(tz)^{m})}\tag{4} \end{align*}

Denoting with $[z^n]$ the coefficient of $z^n$ in a series we obtain from (4) the number of wanted words as \begin{align*} \color{blue}{f_m(k,n)}&=\binom{k}{n}-g_m(k,n)\\ &\color{blue}{=\binom{k}{n}-[z^kt^{k-n}]\frac{1-(tz)^m}{1-z(1+t-(tz)^{m})})}\tag{5} \end{align*}

Example: Let's look at OPs example. We set $k=10,n=7$ and $m=2$ and we obtain with some help of Wolfram Alpha \begin{align*} \color{blue}{f_2(10,7)}&=\binom{10}{7}-[z^{10}t^3]\frac{1-(tz)^2}{1-z(1+t-(tz)^{2})}\\ &=120-[z^{10}t^3]\left(1 + (t + 1) z + (2 t + 1) z^2\right.\\ &\qquad\left. + \cdots + (6 t^5 + 35 t^4 + \color{blue}{56} t^3 + 36 t^2 + 10 t + 1) z^{10} + \cdots\right)\\ &=120-56\\ &\,\,\color{blue}{=64} \end{align*} with probability

\begin{align*} \color{blue}{p_2(10,7)}=\binom{10}{7}^{-1}f_2(10,7)=\frac{64}{120}\color{blue}{=\frac{8}{15}=0.5\dot{3}} \end{align*}

The blue colored coefficient of $z^{10}$ shows there are $\color{blue}{56}$ binary words of length $10$ with $3$ zeros and runs of $0$ with length less than $k=2$. The blue colored result $\color{blue}{64}$ is the number of valid words having runs of zeros of length at least $2$.

These $64$ words are $$ \begin{array}{cccc} \color{blue}{00}01111111&1\color{blue}{00}0111111&11\color{blue}{00}011111&111\color{blue}{00}01111\\ \color{blue}{00}10111111&1\color{blue}{00}1011111&11\color{blue}{00}101111&111\color{blue}{00}10111\\ \color{blue}{00}11011111&1\color{blue}{00}1101111&11\color{blue}{00}110111&111\color{blue}{00}11011\\ \color{blue}{00}11101111&1\color{blue}{00}1110111&11\color{blue}{00}111011&111\color{blue}{00}11101\\ \color{blue}{00}11110111&1\color{blue}{00}1111011&11\color{blue}{00}111101&111\color{blue}{00}11110\\ \color{blue}{00}11111011&1\color{blue}{00}1111101&11\color{blue}{00}111110&11101\color{blue}{00}111\\ \color{blue}{00}11111101&1\color{blue}{00}1111110&1101\color{blue}{00}1111&111011\color{blue}{00}11\\ \color{blue}{00}11111110&101\color{blue}{00}11111&11011\color{blue}{00}111&1110111\color{blue}{00}1\\ 01\color{blue}{00}111111&1011\color{blue}{00}1111&110111\color{blue}{00}11&11101111\color{blue}{00}\\ 011\color{blue}{00}11111&10111\color{blue}{00}111&1101111\color{blue}{00}1&\\ 0111\color{blue}{00}1111&101111\color{blue}{00}11&11011111\color{blue}{00}&\\ 01111\color{blue}{00}111&1011111\color{blue}{00}1&&\\ 011111\color{blue}{00}11&10111111\color{blue}{00}&&\\ 0111111\color{blue}{00}1&&&\\ 01111111\color{blue}{00}&&&\\ \\ 1111\color{blue}{00}0111&11111\color{blue}{00}011&111111\color{blue}{00}01&1111111\color{blue}{00}0\\ 1111\color{blue}{00}1011&11111\color{blue}{00}101&111111\color{blue}{00}10\\ 1111\color{blue}{00}1101&11111\color{blue}{00}110&11111101\color{blue}{00}\\ 1111\color{blue}{00}1110&1111101\color{blue}{00}1&\\ 111101\color{blue}{00}11&11111011\color{blue}{00}&\\ 1111011\color{blue}{00}1&&\\ 11110111\color{blue}{00}&&\\ &&\\ &&\\ \end{array} $$

Formula of $f_m(k,n)$:

We derive a formula of $f_m(k,n)$ from (5) manually. It is convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series.

We obtain from (5) \begin{align*} \color{blue}{f_m(k,n)}&=\binom{k}{n}-[z^kt^{k-n}]\frac{1-(tz)^m}{1-z(1+t-(tz)^m}\\ &=\binom{k}{n}-[z^kt^{k-n}]\sum_{j=0}^\infty z^j\left(1+t-(tz)^{m}\right)^j\left(1-(tz)^m\right)\tag{6}\\ &=\binom{k}{n}-[t^{k-n}]\sum_{j=0}^k [z^{k-j}]\left(1+t-(tz)^{m}\right)^j\left(1-(tz)^m\right)\tag{7}\\ &=\binom{k}{n}-[t^{k-n}]\sum_{j=0}^k [z^j]\left(1+t-(tz)^{m}\right)^{k-j}\left(1-(tz)^m\right)\tag{8}\\ &=-[t^{k-n}]\sum_{j=1}^{\lfloor k/m\rfloor}[z^{mj}]\left(1+t-(tz)^{m}\right)^{k-mj}\left(1-(tz)^m\right)\tag{9}\\ &=-[t^{k-n}]\sum_{j=1}^{\lfloor k/m\rfloor}[z^{mj}]\sum_{l=0}^{k-mj}\binom{k-mj}{l}\left(1-(tz)^m\right)^{l+1}t^{k-mj-l}\tag{10}\\ &=-[t^{k-n}]\sum_{j=1}^{\lfloor k/m\rfloor}[z^{mj}]\sum_{l=0}^{k-mj}\binom{k-mj}{l}\sum_{u=0}^{l+1}\binom{l+1}{u}(-1)^{u}(tz)^{mu}t^{k-mj-l}\tag{11}\\ &=[t^{k-n}]\sum_{j=1}^{\lfloor k/m\rfloor}\sum_{l=0}^{k-mj}\binom{k-mj}{l}\binom{l+1}{j}(-1)^{j+1}t^{k-l}\tag{12}\\ &\,\,\color{blue}{=\sum_{j=1}^{\lfloor k/m\rfloor}\binom{k-mj}{n}\binom{n+1}{j}(-1)^{j+1}}\tag{13}\\ \end{align*} with probability \begin{align*} \color{blue}{p_m(k,n)=\binom{k}{n}^{-1}f_m(k,n)} \end{align*} in accordance with (0).

Comment:

  • In (6) we do a geometric series expansion.

  • In (7) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$. We also set the upper limit to $k$, since other terms do not contribute.

  • In (8) we change the order of summation $j\to k-j$.

  • In (9) we sum over multiples of $m$ only by setting $j\to mj$ since we have $z^{m}$ in the binomial expansion. We also note that $\binom{k}{n}$ is canceled with the first summand $j=0$ since $[z^0t^{k-n}](1+t-(tz)^m)^k(1-(tz)^m)=[t^{k-n}](1+t)^k=\binom{k}{k-n}=\binom{k}{n}$.

  • In (10) we expand the binomial.

  • In (11) we expand the binomial.

  • In (12) we select the coefficient of $z^{mj}$ by selecting the summand with $u=j$.

  • In (13) we select the coefficient of $t^{k-n}$ by selecting the summand with $l=n$.

Example revisited:

By calculating OPs example ($k=10,n=7,m=2$) now with formula (13) we obtain \begin{align*} \color{blue}{f_2(10,7)}&=\sum_{j=1}^5\binom{10-2j}{7}\binom{8}{j}(-1)^{j+1}\\ &=\binom{8}{7}\binom{8}{1}\\ &\,\,\color{blue}{=64} \end{align*} in accordance with the result above.

Note that here we only take the summand $j=1$, since other terms have lower index $7$ greater than the upper index $10-2j$, so that the binomial coefficients are zero.

$\endgroup$
  • $\begingroup$ This is great; thank you! Also: Within the first indented sentence I had guessed correctly who the answerer was. :) $\endgroup$ – Benjamin Dickman Dec 22 '18 at 19:25
  • $\begingroup$ @BenjaminDickman: You're welcome and many thanks for your amusing remark. :-) $\endgroup$ – Markus Scheuer Dec 22 '18 at 19:48
  • 1
    $\begingroup$ @BenjaminDickman: I've added a derivation of an explicit formula to complete the job. $\endgroup$ – Markus Scheuer Dec 23 '18 at 8:19
7
$\begingroup$

Denote the sizes of the runs of empty bins as $x_1, \ldots, x_{n + 1}$. (Note that there are at most this many runs, so runs may be empty; i.e., $x_j = 0$.) Now, count the number of nonnegative integer solutions to

$$ x_1 + \cdots + x_{n + 1} = k - n $$

that have at least one $x_j \ge m$. This is equivalent to solving the problem.

To count this quantity, use the facts that:

  1. The number of nonnegative integer solutions to $$ x_1 + \cdots + x_k = n $$ is $$ \binom{n + k - 1}{k - 1}\text. $$ This is a simple stars and bars argument.
  2. The number of nonnegative integer solutions to $$ x_1 + \cdots + x_k = n $$ with each $x_j < c$ is $$ \binom{n + k - 1}{k - 1} - \sum_{i = 1}^{\lfloor n / {c} \rfloor} {(-1)}^{i + 1} \binom{k}{i}\binom{n - c i + k - 1}{k - 1}\text.\tag{*}\label{*} $$ To show (\ref{*}), recall the complementary form of the inclusion–exclusion principle. Namely, we can count the number of nonnegative integer solutions with each $x_j < c$ as $$ \begin{align} && \text{the number of all (unrestricted) solutions} \\ &-& \text{the number of solutions with one } x_j \geq c \\ &+& \text{the number of solutions with two } x_j \geq c \\ &-& \cdots \\ &{(-1)}^{\lfloor n / {c} \rfloor}& \text{the number of solutions with }\lfloor n / {c} \rfloor \text{ } x_j \geq c\text. \end{align} $$ Now, how do you count the number of solutions that have $i$-many $x_j \geq c$? It's quite simple; write those $x_j$ as $c + y_j$ (since we already know they're greater than or equal to $c$), and you already have a reduction to the stars and bars argument, but with $n' = n - c i$. This tells us that the number of solutions with $i$-many $x_j \geq c$ is $\binom{n - c i + k - 1}{k - 1}$. The $\binom{k}{i}$ factor counts the number of ways to have this scenario.
$\endgroup$
  • 1
    $\begingroup$ Nice answer! I think the number of variables should be $n+1$, rather than $k-n$. The variables are the gaps between the balls, and there are $n$ balls, so $n+1$ gaps. $\endgroup$ – Mike Earnest Dec 11 '18 at 14:36
  • $\begingroup$ Thank you; you are right. I corrected the answer and checked that it agrees with the one for $m = 2$ (math.stackexchange.com/a/3035312/112944). $\endgroup$ – d125q Dec 11 '18 at 14:44
  • $\begingroup$ Could you say something about the second fact? The first one looks to me like stars and bars, but is the second one... stars and bars combined with the inclusion-exclusion principle? $$ $$ If you could indicate how this works in practice for, say, $n = 6$, $k = 10$, and $m = 2$, then that would be very helpful, too. (And could compared with @MikeEarnest's answer, as well as the hand computations I've done.) Thanks! $\endgroup$ – Benjamin Dickman Dec 11 '18 at 16:21
  • 1
    $\begingroup$ @BenjaminDickman Give the inclusion exclusion a try! The idea is this; you take all of the solutions, then for each variable subtract the cases where the variable is “bad”, meaning more than $m$, then add back in the cases where two variables are bad, etc. $\endgroup$ – Mike Earnest Dec 11 '18 at 16:45
  • 1
    $\begingroup$ @BenjaminDickman I added some "proof sketches." $\endgroup$ – d125q Dec 20 '18 at 15:48
4
+50
$\begingroup$

This is supposed to be an integration to d125q's answer, as to better explain how to reach to the formula he gave, but it is too long for a comment.

You are placing $0$ or $1$ ball in every bin.
We are clearly speaking of undistiguishable balls.
While, speaking of consecutive bins, that implies that the bins be distinguishable (i.e. labelled, i.e. aligned in a row).

Then your problem is equivalent to :

given all the binary strings of length $k$, with $n$ ones (and $n-k$ zeros), how many of them will contain one or more runs of consecutive zeros whose length is $m$ or greater ?

The number of binary strings of length $k$ and with $n$ ones is $\binom{k}{n}$.
So the complement of the above will be the number of strings where the length of each run of consecutive zeros is less than $m$, and naturally, in a binary string we can exchange the zeros with the ones.

Now, to keep congruence with the precedent posts I am going to cite, let me change the formulation and the parameters of the problem with the following:

Consider a binary string with $s$ "$1$"'s and $m$ "$0$"'s in total. Let's put an additional (dummy) fixed $0$ at the start and at the end of the string. We individuate as a run the consecutive $1$'s between two zeros, thereby including runs of null length. With this scheme we have a fixed number of $m+1$ runs.
(refer also to the similar post).

Bernoulli_runs_1

Then, imposing that each run does not contain more than $r$ ones is equivalent to compute $$N_{\,b} (s,r,m+1) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m+1} = s \hfill \\ \end{gathered} \right.$$ which as explained in this other post is expressed as $$ N_b (s,r,m + 1)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s} {r}\, \leqslant \,m + 1} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} m + 1 \\ k \\ \end{gathered} \right)\left( \begin{gathered} s + m - k\left( {r + 1} \right) \\ s - k\left( {r + 1} \right) \\ \end{gathered} \right)} $$ Note that by rewriting the binomial in the way shown above render the summation bounds implicit in the binomial, so that they can be omitted (that's why they are indicated in brackets), which is of great advantage in performing algebraic manipulations.

I think that an effective way to understand the above is by developing the polynomial $$ \eqalign{ & \underbrace {\left( {1 + x + x^{\,2} + \cdots + x^{\,r} } \right) \cdot \left( {1 + \cdots + x^{\,r} } \right) \cdot \; \cdots \; \cdot \left( {1 + \cdots + x^{\,r} } \right)}_{m\;times} = \cr & = \left( {{{1 - x^{\,r + 1} } \over {1 - x}}} \right) = \sum\limits_{0\, \le \,\,s\,\,\, \le \,m\,r} {N_b (s,r,m)\;x^{\,s} } \cr} $$ thereby having the o.g.f. in $s$, and from there easily getting the recursion $$ N_{\,b} (s,r,m + 1) = \sum\limits_{i\, = \,0}^r {N_{\,b} (s - i,r,m)} $$

Finally note that the $N_b$ are called "r-nomial coefficients" in OEIS: see e.g. Table A008287.

$\endgroup$
  • 1
    $\begingroup$ @BenjaminDickman good that the o.g.f. is explicative. Sorry for the broken links: adjusted. $\endgroup$ – G Cab Dec 19 '18 at 17:06
3
$\begingroup$

There's a nice way to do this if $m = 2.$ I describe it here, although it does not solve the more general problem indicated in the question.

We can get a classic "random" arrangement if the bins are identifiable and the balls are not distinguishable, so I'll make those assumptions.

In each bin we either place one ball or no balls. We choose $n$ of the bins in which to place the $n$ balls, leaving $n - k$ empty. The number of ways to do this is $$\binom k{k-n} = \binom kn,$$ each way equally probable.

Another way to think about those same arrangements of balls and bins is that we have $k - n$ empty bins, with a run of zero or more full bins before the first empty bin, after the last empty bin, and between each consecutive pair of empty bins. That is, we are putting $n$ balls into $k - n + 1$ "super bins", where each "super bin" is a run of zero or more filled bins.

As a check on the last interpretation of the problem, the number of ways to put zero or more indistinguishable items into each of $k - n + 1$ containers, placing a total of $n$ items, is $$ \binom{n + (k - n + 1) - 1}{(k - n + 1) - 1} = \binom k{k - n}.$$

So that is the number of equally probable events in our sample space. Now let's count the number of these events that do not have two consecutive empty bins. That means that the $k - n - 1$ runs of full bins that lie between consecutive pairs of empty bins must each include at least one full bin. Having determined that we need $k - n - 1$ balls placed in this way, we see that there are no such arrangements if $n < k - n - 1,$ that is, if $2n - k + 1 < 0.$ On the other hand, if $n + 1\geq k$ there are not even two empty bins anywhere and so it is guaranteed that we will not have two adjacent empty bins. But if $2n - k + 1 \geq 0$ and $n + 1 < k,$ then the number of ways to place the remaining $2n - k + 1$ full bins into the $k - n + 1$ runs (including the ones on each end) is $$ \binom{(2n - k + 1) + (k - n + 1) - 1}{(k - n + 1) - 1} = \binom{n + 1}{k - n}. $$

So the probability of two consecutive empty bins is $0$ if $n + 1 \geq k$; if $2n - k + 1 < 0$ the probability is $1$; and in all other cases the probability is $$ 1 - \frac{\displaystyle\binom{n + 1}{k - n}}{\displaystyle\binom k{k - n}} = 1 - \frac{(n + 1)! \,n!}{(2n - k + 1)!\, k!}. $$

$\endgroup$
3
$\begingroup$

There is the possibility to calculate numerically the result with a rather simple recursive equation.

We will assume $m = 2$ in the following.
To simplify the notation, we will consider that $0$ represents the case "no ball" and $1$ the case "with a ball".
We note $f(k, n)$ the probability associated with $k$ and $n$.
We represent the set of possibilities as a graph.
We consider three cases for the first bins:

  • 1 in the first bin. Probability $\frac{n}{k}$. The subgraph corresponds to $f(k-1, n-1)$
  • 01 in the first 2 bins: Probability $\frac{k-n}{k} \times \frac{n}{k-1}$. The subgraph corresponds to $f(k-2, n-1)$
  • 00 in the first 2 bins: Probability $\frac{k-n}{k} \times \frac{k-1-n}{k-1}$ -> we get the $m$ holes.

Then, we obtain, for $m = 2$

$$f(k,n) = \frac{n}{k} f(k-1, n-1) + \frac{n(k-n)}{k(k-1)} f(k-2, n-1) + \frac{(k-n)(k-1-n)}{k(k-1)}$$

We note in addition that $f() = 0$ if $k-n \le m-1$ and that $f() = 1$ if $n=0$ and $k \ge m$

This recursive formula can be generalised for higher values of $m$, although it becomes more difficult.

This is clearly not as satisfactory as a close form formula. However, it can be represented on a graph rather easily, and it is easy to program.
It may be used for secondary school students.

Note: the program gives $f(10, 7, 2) = \frac{8}{15}$

EDIT:
When I arrived at this point, I suspected something ...
Is there a much simpler solution ?
I thought having found a simple formula, it was a mistake ...

EDIT 2: C++ programme for $m = 2$

#include <iostream>
#include <iomanip>

double f2(int k, int n) {       // m = 2
    if ((k - n) <= 1) return 0.0;
    if (n == 0) return 1.0;
    double res = double ((k-n)*(k-1-n)) / (k*(k-1))
        + (double (n*(k-n)) / (k*(k-1))) * f2(k-2, n-1)
        + (double (n)/k) * f2(k-1, n-1);
    return res;
}

int main() {
    int k = 10;
    int n = 7;
    double prob = f2(k, n);
    std::cout << "f = " << std::setprecision(12) << prob << "\n";
    return 0;
}

EDIT 3: Display of a part of the graph.
"0:3/10" means that the line above corresponds to "0" (no ball), and that the corresponding probability is equal to 3/10. SB means "subgraph", and the near figure corresponds to the probability associated to this subgraph. This also illustrates the low efficiency of the scheme in terms of computation. However, again, it was not the goal of this proposal.

                      f(10,7)=8/15
                        /      \
                       /        \
                      /          \
                   0:3/10       1:7/10
                  SB:1/8        SB:f(9,6)=7/12                     
                  /    \               |     \
                 /      \              |      \
                /        \             |       \
             0:2/9      1:7/9         0:1/3     1:2/3
            SB:1.0   SB:f(8,6)=1/4   SB:13/28   SB:f(8,5)=9/14
                        /     \        |   \        |       \
                       /       \       |    \       |        \
                                       |     \
                                     0:1/4    1:3/4
                                     SB:1.0   SB:f(7,5)=2/7
                                                  /     \
                                                 /       \ 
$\endgroup$
  • $\begingroup$ Could you indicate how the described program outputs 8/15? I find myself not quite able to follow the description and suspect seeing those steps written out could help me! $\endgroup$ – Benjamin Dickman Dec 19 '18 at 16:47
  • $\begingroup$ Sorry, I was really unclear. I mentioned the easiness to write a programme . .. I wrote such a C++ (very simple) programme for $m=2$ and use it. I might post it. You need to represent what I present in a graph ...Easy to follow with such a graph in front of the eyes. ... Not so easy without $\endgroup$ – Damien Dec 19 '18 at 17:04
  • $\begingroup$ Including the program and a graph would be great $\endgroup$ – Benjamin Dickman Dec 19 '18 at 20:39
  • 1
    $\begingroup$ I have included the C++ programme. I will try now to draw a graph. Much easier by hand than creating a figure, without any drawing software at home ... $\endgroup$ – Damien Dec 19 '18 at 21:49
  • 1
    $\begingroup$ I tried to display a part of the graph. Hope it is clear enough $\endgroup$ – Damien Dec 20 '18 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.