# The number of the union-intersection calculation results equals to the number of paths

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?

• @Henry Fixed. Thanks! Nov 6, 2023 at 3:57
• 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 Nov 6, 2023 at 9:06
• @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. Nov 6, 2023 at 14:14
• So you are saying $1, 2, 4, 10, 24, 66,172, \ldots$ which seems to be A084078 or A137842. Nov 6, 2023 at 17:39
• @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... Nov 6, 2023 at 17:40

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.

• 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)...? Nov 23, 2023 at 22:36
• 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! Nov 23, 2023 at 22:43
• @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$. Nov 24, 2023 at 3:15