0

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)$?

J. W. Tanner
  • 60,406
user19872448
  • 135

1 Answers1

1

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."

angryavian
  • 89,882
  • in your example for $n=2$ do you refer to $\mathcal{R}_2^{(2)}={12,21}$? – user19872448 Nov 14 '23 at 01:00
  • 1
    @user19872448 No, $\mathcal{R}^{(2)} = {12, 21}$. Updated my answer to clarify what I mean. – angryavian Nov 14 '23 at 01:02
  • ok, now $\mathcal{R}^{(2)}$ is clear to me, but it is not completely clear to me how to interpret $1;\text{Seq}(1);2;\text{Seq}(1+2)\cup 2;\text{Seq}(2);1;\text{Seq}(1+2)$, could you give me (if possible) another way to interpret this? – user19872448 Nov 14 '23 at 03:05
  • my doubt is in $\text{Seq}(1+2)$ – user19872448 Nov 14 '23 at 03:07
  • 1
    @user19872448 My last sentence explains how to interpret it. $\text{Seq}(1+2)$ denotes the class of strings constructed from the digits $1$ and $2$. – angryavian Nov 14 '23 at 03:28
  • Ok, now I understand perfectly. One last question (and sorry for so many questions), for example, in the case ${12}$ which corresponds to $1;\text{Seq}(1);2;\text{Seq}(1+2 )$, how is it justified that $\text{Seq}(1)$ and $\text{Seq}(1+2)$ are "empty"? – user19872448 Nov 14 '23 at 04:21
  • Intuition tells me that it is because the size must be 2, so all that remains is to discard it, but is there a more "formal" way to say it? – user19872448 Nov 14 '23 at 04:24
  • 1
    Revisit the definition of the Seq operator. $\text{Seq}(\mathcal{A})$ consists of sequences of objects from $\mathcal{A}$, including the empty sequence. – angryavian Nov 14 '23 at 04:38
  • $\text{Seq}(1)={\epsilon, 1, 11, 111,...}$, right? – user19872448 Nov 14 '23 at 05:03
  • then the expression refers to the fact that I must choose an element from $\text{Seq}(1)$!! – user19872448 Nov 14 '23 at 05:04
  • Yes, that's right. – angryavian Nov 14 '23 at 05:14