-1
$\begingroup$

I am trying to solve a combinatorial problem regarding a specific class of permutations.

The Problem: Consider a permutation $\sigma$ of the set $\{1, 2, \dots, n\}$, where $n=13$. The permutation satisfies the condition that for every index $i$ (where $2 \le i \le n$), the element $\sigma_i$ is either strictly greater than all preceding elements or strictly smaller than all preceding elements.

Formally, for all $i \in \{2, \dots, n\}$: $$ \sigma_i > \max(\sigma_1, \dots, \sigma_{i-1}) \quad \text{or} \quad \sigma_i < \min(\sigma_1, \dots, \sigma_{i-1}) $$

How many such permutations exist for $n=13$?

My Attempt: I started by looking at small cases to find a pattern:

  • For $n=1$: There is only $(1)$. (1 permutation)
  • For $n=2$: The permutations are $(1,2)$ and $(2,1)$. Both satisfy the condition. (2 permutations)
  • For $n=3$:
    • $(1,2,3)$ works (2 is max, 3 is max).
    • $(3,2,1)$ works (2 is min, 1 is min).
    • $(2,1,3)$ works (1 is min, 3 is max).
    • $(2,3,1)$ works (3 is max, 1 is min).
    • $(1,3,2)$ fails because 2 is neither greater than 3 nor smaller than 1.

It seems like for each step $i$, we have two choices relative to the previous elements, but I am unsure how to formalize this into a general formula for $n=13$.

Any insights or hints on how to count these would be appreciated.

Tags: combinatorics, permutations, discrete-mathematics

$\endgroup$
4
  • 2
    $\begingroup$ What is the context of your question? What did you try to answer it? $\endgroup$ Commented Nov 16 at 8:53
  • $\begingroup$ Hint: how many such permutations start with 1? How many start with 2? How many start with 3? ... $\endgroup$ Commented Nov 16 at 9:03
  • 1
    $\begingroup$ Welcome to Mathematics SE. Take a tour. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. $\endgroup$ Commented Nov 16 at 9:10
  • 2
    $\begingroup$ A simple Google search shows that this has been asked and answered before: math.stackexchange.com/q/3126642/42969. $\endgroup$ Commented Nov 16 at 9:11

1 Answer 1

Reset to default
2
$\begingroup$

Let $a_n$ be the number of such permutations of $\{1,2,\dots,n\}$. Notice that the last element of any such permutation must be either the global maximum or the global minimum—that is, either $1$ or $n$. By removing the last element, we therefore obtain a valid permutation of either $\{1,2,\dots,n-1\}$ or $\{2,3,\dots,n\}$.

Conversely, by appending $n$ to a valid permutation of $\{1,2,\dots,n-1\}$, or appending $1$ to a valid permutation of $\{2,3,\dots,n\}$, we obtain a valid permutation of $\{1,2,\dots,n\}$.

This shows that there is a bijection between the set consisting of valid permutations of $\{1,2,\dots,n-1\}$ together with those of $\{2,3,\dots,n\}$, and the set of valid permutations of $\{1,2,\dots,n\}$. The cardinality of the former set is $a_{n-1} + a_{n-1}$, while the cardinality of the latter set is $a_n$. Since there is a bijection, we obtain the recursive formula \begin{equation} a_n = 2a_{n-1}. \end{equation}

Finally, because $a_1 = 1$, applying the recurrence gives \begin{equation} a_n = 2^{n-1}, \end{equation} and in particular \begin{equation} a_{13} = 2^{12} = 4096. \end{equation}

$\endgroup$
1
  • 2
    $\begingroup$ This question seems not to meet the standards for the site. Instead of answering it, why not look for a good duplicate target, or help the user by posting comments suggesting improvements? Please also read the meta announcement regarding quality standards. $\endgroup$ Commented Nov 16 at 9:11

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.