Express the class $\mathcal{R}$ of surjections in terms of $\text{Seq}$?

57 Views Asked by At

While studying these notes about two-level constructions in analytical combinatorics I noticed that the following is mentioned

$\mathcal{R}^{(2)}= 1\,\text{Seq}(1)\,2\,\text{Seq}(1+2)\cup 2\,\text{Seq}(2)\,1\,\text{Seq}(1+2)$. And that equality is not clear to me, I understand the following:

$\mathcal{R}^{(2)}=\mathcal{R}^{(2)}_1\cup\mathcal{R}^{(2)}_2$, where $\mathcal{R}^{(2)}_1$ are surjections of the form $\phi_1:\{1\}\to\{1,2\}$, and $\mathcal{R}^{(2)}_2$ are surjections of the form $\phi_2:\{1,2\}\to\{1,2\}$.

Then $\mathcal{R}^{(2)}_1=\{(1)(2)\}$, and $\mathcal{R}^{(2)}_2=\{(12)(21)\}$ (I'm right?)

Then $\mathcal{R}^{(2)}=\mathcal{R}^{(2)}_1\cup\mathcal{R}^{(2)}_2=\{(1)(2)\}\cup \{(12)(21)\}= \{(1)(2)(12)(21)\} $

So, my question becomes the following,assuming my analysis is correct, why $ \{(1)(2)(12)(21)\}= 1\,\text{Seq}(1)\,2\,\text{Seq}(1+2)\cup 2\,\text{Seq}(2)\,1\,\text{Seq}(1+2)$?

1

There are 1 best solutions below

11
On BEST ANSWER

I think you are misinterpreting.

$\mathcal{R}^{(2)}$ is a class (indexed by $n$) that counts surjections $\varphi : [1 .. n] \to \{1, 2\}$. Surjections can be represented by the string "$\varphi(1), \varphi(2), \ldots, \varphi(n)$."

$\mathcal{R}^{(2)}$ can be partitioned into two classes $\mathcal{R}^{(2)}_1$ and $\mathcal{R}_2^{(2)}$ based on whether $\varphi(1)=1$ or $\varphi(1) = 2$ respectively.

For example, for $n=2$, the equation $\mathcal{R}^{(2)} = \mathcal{R}^{(2)}_1 \cup \mathcal{R}^{(2)}_2$ is $$\{12, 21\} = \{12\} \cup \{21\},$$ and for $n = 3$, $\mathcal{R}^{(2)} = \mathcal{R}^{(2)}_1 \cup \mathcal{R}^{(2)}_2$ is $$\{112, 122, 121, 211, 212, 221\} = \{112, 122, 121\} \cup \{211, 212, 221\}.$$

You should read $1 \text{Seq}(1) 2 \text{Seq}(1+2)$ as "a string that starts with $1$, followed by a nonnegative number of $1$s, followed by a $2$, followed by a nonnegative number of other digits."