# Alternating Pair

I want to find the number of permutations of $1,2,\ldots,N$ having exactly $k$ triples satisfying the condition that either $n_{i-1}>n_i<n_{i+1}$ or $n_{i-1}<n_i>n_{i+1}.$

For example for N=4

0 conditions matching = 2 because permutation $1234$ and $4321$ don't satisfy the given condition.

1 matching should give 12 because in following permutation only once the condition is met  2 1 3 4 3 1 2 4 3 2 1 4 1 2 4 3 4 1 2 3 4 2 1 3 1 4 3 2 1 3 4 2 4 3 1 2 2 4 3 1 3 4 2 1 2 3 4 1

Similarly for 2 conditions matching it should give 10 because, 10 permutations are such that exactly 2 times the conditions are met.  1 3 2 4 2 3 1 4 2 1 4 3 1 4 2 3 2 4 1 3 4 1 3 2 3 1 4 2 3 4 1 2 4 2 3 1 3 2 4 1  I want a formula for counting all such conditions seperately, ex for 2 conditions, 3 conditions and so on.

• See also math.stackexchange.com/questions/686703/… --- where I raised a question for the author. Feb 23, 2014 at 9:21
• Is the question clear now Feb 23, 2014 at 9:27
• i don't understand what is being asked here. Feb 23, 2014 at 9:35
• I don't have a good idea at the moment. Have you looked at the link in Gerry Myerson's answer? That sequence is, indeed, the answer to your question. A sequence with $k+1$ alternating runs will have $k$ triples satisfying your condition. Clearly for $k=0$ there are two permutations. For $k=1$, the number is $2^N-4.$ This is not that hard to see. I'm not sure whether one can expect a closed form for general $k$. Gerry Myerson's link only gives a recurrence and an exponential generating function. Feb 23, 2014 at 12:26
• For $k=2,$ the number is $\frac{1}{2}\left(3^N-2^{N+2}-2N+11\right).$ Feb 23, 2014 at 13:18

$P(n, k)=0$ if $n\lt2$ or $k\lt1$ or $k\ge n$;
$P(2, 1)=2$;
$P(n, k)=kP(n-1, k)+2P(n-1, k-1)+(n-k)P(n-1, k-2)$.