YAMP (Yet Another Math Puzzle)

[cyclops]

Yesterday I visited my go book dealer to get a fresh shot. Instead of a go book I scored a math book. It poses lots of problems. One somehow reminds me of Herman's.

Let n and k be some definite integers such that 2 <= k <= n and N be the set {1,2, .. ,n} and a k-selection be a strictly increasing sequence of k numbers from N. For such k-selection S we define W(S) as the smallest absolute difference between two of its consecutives numbers. If S is chosen randomly from N then what is the probability distribution of W(S)?
Resuming. S: ( 1 <= ) A1 < A2 ... < Ak ( <= n ) integers & W(S): the smallest step. Probability that W(S) is some given natural number?

After one week I give the book's hint and after two weeks the solution. Both hidden.
Hidden here my first obvious observation.

1 <= W(S) <= (n-1)/(k-1) since k -1 steps makes at most n - 1 difference

[cyclops]

I apologize for this ugly contribution. I started writing before realizing how messy it would become. Because I believe that it is basically correct I couldn't help but posting it.

The problem is not Herman's but the one stated in my previous post. I think there are similarities, so I feel justified in my topic jacking even more because everything here is Off Topic.

In the remaining I keep n and k fixed. I underscore stochasts. So S is a random k-selection from N. A₁ is the first number of this selection.
W(S) is the stochastic function that represents the smallest step in S.
We need to find f(n,k,r) defined as f(n,k,r) = P(W(S) = r ) for 1 < k <= n and 1 <= r <= (n-1)/(k-1). For convenience we define f = 0 for other k or r. The easy case is for k = n because then W(S) = 1.
Hence f(n,n,r) = 1 for r = 1 but zero otherwise. .......... (1)
For k = 2. We count the number of pairs at distant r apart. There are n - r such pairs. But there are ( n over 2 ) arbitrary pairs.
So f(n,2,r) = 2(n-r)/(n*(n-1)) ..............(2)

I will express f(n,k,r) in terms of several f(m,l,s) where m is smaller than n. Thus f is determined by recursion.

f(n,k,r) = P(A₁ = 1 ) * P(W(S) = r | A₁ = 1 ) + P(A₁ > 1 ) * P(W(S) = r | A₁ > 1 ) ...... ( 3 )
P(A₁ = 1 ) = k/n ............. ( 4 )
P(A₁ > 1 ) = 1 - k/n .............( 5 )
P(W(S) = r | A₁ > 1 ) = f(n-1,k,r) .......(6)

The remaining factor is less easy but doable.
We split this case in two disjoint subcases. In the first subcase the first step equals r and the remaining steps are at least r. Its probability given A₁ = 1 is
P1 = ( N - 2s over k - 2 )/ ( N - 1 over k - 1 ) * ( 1 - Sum ( f(n-2s, k-2, t ))).... (7)
where the sum is over positive integers t < s
In the second subcase the first step is bigger then r and the remaining steps are at least r but at least one equals r. Its probability given A₁ = 1 is
P2 = ( N - s -1 over k - 1 )/ ( N - 1 over k - 1 ) * f(n-s-1,k-1,s) ...... (8)

For the remaining factor in (3) we substitute the sum of P1 and P2 and we get our recursion formula. I realize that my derivations need some more explanation, but as a start of the solving process they might be fine. Next Mac Gates can compute the numerical values and the problem is solved.

Apart from the fact that the book only allows for elegant solutions.

[perceval]

i

I apologize for this ugly contribution. I started writing before realizing how messy it would become. Because I believe that it is basically correct I couldn't help but posting it.

The problem is not Herman's but the one stated in my previous post. I think there are similarities, so I feel justified in my topic jacking even more because everything here is Off Topic.

In the remaining I keep n and k fixed. I underscore stochasts. So S is a random k-selection from N. A₁ is the first number of this selection.
W(S) is the stochastic function that represents the smallest step in S.
We need to find f(n,k,r) defined as f(n,k,r) = P(W(S) = r ) for 1 < k <= n and 1 <= r <= (n-1)/(k-1). For convenience we define f = 0 for other k or r. The easy case is for k = n because then W(S) = 1.
Hence f(n,n,r) = 1 for r = 1 but zero otherwise. .......... (1)
For k = 2. We count the number of pairs at distant r apart. There are n - r such pairs. But there are ( n over 2 ) arbitrary pairs.
So f(n,2,r) = 2(n-r)/(n*(n-1)) ..............(2)

