1
$\begingroup$

I have numbers from $1$..$n$. I want to find number of permutation from all $n!$ permutation where the numbers have following arrangement.

$L$ $G$ $L$ $G$ $L$ or $G$ $L$ $G$ $L$ $G$.

Where L means that the number is less than $G$.

for ex if $n$=$4$ than I want to find following permutation

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

Here number of such permutation is $10$. I want to generalize it for any $n$.

$\endgroup$
6
  • $\begingroup$ "Where L means that the number is less than G." Fine, but what does $G$ mean? I cannot figure out what you are asking. $\endgroup$ Feb 23, 2014 at 8:16
  • $\begingroup$ it means the number can either be ni-1<ni>ni+1 or ni-1>ni<ni+1 $\endgroup$ Feb 23, 2014 at 8:23
  • $\begingroup$ So, each number is either bigger than both its neighbors, or smaller than both its neighbors? $\endgroup$ Feb 23, 2014 at 8:24
  • $\begingroup$ yes, thats correct. $\endgroup$ Feb 23, 2014 at 8:29
  • 1
    $\begingroup$ Evidently not, since you want $(32451)$. $\endgroup$ Feb 23, 2014 at 8:35

1 Answer 1

1
$\begingroup$

These are called alternating permutations, see http://oeis.org/A001250

$\endgroup$
7
  • $\begingroup$ sorry can you elaborate with example. The link is not much clear $\endgroup$ Feb 23, 2014 at 8:08
  • $\begingroup$ I read about alternating permutation, but my question is not exactly about them $\endgroup$ Feb 23, 2014 at 8:10
  • 1
    $\begingroup$ I don't see the difference between alternating permutations, and what you are asking about. Can you give an example of an alternating permutation that you don't count? or a permutation you do count that isn't alternating? $\endgroup$ Feb 23, 2014 at 8:27
  • $\begingroup$ Take n=5, than 3 2 4 5 1 is not an alternating permutation but as you can see but 324 and 451 are required permutation $\endgroup$ Feb 23, 2014 at 8:31
  • $\begingroup$ True, but the numbers on either side of $4$, one of them is bigger than $4$, and the other is less than $4$. So I still don't understand what permutations you want. $\endgroup$ Feb 23, 2014 at 8:35

You must log in to answer this question.

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