0
$\begingroup$

Let $(S_i)_{i \in \mathbb{N}}$ be a sequence of sets defined recursively as follows:

  • $S_1 = \{1\}$
  • $S_{i+1} = S_i \cup \{S_i, i+1\} \quad \forall i \in \mathbb{N}$

A permutation $\sigma$ of $S_i$ is deemed valid if it satisfies these conditions:

  1. Internal Order Preservation:

    • If $a, b \in S_i$ with $a \neq S_{i-1}$ and $b \neq S_{i-1}$, and $a < b$ in the natural ordering of $\mathbb{N}$, then $\sigma^{-1}(a) < \sigma^{-1}(b)$.
    • For any $j < k < i$, we have $\sigma^{-1}(S_j) < \sigma^{-1}(S_k)$.

  2. Successor Placement: $\sigma^{-1}(i) > \sigma^{-1}(S_{i-1})$.

Is there a closed-form expression or an efficient algorithm to compute the number of valid permutations of $S_i$, denoted $|VP(S_i)|$, for any $i \in \mathbb{N}$.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ "Thus, each $S_i$ is a finite set containing the natural numbers from $1$ to $i$, and also all preceding sets $S_j$ for $j < i$.": this does not match the way you defined $S_{i+1}$ in the preceding line; the way you defined it, $S_{i+1}=\{1,\ldots,i+1\}$. $\endgroup$
    – Sam Hopkins
    Commented Aug 21 at 22:01
  • $\begingroup$ I don't think I understand the definition. If $\sigma^{-1}(i) > \sigma^{-1}(x)$ for all $x \in S_{i - 1}$, then $\sigma^{-1}(i)$ is greater than $i - 1$ distinct elements of $S_i$, so it must equal $i$. Then (1) just says that $\sigma$ is order-preserving on $S_{i - 1}$. (Ah, and now I see that I read the formal definition and missed the informal description of $S_i$, which, as @SamHopkins says, doesn't match the formal definition. If you did mean the informal definition, then what's the (total?) order on $S_i$?) $\endgroup$
    – LSpice
    Commented Aug 21 at 22:01
  • 4
    $\begingroup$ Your update makes less sense. Now each $S_i$ is a two element set, so there are only two "permutations" of it (if permutations are understood in the usual sense as bijections from a finite set to itself). $\endgroup$
    – Sam Hopkins
    Commented Aug 21 at 22:17
  • 2
    $\begingroup$ In condition 1, shouldn't it be $a,b\in\mathbb N$ rather than $a\ne S_{i-1}$ and $b\ne S_{i-1}$? Otherwise one can take, say, $a=S_{i-2}$ with no "natural ordering". And even if $a,b$ are numbers, $\sigma^{-1}(a)$ and $\sigma^{-1}(b)$ may be not numbers but some $S_i$ - how do you compare them? $\endgroup$
    – Max Alekseyev
    Commented Aug 22 at 1:15
  • 4
    $\begingroup$ Can you do an example? Say the case $i=3$ or $i=4$? Clearly you have something specific in mind but it seems you are having trouble communicating it. $\endgroup$
    – Sam Hopkins
    Commented Aug 22 at 1:55

0

Reset to default

You must log in to answer this question.