I will express f(n,k,r) in terms of several f(m,l,s) where m is smaller than n. Thus f is determined by recursion.

f(n,k,r) = P(A₁ = 1 ) * P(W(S) = r | A₁ = 1 ) + P(A₁ > 1 ) * P(W(S) = r | A₁ > 1 ) ...... ( 3 )
P(A₁ = 1 ) = k/n ............. ( 4 )
P(A₁ > 1 ) = 1 - k/n .............( 5 )
P(W(S) = r | A₁ > 1 ) = f(n-1,k,r) .......(6)

The remaining factor is less easy but doable.
We split this case in two disjoint subcases. In the first subcase the first step equals r and the remaining steps are at least r. Its probability given A₁ = 1 is
P1 = ( N - 2s over k - 2 )/ ( N - 1 over k - 1 ) * ( 1 - Sum ( f(n-2s, k-2, t ))).... (7)
where the sum is over positive integers t < s
In the second subcase the first step is bigger then r and the remaining steps are at least r but at least one equals r. Its probability given A₁ = 1 is
P2 = ( N - s -1 over k - 1 )/ ( N - 1 over k - 1 ) * f(n-s-1,k-1,s) ...... (8)

For the remaining factor in (3) we substitute the sum of P1 and P2 and we get our recursion formula. I realize that my derivations need some more explanation, but as a start of the solving process they might be fine. Next Mac Gates can compute the numerical values and the problem is solved.

Apart from the fact that the book only allows for elegant solutions.

interesting i took a bit of tiem to convince myslef that (6) is true.

I find it easier to count the selection with steps egal or greater than r and then to divide by C(n,k) than to think of proab directly (because then you have to translate the proba hen you chaneg n: cf your n/k factores evrywhere)
if i note F(n,k,r) the number of selection (so F(n,k,r)=C(n,k)f(n,k,r)):
i divide in 3 cases:
1) 1 and r+1 are selected:then any selection of k-2 amonsgt r+2...n with a gap at least r is ok
sum_{t>=r} F(n-r+1,k-2,t) selections (1)

2) 1 is selected but the second number selected is greater than r+1:
then the remainder of the selection must have a shortest distance exaclty r:
(here p is the index of the second selected site)
sum_{p>r+1} F(k-2,n-p,r)
3) 1 is not selected, the selection can then be viewed as a selection between 2....n :
there is F(k,n-1,r) such selections
So:

F(n,k,r) = F(n-1,k,r) + sum_{p>r+1} F(n-p,k-2,r) + sum_{t>=r} F(n-r+1,k-2,t)

from there using F(n,k,r)=C(n,k)f(n,k,r) its easy to convert to a rec on f but i find this recursion less messy (but still i dont see an analytic solution)

If there is an elegant solution i doubt its an enumeration

[perceval]

another approach, lets stick with number of conf but switch to G(n,k,r): selection such that that the smallest step is at least r. () (kind of like the cumulative function of F)
of course F(n,k,r)=G(n,k,r)-G(n,k,r+1)

ONLY 2 cases of interest:

1) 1 is not selected, the selection can then be viewed as a selection of k number between 2....n :
there is G(k,n-1,r) such selections

2) 1 is selected:
then any section of k-1 elements amongst r+1 (corrected from 2)....n is ok (thanks to changing the definition to W(s)>=r the proprty is NOT lost when we remove the element 1 from the selection) : G(n-r (corrected),k-1,r)

G(n,k,r) = G(n-1,k,r) + G(n-r (corrected),k-1,r)
we retrieve pascal triangle for r=1

now that looks computable : r does not vary and THERE IS NO SUM


and we have :
f(n,k,r) = [G(n,k,r)- G(n,k,r)]/(C(n,k))


Does someone spots a mistake ?

[cyclops]

In response to your first contribution
- I agree that your notaion using capital F is more handy.
- Apart from that our approach is the same. Your case 1 and case 2 are mine subcase 1 and subcase 2. If the results are not similar one of us must have made a mistake.

