This one is of my own devising, I thought the solution was interesting

Given a list of items [1..N], how many permutations are there, as a function of N, where no element has moved more than one space away from its original position?

E.g. with three items:

[213] is valid, [312] (the 3 has moved too far) is not.

f(1)=1
f(2)=2
f(N)=f(N-1)+f(N-2)

If 1 stays at the first place, the rest of the list, [2...N], has f(N-1) possibilities. If 1 left its place, it must at the second afterwards and the only number in first place can be 2, therefore the rest of the list, [3...N], has f(N-2) possibilities.

F(N) = Fib(N+2)

And, yes, it is interesting. There is probably some fascinating connection that we are missing.

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

Even though it is interesting, I think there's no special connection between Fibonacci and this subset of the symmetric group. Of all recursive sequences in which f(N) is built by f(N-1) and f(N-2), the sum of those is the most simple one. So the interesting thing here for me is, that the formula is not very complex and contains just two cases.

Yep, same solution I got (though I started with f(0) = 1).

For the programmers among us, it might be interesting to write a program that generates all valid permutations efficiently


So now, a follow-up challenge:

Generalize towards any distance, i.e: F(N,K) is the number of permutations of a list of N items where no item has moved more than K spaces from its original position. (This one I'm still puzzling on myself)

interesting...
conjecture: does that mean that no cycle of length greater than k+1 can exists (true for k=1)?
not sure but seems plausible
if true would that help ?
mmm i am gonna obsess about that one

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

I've been thinking about this one also. Not having the advantages of an Agean breeze, I'm not coming up with a good answer.

The best I've got is that as K approaches N-1, F(N) approaches N!

In other words...

Assuming N > K, N > 0, K > 0

F(N,0) = 1 1 1 1 1 1 ...
F(N,1) = 1 2 3 5 8 13 21 ...
F(N,2) = 1 2 6 14 ...
F(N,3) = 1 2 6 24 ...
...
F(N,N-1) = 1 2 6 24 120 760 ... = N!

I think I have the beginnings of a formula. For the first term that deviates from the factorial, the formula looks like this:

3 = 6 - ( 2 + 2 - 1 )
14 = 24 - ( 6 + 6 - 2 )

F(N,K) = N! - ( 2(N-1)! - K )

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

Interesting! The first term that deviates from the factorial would be the case where K = N-2, right? Because K >= N-1 yields the factorial.

For K = N-2, the only invalid permutations would be those where the last element moves to the first position, or the first element moves to the last. Both invalidating (N-1)! permutations. Except we've counted double those cases where both happen at the same time, which are (N-2)! cases. So I guess that means, for K = N-2:

F(N,K) = N! - (2(N-1)! - (N-2)!)

I hadn't thought yet of approaching the problem from the other side, seeing which cases are invalid and subtracting them from all N! permutations. Food for thought!

It looks like you got the last term in the formula. I was trying to do it as a function of K, not N.

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

BTW...

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

This seems to be equivalent to the problem I posted, actually

Since permutations where no element moves more than one place can only be produced by swapping numbers, we can encode the permutation as a binary string, where a 1 signifies that an item has been swapped with the next one. Since you swap with the next item, that one cannot be swapped as well, which means you cannot have consecutive 1's in the binary string. Also, you can never swap the last one, so you need one less bits than items.

Which means that all valid permutations of a list of 5 items can be encoded in a 4 bit string with no consecutive 1's, giving us F6 = 8 options

interesting to

intersting but i doubt the formula stay that simple for K around N/2. As observed By HH, you have very few permutation removed when K=N-1,N-2, but when K is around N/2 or below, you remove a whole bnunvh of them.

My conjecture above


is totally wrong:
consider the permutation:
1->3->5->..->2p+1->2p->2p-2 ->....->4->2->1
this is a cycle of length 2p+1 with max dist=2
and this shed some lights to why it is so much harder for K>1 : simple recurrences falls into pieces.
Here is a shot at the case K=2:

lets look for a rec for F(N,2):

if 1 stays in place : F(N-1,2) combinaisons.
if we have a permutation of 1 and 2:
F(N-2,2) combinaisons. (same as K=1 case so far).

Now for the new cases: 1 is send to 3 and/or 3 send to 1:

if transposition of 1 and 3: 2 can either stay in place (F(N-3,2) possibilities as we must permute 4....N) or be transposed with 4: F(N-4,2) possibilities (we must permute 5...N).
Now a cycle with 1,2,3: lets assume that 1->2 and 3->1 (we'll double the cases for the reverse cycle 1->3 2->1).
in that case 2 must go either to 3 (cycle of length 3)or 4 .
That cycle AS TO BE of the form above:
1->2->4->..->2p->2p-1->2p-3 ->....->3->1 (length 2p)
OR. 1->2->4->..->2p->2p+1->2p-1 ->....->3->1 (length 2p+1)
So 1 is part of a cycle which span all elements from 1 to k without "holes".
Then we must permute elements k+1....N:

So sum_{k=3,N} F(N-k,2) permutations in that case.
(and a factor of 2 for reverse cycle)

Final recurrence looks like:
F(N,2)= F(N-1,2)+F(N-2,2)+F(N-3,2) + F(N-4,2)+ 2 sum_{k=3,N}F(N-k,2)


(there is probably errors BUT the point is its doable to reduce to a recurrence like that)
with F(1,2)=1
F(2,2)=2
F(3,2)=6

and this is kept simple because for k=2 there is no "hole" possible: we can describe all possible cycle including 1 and reduce F(N-k,2) to F(N-k,2) with lower N.. this fails with k>2 as you can leave holes in the cycle of 1 ie for K=4:
1->3->7->4->1
2->5->6->2
We could maybe describe again for K=3 with some efforts but it will get harder and harder as K rises with more and more cases.
Hard problem

Edite for clarity

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

aa maybe a step forward:
EDIT: that's WRONG see below
Lets consider The permutation S_N(n) of N elements.
Lets assume that There is exists k0 <N such as:
S_N(n)<=k0 if n<=k0
S_N(n)>k0 if n>k0 (the permutation can be "partioned" at k0)

We have
F'(K,N)=sum_{p=1,N} F(K,p)F(K,N-p)

where F'(K,N) is the number of permutation such that |S_N(n)-n|<k AND there exists a partition of the permutation.

Now we "just" have to estimate the permutations that are parts of F(K,N) which does NOT have this property.
if we call this number G(N,K) : number of permutations without a partition but such as |S(n)-n|<=k
we have:
F(N,K)=G(N,K)+ sum_{p=1,N} F(K,p)F(K,N-p)

we have F(K,N)=N! if N<=K

For K=1, K=2 G(N,K)=0 (i think) which simplified the computation

mmmmm still
hope the above is not too wrong (EDIT: IT IS)

Edited for clarity

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

The above is really wrong.
We are counting multiple time permutation with several partition , and we do not even recover the established formulas for K=1,K=2

the good formula to avoid multiplecounting is:

F(N,K)=sum_{p=1,N}G(p,K)F(N-p,K)
where again we call G(N,K) : number of permutations of N elements without a partition but such as |S_N(n)-n|<=k
(here p simply represents the position of the lowest partition of a permutation which is unique)
(F(0,K)=1 by convention)

with G(1,K)=G(2,K)=1 for all K
G(n,1)=0 for n>2 (you always have a partition after element 2)
so for K=1 we have the Fibonacci formula above.

for K=2: (standard cycle notation) number of permutation with NO partition and |S_N(n)-n|<=2
G(1,2)=1 : (1)
G(2,2)=1 : (1 2)
G(3,2)=3 : (1 2 3),( 3 2 1 ), (1 3) (2) [ the other permutations: (1) (2) (3),(12) 3 and (1) (2 3) have a partition]
G(4,2)=3 : (1 2 4 3), (1 3 4 2), ( 1 3 )( 2 4 )
for p>4 we can only have the odd-even cycle described above: (1 3..2p+1 2p 2p-2 ... 2 1 ) and the reverse, so
G(p,2)=2 for all p>4

So we recover the formula for K=2
F(N,2)= F(N-1,2)+F(N-2,2)+F(N-3,2) + F(N-4,2)+ 2 sum_{k=3,N}F(N-k,2)

The nightmare begins with K=3 to compute G(N,3)... i dont see any easy rec, neither with K nor N
So this formula is of little practical help except to show that K=1 and K=2 are indeed special simple cases and to generalize the reasoning for K=1 and K=2

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

edit: I owe Herman a more serious reaction than my deleted one.

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.

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.

i

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

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

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 ?

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

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.

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)

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.