-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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.