perceval: 1) 1 and r+1 are selected:then any selection of k-2 amonsgt r+2...n with a gap at least r is ok
sum_{t>=r} F(n-r+1,k-2,t) selections (1)

The third selected number should be at least 2r+1. So the space for the remaining selections is reduced to n - 2r
so this term should be sum_{t>=r} F(n-2r,k-2,t) selections (1)

perceval: 2)1 is selected but the second number selected is greater than r+1:
then the remainder of the selection must have a shortest distance exaclty r:
(here p is the index of the second selected site)
sum_{p>r+1} F(k-2,n-p,r)

You meant F(n-p,k-2,r). Again you should reduce n-p likewise as in 1).
Above all, you can save yourself another summation if you count the number of exceptable (k-1)selections on [r+2,n].
I'm sure we arrived at the brute force solution. Because I don't feel like implementing it, I leave it at that.

[cyclops]

another approach .....


Does someone spots a mistake ?

brilliant!!!!!
Because r is constant it is solvable by spreadsheet. But first I go after solving the recursion analytically.

[perceval]

In response to your first contribution
- I agree that your notaion using capital F is more handy.
- Apart from that our approach is the same. Your case 1 and case 2 are mine subcase 1 and subcase 2. If the results are not similar one of us must have made a mistake.

sum_{t>=r} F(n-r+1,k-2,t) selections (1)

Yes it is the same approach i agree

he third selected number should be at least 2r+1. So the space for the remaining selections is reduced to n - 2r

True

Above all, you can save yourself another summation if you count the number of exceptable (k-1)selections on [r+2,n].
I'm sure we arrived at the brute force solution. Because I don't feel like implementing it, I leave it at that.

but the solution on the second post is easier as there is no sum at all
[/quote]
True the second summation was not needed. Anyway i think my second post allows to even remove the first summation (and this computation is also not victim of the error the first). It is less brute force an maybe another transformation would allow an anlytic solution

[cyclops]

trying for r = 1, I smell there is something rotten. Because all selections have a minimum stepsize of at least one all selections are acceptable. So your formula should reproduce C(n,k). But it doesn't.
It would fit if G(n,1,1) = n, G(n,n,1) = 1 and G(n,k,1) = G(n-1,k,1) + G(n-1,k-1,1) as in pascal's triangle.
I dare to speculate that if we generalize pascal's triangle to 3 dimensions: pascal's pyramid we have the solution.

[perceval]

trying for r = 1, I smell there is something rotten. Because all selections have a minimum stepsize of at least one all selections are acceptable. So your formula should reproduce C(n,k). But it doesn't.
It would fit if G(n,1,1) = n, G(n,n,1) = 1 and G(n,k,1) = G(n-1,k,1) + G(n-1,k-1,1) as in pascal's triangle.
I dare to speculate that if we generalize pascal's triangle to 3 dimensions: pascal's pyramid we have the solution.

arf off-by-1 error ( did i mentioned i am not detail oriented somewhere ?) :

2) 1 is selected:
then any section of k-1 elements amongst r+2....n is ok (thanks to changing the definition to W(s)>=r the proprty is NOT lost when we remove the element 1 from the selection) : G(n-(r+1),k-1,r)

the selection is amongst r+1....n so G(n-r,k-1,r)

G(n,k,r) = G(n-1,k,r) + G(n-r,k-1,r)
indeed for r=1 we recover pascal triangle egality, which i should have checked ... i am lazy as a programer ...

I am not sure about the pascal pyramide inegality...rather a "skewed triangle" inegality

[cyclops]

...

To resume:
n,k, r positive integers
G(n,k,r) = G(n-1,k,r) + G(n-r,k-1,r)
G(n,1,r) = n
G(n,k,r) = 0 n <= (k-1)*r

I get: G(n,k,r) = C(n - ( r -1 )(k-1),k) when not mistaken, where C is as before the number of combinations.

[perceval]

...

To resume:
n,k, r positive integers
G(n,k,r) = G(n-1,k,r) + G(n-r,k-1,r)
G(n,1,r) = n
G(n,k,r) = 0 n <= (k-1)*r

