10
$\begingroup$

Problem Statement:

Let $A_1,A_2,\dots,A_{2k+1}$ be $2k+1$ generic sets. We insert $\cap$ and $\cup$ alternately between them, as $A_1\cap A_2\cup A_3\dots\cup A_{2k+1}$. The calculation results depend on how I add the parentheses, as $A_1\cap (A_2\cup A_3)$ generally does not equal to $(A_1\cap A_2)\cup A_3$. But sometimes different parenthesis may have same results, as $((A_1\cap A_2)\cup (A_3\cap A_4))\cup A_5$ equals to $(A_1\cap A_2)\cup ((A_3\cap A_4))\cup A_5)$. Among all possible ways to add the parentheses, how many distinct results (for general sets) are there? What about $2k$ sets?

I have written some code and looked for OEIS, and it turns out the $2k$-set case matches A032349 and $2k+1$-set case matches A027307. The description for the sequence is partially correct. Both of them are considering paths taking steps $(2,1),(1,2),(1,-1)$ and does not fall below $x$ axis, but A032349 has wrong starting point and destination: it should be from $(0,1)$ to $(3k+1,0)$.

I have tried several ways to deal with this, such as deriving a recurrent formula for the number of results (as we deal with Catalan) or doing bijection (I have make the number of sets to some kind of trees). However, I failed.

One of my friends hinted this literature as "schroder path" or "full ternary tree", but I cannot understand it...

Can anyone craft an easy-to-understand bijection or proof? Thank you all!

P.S. As @Henry pointed out there is another combinatorial interpretation of the sequence, which is A084078. It is the length of generating sequences, starting from $[0]$ (see it as a python list), and every time we substitute each $k$ the values $-|k+1|,-|k+1|+2,\dots,|k-1|$. For example, initial is $[0]$, and the range for $0$ is $[-1,1]$, so $[0]$ becomes $[-1,1]$. Now for $-1$ the range is $[0,2]$ and for $1$ it is $[-2,0]$, so the sequence becomes $[0,2,-2,0]$. Then the sequence becomes $[-1,1,-3,-1,1,-1,1,3,-1,1]$, and so on. Now the question becomes more complecated... is there a (bijective, hopefully) proof for proving the number of these three items to be equal?

$\endgroup$
10
  • $\begingroup$ @Henry Fixed. Thanks! $\endgroup$
    – JetfiRex
    Nov 6, 2023 at 3:57
  • $\begingroup$ I suspect your friend may have been looking at something like A006318. I am not clear what initial terms of the sequence(s) you have found $\endgroup$
    – Henry
    Nov 6, 2023 at 9:06
  • $\begingroup$ @Henry Oh, the initial terms are the same (there are no offsets). That is, if there are $2k$ sets, it is the $k$ th term of A032349. If there are $2k-1$ terms, it is $k$th term of A027307. $\endgroup$
    – JetfiRex
    Nov 6, 2023 at 14:14
  • $\begingroup$ So you are saying $1, 2, 4, 10, 24, 66,172, \ldots$ which seems to be A084078 or A137842. $\endgroup$
    – Henry
    Nov 6, 2023 at 17:39
  • $\begingroup$ @Henry That is right. Yes, if you join the two sequence together it is A137842. I split the odd and even case is because the starting and ending point are not the same. Thank you for finding another combinatorial implication as A084878 However, I still could not find the bijection and prove the relations though... $\endgroup$
    – JetfiRex
    Nov 6, 2023 at 17:40

1 Answer 1

4
+200
$\begingroup$

This may not be an elegant solution, but it does the job.

We can map every parenthesization of $A_1\cap A_2\cup A_3\cap A_4\cup A_5\cap \dots$ onto a plane tree with internal vertices labeled $\cup$ or $\cap$ and leaves labeled $A_1,A_2,A_3,\dots\,$, where internal vertex labels alternate away from the root. Given a tree with root $R$ whose children are subtrees $(T_1,\dots,T_k)$, $k\ge 2$, from left to right, we can read off the sequence $\ell(T)$ of the labels of the internal vertices of $T$ as follows: $$ \ell(T)=(\ell(T_1),\ell(R),\ell(T_2),\ell(R),\ell(T_3),\dots,\ell(R),\ell(T_k)). $$ We also let $|\ell(T)|$ be the length of $\ell(T)$ (which we we also define to be the \emph{size} of $T$) and give each internal vertex weight $z$, so that a tree $T$ has weight $z^{|\ell(T)|}$. We want to ensure that the sequence $\ell(T)$ is alternating, and then it is uniquely determined, since it starts with a $\cap$.

To ensure the labels alternate, $|\ell(T_i)|$ must be odd for all $i=2,\dots,k-1$, i.e. each subtree except the leftmost one and the rightmost one must be of odd size. For a tree $T$ with internal vertices, let $T_l$ and $T_r$ be its left and right subtrees, respectively. Moreover, since the root labels of all subtrees $T_i$, $i=1,\dots,k$, must be different from $\ell(R)$, we must have the following:

  • the rightmost subtree $T_{1,r}$ of $T_1$ must be of even size,
  • the leftmost subtree of $T_{k,l}$ of $T_k$ must be of even size,
  • both the leftmost subtree $T_{i,l}$ and the rightmost subtree $T_{i,r}$ of each subtree $T_i$, $i=2,\dots,k-1$, must be of even size.

