Let a1... , a, be a permutation of 1, 2,..., n. We say that this sequence...

  

Transcribed Image Text:

Let a1... , a, be a permutation of 1, 2,..., n. We say that this sequence is a zig-zag sequence if, for every 2 <i < n, either: • a, is greater than all the numbers occurring before it in the sequence, i.e. greater than each of a;-1, aj-2,..,a1, or • a, is less than all the numbers occurring before it in the sequence, i.e. less than each of a-1, ai-2, ., a1. How many of the n! permutations of 1,2,...,n are zig-zag sequences? Let a1... , a, be a permutation of 1, 2,..., n. We say that this sequence is a zig-zag sequence if, for every 2 <i < n, either: • a, is greater than all the numbers occurring before it in the sequence, i.e. greater than each of a;-1, aj-2,..,a1, or • a, is less than all the numbers occurring before it in the sequence, i.e. less than each of a-1, ai-2, ., a1. How many of the n! permutations of 1,2,...,n are zig-zag sequences?

Answer rating: 100% (QA)

S n be the set of permutations on 1 2 n Let A n denote the number of zigzag permutations in S n We g... View the full answer