Generating function for tuples of objects based on their maximal size

Question

This is a question which arose while working through Flajolet-Sedgewick's Analytic Combinatorics.

In their terminology, the cartesian product of two combinatorial classes $\mathcal{A},\mathcal{B}$ gives a new combinatorial class

$$\mathcal{C}=\mathcal{A}\times \mathcal{B}$$

and the generating function of $\mathcal{C}$ is simply

$$C(z)=A(z)\cdot B(z).$$

However, this rule assumes that the "size" of the objects in $\mathcal{C}$ is inherited as

$$\forall a\in\mathcal{A},b\in\mathcal{B}:|(a,b)|_{\mathcal{C}}:=|a|_{\mathcal{A}}+|b|_{\mathcal{B}}$$

Now, assume I define a different product $$\mathcal{C}=\mathcal{A}\circ\mathcal{B}$$ which shall fulfill that

$$|(a,b)|_{\mathcal{C}}:=\max(|a|_{\mathcal{A}},|b|_{\mathcal{B}})$$

What would then be the rule to obtain $C(z)$. Simple counting brings me to

$$C(z)=\sum_{n,m\in\mathbb{N}_0}A_n B_m z^{\max(n,m)}=...$$ $$ = \sum_{k\in\mathbb{N}_0}\left(\sum_{n\leq k}(A_n B_k+A_k B_n)-A_k B_k\right)z^k$$

But I was unable to bring this to a "simple" form, which expresses $C(z)$ in terms of $A(z)$ and $B(z)$. Can anyone help?

Answer 1

Note that if $\sum_kA_kz^k=A(z)$, then

$$ \left(\sum_{n\le k}A_n\right)z^k=A(z)(1+z+z^2+\cdots)=\frac{A(z)}{1-z}\;. $$

Thus you have

$$ \sum_{k\in\mathbb{N}_0}\left(\sum_{n\leq k}(A_n B_k+A_k B_n)-A_k B_k\right)z^k=\frac{A(z)}{1-z}\star B(z)+A(z)\star \frac{B(z)}{1-z}-A(z)\star B(z)\;, $$

where $\star$ denotes the Hadamard product given by coefficient-wise multiplication. As discussed e.g. here, here and here, Hadamard products are non-trivial. Since the equation can't be solved for a Hadamard product, it doesn't prove that your problem is equivalent to (and hence as hard as) taking Hadamard products, but it does show that if you do find a simpler form, it's going to have to involve at least a bit of a detour. My guess would be that this is the best you'll be able to get in the general case.