I get: G(n,k,r) = C(n - ( r -1 )(k-1),k) when not mistaken, where C is as before the number of combinations.

Interesting, Then there must be a more straightforward demonstration. How do you derive it ? seems true for r=1 k=1 and k=2 at least

For the orignal question it gives:

f(n,k,r)= C(n - ( r -1 )(k-1),k) -C(n - r (k-1),k) /C(n,k)= (n-k)![ [n - ( r -1 )(k-1)]!/(n - ( r -1 )(k-1)-k)! - [n - r (k-1)]!/( n - r (k-1)-k)!] /n!

which is ugly a good indication that using the cumulative function was the way to go

[cyclops]

I uploaded an illustrative picture from wikipedia-multicombination.

370px-Combinations_with_repetition;_5_multichoose_3.svg.png (81.51 KiB) Viewed 5368 times

I'll apply the third column on x..x..x..x (misleading point removed here )
How? By adding the corresponding number of dots to the corresponding five slots. The first slot in front of the first x, the last slot after the last x. The others in between We get:
...x..x..x..x
..x...x..x..x
..x..x...x..x
..x..x..x...x
..x..x..x..x.
and so on.

So G(13,4,3)=C(7,4)=35

What a go board is good for
edit: a misleading dot deleted
edit2: the 2 corrected in G(13,4,2) to G(13,4,3)

[cyclops]

Let f be the number of free dots ( 3 in the example ) and s = k+1 the number of slots ( 5 here )
Then we have C(f + s - 1, f ) multicombinations = C(f+k,f) = C(f+k,k)
From given n,k,r lets find f. Because r is the smallest step, each step fixes at least (r-1) dots. So we have (k-1)(r-1) fixed dots. There are k crosses ( x's). So f = n - k -(k-1)*(r-1) ....corrected
So G(n,k,r) = C(n - (k-1)*(r-1),k) as stated before. ..... corrected

Perceval and I climbed the northface of the Eiger to discover there is a staircase at the other side. I want to thank him for his good compagnionships and his brilliant ideas. He did the Hillary Step and the passage through the labyrinth. I found the staircase back to earth.

edit: two corrections: s->r

[perceval]

Your 2 last posts are a bit hard to follow.

Here is what i understand: the ha-ha is that instead of selecting k amongst n, you will place n-(k-1)(r-1) dots in between the selected k to reach a size of n.
ie if r=3 and k=4: you start from: the X represents teh selected k, the x the necessary number in between to insure that the distance is at least r.
XxxXxxXxxX
there is k X and (k-1)(r-1) x to insure minimal distance of r between the X.
Then you can add n- [(k-1)(r-1)+k] other number wherever you want between a x and X (or after the last X, or before the first X): so
you have k+1 slots to add n-[(k-1)(r-1)+k] dots


You can have several of those "dots" in each slot so you are using the multicombinaison formula: which is given by C(k+1 + n-[(k-1)(r-1)+k]-1,k+1-1) (i didnt know or at least totally forgot this simple relation) where i took N=k+1, K= n-[(k-1)(r-1)+k]-1

Indeed we recover the result:

G(n,k,r) = C(n-[(k-1)(r-1)],k)

i felt like there has to be an easy demo after you showed that the result in a simple C(q,k) but failed to find this interpretation, nice that you found it .

Still the initial problem was : asking as a proba computation with S(r)=r was bound to lead into dead ends
interesting one cyclops !

I dont think that might be useful for HH initial problem tough

[cyclops]

Your 2 last posts are a bit hard to follow.

You understood me perfectly. thx for clarifying.

(i didnt know or at least totally forgot this simple relation)

I had a vague remembrance about its existence from 40 yrs ago.

Still the initial problem was : asking as a proba computation with S(r)=r was bound to lead into dead ends
interesting one cyclops !

Working on that and arrived at similar ugly formula's as you did. Maybe the attached picture in my previous post can help us out in the substracting.( just a wild guess)

I dont think that might be useful for HH initial problem tough

I have been thinking on that but I have to admit I didn't study your answers to HH's problem. I have tried to change his problem by arranging "his yachts" circularly. But gave up.