0
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ See also math.stackexchange.com/questions/686703/… --- where I raised a question for the author. $\endgroup$ Feb 23, 2014 at 9:21
  • $\begingroup$ Is the question clear now $\endgroup$ Feb 23, 2014 at 9:27
  • 1
    $\begingroup$ i don't understand what is being asked here. $\endgroup$ Feb 23, 2014 at 9:35
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 23, 2014 at 12:26
  • 1
    $\begingroup$ For $k=2,$ the number is $\frac{1}{2}\left(3^N-2^{N+2}-2N+11\right).$ $\endgroup$ Feb 23, 2014 at 13:18

1 Answer 1

0
$\begingroup$

It looks like these are the numbers tabulated here. Some recurrences are given, but no closed form formula. For example,

$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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .