let A[i][j] be the number of i permutations that start with j and we jump 2. The recurrence is:
a[i][1] = a[i - 1][1] + a[i - 1][2],
a[i][2] = a[i - 1][2] + a[i - 3][2]

I use the same methon...But I got Wa????

We can do it more easyly!
Just think of this:
1 2 ... means N - 1;
1 3 2 4 means N - 3;
1 3 5 7...6 4 2 only 1;
1 3 4 2 (only N == 4);
So we can DP;

test

You can using this:

  Initilization:
  a[1]:=1;
  a[2]:=1;
  a[3]:=2;

  And solve:
  a[i]:=a[i-1]+a[i-3]+1;

So, your answer in a[n]

I konw why I was WA...... Very thanks!!!!

I've solved it with help of asympthotic. Starting from 20 - 25-th member (it can be found recursively) - a[i] ~ a[i-1]*(a[i-1]/a[i-2])

Well, actually I decovered this formula after writing brute force algorithm. I am wondering how it could be proven.

Any ideas?

Edited by author 10.04.2004 02:04

I don't understand your formula .
Could you explain ?

But Timgreen had almost proved it.

write the permutations down and look it carefully as hard as you can and you'll find out sth useful for you associated with the informations provided above by all the upper friends...

Take i=5 for example

The permutations are:

1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 3 2 4 5
1 3 5 4 2

a[i-1] stands for the first four, beginning with '1 2'. If you ignore 1, you have the same prob for N=i-1.
a[i-3] stands for the fifth, beginning with '1 3 2 4'. If you ignore 1, 3, 2, you have the same prob for N=i-3.
And a special case (the last) -- all the odds in increasing order, followed by all the evens in decreasing order. The is what the +1 in the formula means.

Good luck!

thanks for explanation.

I used another method to solve this.

Suppose we have N numbers.
We will care about five possible configurations:

K(n)  ... n n-1 ...
T(n)  ... n-1 n ...
E(n)  ... n-2 n
P(n)  ... n n-1
S(n)  ... n-1 n

here K(n) is the number of correct configurations of the first type and so on.

It's clear that the answer for N will be K(N)+T(N)+E(N)+P(N)+S(N).

So, what we need to do is understand how to get K(n+1),T(n+1)... from K(n),T(n),...

And it is very easy to see that following is true:

K(n+1) = T(n)
T(n+1) = K(n)+P(n)
E(n+1) = P(n)
P(n+1) = S(n)
S(n+1) = S(n)+E(n)

Can somebody give tests? for exmaple for 6,10,55... Thanks.

for 6 , ans = 9
for 10, ans = 46
for 55, ans = 1388937263

my formula is:
a[i][1] = a[i-1][1] + a[i-2][2]
a[i][2] = a[i-2][1] + 1
But i don't understand your formula?
Could you explain??

Edited by author 14.07.2008 22:25

Can you explain your formul?how should I use it!)

I don't know if we can call this a proof. This is an observation I guess.