Permutations Restricted By Primes

[David Wasserman]

>I was wondering, how many permutations <n(1),n(2),...,n(m)> are there of
><1,2,...,m>, where
>
>n(k) < n(k-1) whenever k is prime,
>n(k) > n(k-1) whenever k is composite?

I find this sequence interesting.

Let T(m, j) be the number of permutations of this kind that end with j.
(So your sequence is a(m) = sum T(m, j), j = 1..m.)
Then T obeys a recurrence:
	T(1, 1) = 1;
	T(m, j) = sum T(m-1, i), i = j..m-1   if m is prime;
and	T(m, j) = sum T(m-1, i), i = 1..j-1   if m is composite.

(To see why this works, think of n(1), n(2), ... as real numbers instead of as a permutation.  So given <n(1),n(2),...,n(m)>, you can extend it to length m+1 by adding n(m+1) between the other members of the sequence.)

So T begins with
1
1,0
1,0,0
0,1,1,1
3,3,2,1,0
0,3,6,8,9,9
35,35,32,26,18,9,0

and the sequence begins with
1,1,1,3,9,35,155.

Neither is in OEIS.

>Another possible sequence would be the number of permutations, where (as 
>above)
>n(k) < n(k-1) whenever k is prime,
>but there is no restriction on n(k) if k is composite.
>
>And of course, we can use other criteria besides primeness to generate 
>other permutation-counting sequences using the same basic idea.
>
>thanks,
>Leroy Quet

In general,
	T(m, j) = sum T(m-1, i), i = j..m-1   if n(m) must be < n(m-1);
	T(m, j) = sum T(m-1, i), i = 1..j-1   if n(m) must be > n(m-1);
and	T(m, j) = sum T(m-1, i), i = 1..m-1   if there is no restriction.

 - David