2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, your guess that there might be no simpler solution is exactly what I am afraid of :) $\endgroup$ – flonk Sep 1 '15 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.