Generating function for the number of choices $I,J\!\subseteq[n]$ such that $\max\,[n]\!\setminus\!(I\!\cup\!J) < \max I\!\cap\!J$ Suppose that each pair $I,J\!\subseteq[n]=\{1,\ldots,n\}$ for which 
$$\max\,([n]\!\setminus\!(I\!\cup\!J)) < \max (I\!\cap\!J) \tag{1}$$ contributes $t^{|I|+|J|}$ to a generating function, and each pair $I,J\!\subseteq[n]$ for which 
$$\max\,([n]\!\setminus\!(I\!\cup\!J)) > \max (I\!\cap\!J) \tag{2}$$ contributes $t^{|I|+|J|+1}$ to the same generating function. How can I show that this generating function is the one at the bottom of this calculation (taken from here): 

When $I\cup J=[n]$, this is a special case (that you need not be concerned about) and only $I\!\cap\!J\!=\!\emptyset$ is allowed, so we are counting all choices of $I\!\subseteq\![n]$, of which there are $2^n$, hence we get $2^nt^{|I|+|J|}+2^nt^{|I|+|J|+1}= 2^nt^n+2^nt^{n+1} = (1+t)(2t)^n$, which is the first summand.
But when $I\cup J\subsetneq[n]$, is $L=I\cup J$ or $L=(I\!\cup\!J)\setminus(I\!\cap\!J)$? Where do $$t^3(2t)^{|L|}(1+t^2)^{n-|L|-1} \text{ and } (2t)^{|L|}(1+t^2)^{n-|L|-1} \text{ come from???}$$ I do not understand why $(1)$ should be equivalent to $(1')$ $\max([n]\!\setminus\!(I\!\cup\!J)) \notin K$. I suspect that $K\!=\!I\!\cap\!J$, and that in $(1)$ we have arbitrary $I,J$, but in $(1')$ we have $I=I\!\setminus\!I\!\cap\!J$ and $J=J\!\setminus\!I\!\cap\!J$.
 A: Instead of finding $a_k:=\big|\big\{I,\!J\!\subseteq\![n]; |I|\!+\!|J|\!=\!k, \max(I^C\!\cap\!J^C)\!>\!\max(I\!\cap\!J)\big\}$ $\cup$ $\big\{I,\!J\!\subseteq\![n]; |I|\!+\!|J|\!+\!1\!=\!k, \max(I^C\!\cap\!J^C)\!<\!\max(I\!\cap\!J)\big\}\big|$, we compute the generating function $\sum_{k=0}^{2n+1}\!a_kt^k$. A critical vertex $x_I\!\!\wedge\!y_J$ contributes $t^{|I|+|J|}\!=\!t^{|I\cup J|+|I\cap J|}$ and a critical vertex $x_I\!\!\wedge\!y_J\!\wedge\!z$ contributes $t^{|I|+|J|+1}\!=\!t^{|I\cup J|+|I\cap J|+1}$. 
Let $u_k\!=\!x_k\!\wedge\!y_k$, so that we write any basis element as $x_{I'}\!\!\wedge\!y_{J'}\!\wedge\!u_{K}$ or $x_{I'}\!\!\wedge\!y_{J'}\!\wedge\!u_{K}\!\wedge\!z$, with $I'\!\cap\!J'\!=\! I'\!\cap\!K\!=\! J'\!\cap\!K\!=\!\emptyset$ and $L\!:=\!I'\!\cup\!J'$. If $L\!=\![n]$, then $K\!=\!\emptyset$, hence all $x_{I'}\!\!\wedge\!y_{J'}$ (cannot remove $u_i$) and $x_{I'}\!\!\wedge\!y_{J'}\!\wedge\!z$ (cannot add $u_i$) are critical, contributing $2^nt^n\!+\!2^nt^{n+1}$ (number of subsets $I'\!\subseteq\![n]$ is $2^n$). If $L\!\subsetneq\![n]$, then $x_{I'}\!\!\wedge\!y_{J'}\!\wedge\!u_{K}$ is critical iff $\max(L\!\cup\!K)^C\!>\!\max K$ iff $m\!:=\!\max L^C\!\notin\!K$, contributing 
$$2^{|L|}\sum_{k=0}^{n-|L|-1}\!\!\binom{n\!-\!|L|\!-\!1}{k}t^{|L|+2k} \!=\! 2^{|L|}t^{|L|}\sum_{k=0}^{n-|L|-1}\!\!\binom{n\!-\!|L|\!-\!1}{k}(t^2)^k \!=\! (2t)^{|L|}(1\!+\!t^2)^{n-|L|-1}$$ (number of subsets $I'\!\subseteq\!L$ is $2^{|L|}$, number of subsets $K\!\subseteq\!(L\!\cup\!\{m\})^C$ with $k$ elements is $\binom{n-|L|-1}{k}$), and $x_{I'}\!\!\wedge\!y_{J'}\!\wedge\!u_{K}\!\wedge\!z$ is critical iff $\max(L\!\cup\!K)^C\!<\!\max K$ iff $\max L^C\!\in\!K$, contributing 
$$2^{|L|}\sum_{k=0}^{n-|L|-1}\!\!\binom{n\!-\!|L|\!-\!1}{k}t^{|L|+2(k+1)+1} \!=\! 2^{|L|}t^{|L|+3}\sum_{k=0}^{n-|L|-1}\!\!\binom{n\!-\!|L|\!-\!1}{k}(t^2)^k \!=\! t^3(2t)^{|L|}(1\!+\!t^2)^{n-|L|-1}$$ (number of subsets $I'\!\subseteq\!L$ is $2^{|L|}$, number of subsets $K\!\setminus\!\{m\}\!\subseteq\!(L\!\cup\!\{m\})^C$ with $k$ elements is $\binom{n-|L|-1}{k}$).
