In Flajolet's symbolic method, given a combinatorial class $\mathcal{A}$, $\text{Seq}(\mathcal{A})$ is defined as $\mathcal{E}+\mathcal{A}\times \mathcal{A}+ \mathcal{A}\times\mathcal{A}\times \mathcal{A}+... $ and assuming that the generating function of $\mathcal{A}$ is $A(z)$ then the generating function of $\text{Seq}(\mathcal{A})$ is $1+A(z)+A(z)^2+A(z)^3+...=\frac{1}{1-A(z)}$.In the bibliography it is requested that $\mathcal{A}$ be a combinatorial structure without objects of size $0$, but it is not clear to me why, could someone explain it to me (I think the same thing happens with the $\text{Cyc}( \mathcal{A})$ operation).
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
If there is an object $z\in \mathcal A$ with weight zero, then there would be infinitely many sequences in $\text{Seq}(\mathcal A)$ with weight zero. Namely, $$ (z),(z,z),(z,z,z),\dots,(z,z,\dots,z),\dots $$ all have weight zero. A combinatorial class is only allowed to have finitely many elements of each weight, so $\text{Seq}(\mathcal A)$ is not a well-defined combinatorial class in this case.
answered Apr 13 at 0:23
-
$\begingroup$ Is it the only class in which this case occurs? $\endgroup$ Apr 13 at 4:49
-
1$\begingroup$ @user19872448 Same is true for $\text{Cyc}$ and $\text{MSet}$. There might be others. $\endgroup$ Apr 13 at 16:12
-
$\begingroup$ so, to define $\text{Seq}(\mathcal{A})$ $\mathcal{A}$ must not have a neutral element, but if I define $\mathcal{B}=\text{Seq}(\mathcal{A})$ then $\mathcal{B}$ does have a neutral element ? $\endgroup$ Apr 20 at 22:07
-