Life In 19x19

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.

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

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 )

Joaz Banbeck wrote: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, 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 )

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!

HermanHiddema wrote:... we've counted double those cases where both happen at the same time, which are (N-2)! cases...

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

BTW...

wikipedia wrote:The Fibonacci numbers can be found in different ways in the sequence of binary strings.

* The number of binary strings of length n without consecutive 1s is the Fibonacci number Fn+2. For example, out of the 16 binary strings of length 4, there are F6 = 8 without consecutive 1s – they are 0000, 1000, 0100, 0010, 1010, 0001, 1001 and 0101. By symmetry, the number of strings of length n without consecutive 0s is also Fn+2.
* The number of binary strings of length n without an odd number of consecutive 1s is the Fibonacci number Fn+1. For example, out of the 16 binary strings of length 4, there are F5 = 5 without an odd number of consecutive 1s – they are 0000, 0011, 0110, 1100, 1111.
* The number of binary strings of length n without an even number of consecutive 0s or 1s is 2Fn. For example, out of the 16 binary strings of length 4, there are 2F4 = 6 without an even number of consecutive 0s or 1s – they are 0001, 1000, 1110, 0111, 0101, 1010.

Joaz Banbeck wrote:BTW...

wikipedia wrote: * The number of binary strings of length n without consecutive 1s is the Fibonacci number Fn+2. For example, out of the 16 binary strings of length 4, there are F6 = 8 without consecutive 1s – they are 0000, 1000, 0100, 0010, 1010, 0001, 1001 and 0101. By symmetry, the number of strings of length n without consecutive 0s is also Fn+2.

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

Joaz Banbeck wrote: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 )

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

perceval wrote: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

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

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

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

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