Define the following classes of trees:

  • $\mathcal{E}=\{T\mid\ell(T)\text{ is alternating and } |\ell(T)| \text{ is even}\}$,
  • $\mathcal{O}=\{T\mid\ell(T)\text{ is alternating and } |\ell(T)| \text{ is odd}\}$.

Then we can define the following subclasses of $\mathcal{O}$ and $\mathcal{E}$:

  • $\mathcal{E}'_l=\{T\mid T\in\mathcal{E}, \text{ and } |\ell(T_l)| \text{ is even}\}$,
  • $\mathcal{E}'_r=\{T\mid T\in\mathcal{E}, \text{ and } |\ell(T_r)| \text{ is even}\}$,
  • $\mathcal{O}'=\{T\mid T\in\mathcal{O}, \text{ and } |\ell(T_l)| \text{ and } |\ell(T_r)| \text{ are even}\}$.

Then, for $T\in\mathcal{O}$ with root degree $k\ge 2$, we have $T_2,\dots,T_{k-1}\in \mathcal{O}'$, and for $T_l=T_1$ and $T_r=T_k$, either $T_1,T_k\in \mathcal{E}'$, or $T_1,T_k\in \mathcal{O}'$.

Likewise, for $T\in\mathcal{E}$ with root degree $k\ge 2$, we have $T_2,\dots,T_{k-1}\in \mathcal{O}'$, and for $T_l=T_1$ and $T_r=T_k$, either $T_1\in \mathcal{E}'_l$, $T_k\in \mathcal{O}'$, or $T_1\in \mathcal{O}'$, $T_k\in \mathcal{E}'_r$.

Define the following generating functions:

  • $E=E(z)=\displaystyle\sum_{T\in\mathcal{E}}{z^{|\ell(T)|}}$,
  • $O=O(z)=\displaystyle\sum_{T\in\mathcal{O}}{z^{|\ell(T)|}}$,
  • $O_1=O_1(z)=\displaystyle\sum_{T\in\mathcal{O}'}{z^{|\ell(T)|}}$,
  • $E_{1,l}=E_{1,l}(z)=\displaystyle\sum_{T\in\mathcal{E}'_l}{z^{|\ell(T)|}}$,
  • $E_{1,r}=E_{1,r}(z)=\displaystyle\sum_{T\in\mathcal{E}'_r}{z^{|\ell(T)|}}$.

By symmetry (reflecting the tree and switching all labels), we can see that $E_{1,l}=E_{1,r}=E_1=E_1(z)$ for some function $E_1$.

Then, from the above label sequence decompositions, we have the following relations between the above generating functions: \begin{align*} E&=1+\frac{2zE_1O_1}{1-zO_1}, & O&=\frac{z(E_1^2+O_1^2)}{1-zO_1},\\ E_1&=1+\frac{zE_1O_1}{1-zO_1}, & O_1&=\frac{zE_1^2}{1-zO_1}. \end{align*} This implies $$ E=2E_1-1=E_1+\frac{zE_1O_1}{1-2zO_1}=\frac{E_1}{1-zO_1}. $$ Likewise, $$ O=O_1+\frac{zO_1^2}{1-zO_1}=\frac{O_1}{1-zO_1}. $$ Therefore, $$ \frac{O}{O_1}=\frac{O_1}{zE_1^2}, \quad \text{so} \quad O=z\left(\frac{O_1}{zE_1}\right)^2=z\left(\frac{E_1}{1-zO_1}\right)^2=zE^2. $$ Moreover, we see that $$ \frac{O_1}{zE_1}=E, \quad \text{so} \quad O_1=zEE_1=\frac{zE(1+E)}{2} $$ and $$ \begin{split} E&=1+\frac{2zE_1O_1}{1-zO_1}= 1+z(2E_1)\frac{O_1}{1-zO_1}\\ &=1+z(1+E)O=1+z(1+E)(zE^2)\\ &=1+z^2(E^2+E^3), \end{split} $$ i.e. $E=E(z)=r_3(z^2)$ and $O=O(z)=zr_3^2(z^2)$, where $r_3=r_3(z)$ satisfies $$ r_3=1+z(r_3^2+r_3^3), $$ the recurrence relation for A027307.

$\endgroup$
3
  • $\begingroup$ Thank you so much for your time and your answer! I am so sorry to bother you for further questions, but I cannot verify/understand if I cannot understand the following: is it true that $l(T)$ is always an odd number (like $l(T)$ equals $2\times (\text{sets in }T)-1$)...? If $l(T)$ means how many sets are there in $T$, is it true that for $2,\dots,k-1$ the number of sets in $l(T)$ is even (instead of odd)...? $\endgroup$
    – JetfiRex
    Nov 23, 2023 at 22:36
  • $\begingroup$ But I kind of understand the idea as I trying to understand the recursion. Thank you so much! I try to understand it and write it on my own! $\endgroup$
    – JetfiRex
    Nov 23, 2023 at 22:43
  • $\begingroup$ @JetfiRex You’re welcome! $\ell(T)$ is the number of $\cap/\cup$ operations in the string associated with the tree, i.e. the number of sets (leaves) minus $1$. Note that the number of times each internal node of $T$ is counted in $\ell(T)$ is the number of its children minus $1$. $\endgroup$ Nov 24, 2023 at 3:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .