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

Yes it is the same approach i agree

True

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

_________________
In theory, there is no difference between theory and practice. In practice, there is.

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 ?) :


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

_________________
In theory, there is no difference between theory and practice. In practice, there is.

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

_________________
In theory, there is no difference between theory and practice. In practice, there is.

I uploaded an illustrative picture from wikipedia-multicombination.


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)

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

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

_________________
In theory, there is no difference between theory and practice. In practice, there is.

You understood me perfectly. thx for clarifying.


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


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 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.

I checked the tip in the book and it said to prove the formula for G as we found it. So this brings us not any further.

Next I tabled F(15,k,r):


C(n,k)↓ k↓ r→ 1 2 3 4 5 6 7 8
105 2 14 13 12 11 10 9 8 7
455 3 169 121 81 49 25 9 1 0
1365 4 870 369 111 15 0 0 0 0
3003 5 2541 441 21 0 0 0 0 0
5005 6 4795 210 0 0 0 0 0 0
6435 7 6399 36 0 0 0 0 0 0
6435 8 6434 1 0 0 0 0 0 0
5005 9 5005 0 0 0 0 0 0 0
3003 10 3003 0 0 0 0 0 0 0
1365 11 1365 0 0 0 0 0 0 0
455 12 455 0 0 0 0 0 0 0
105 13 105 0 0 0 0 0 0 0
15 14 15 0 0 0 0 0 0 0
1 15 1 0 0 0 0 0 0 0

Also of little help. So I am about to give up. I will publish the answer from the book shortly unless someone attacks this Bastille.

mm to me it is solved:

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

The fact that it does not simplify to something nice is irrelevant imho.
computation wise, the k! does simplify so your are left with 3 mult of k terms, 1 substraction and one div which is simple (for a computer)

_________________
In theory, there is no difference between theory and practice. In practice, there is.

Here is the solution in the book. As you see the result is the same as ours. Their derivation is a bit more elegant because they don't use multicombinations.
Where they write f_r(n,k) we wrote G(n,k,r).

book solution is elegant indeed

_________________
In theory, there is no difference between theory and practice. In practice, there is.