lazy combinatorial species

[Martin R]

I would like to advertise https://github.com/sagemath/sage/pull/38544, implementing https://en.wikipedia.org/wiki/Combinatorial_species, and as a side request the discussion of one important design question, https://github.com/sagemath/sage/pull/38544#issuecomment-2481392240.

The pull request is building on the lazy series framework built with Travis, and the polynomial species class built with Mainak in the last few years.  It is a replacement for the combinatorial species framework redesigned and ported to Sage by Mike Hansen in 2008.

You can do fun stuff like the examples below with the package.  I am a bit proud of the fact that there is no other CAS that can do such things.

I would like to discuss the design question linked to above in a setting a bit broader than on a hidden PR, because I can imagine that it has consequences I cannot foresee yet.  So, please join :-)

Best wishes,

Martin

EXAMPLES::

Let E be the species of sets and G be the species of graphs.  Then the species of connected graphs Gc satisfies E(Gc) = G.  Thus we can compute Gc in a few lines:

sage: L.<X> = LazySpecies(QQ)
sage: E = L.Sets()
sage: Ep = E.restrict(1)
sage: G = L.Graphs()
sage: Gc = Ep.revert()(G-1)
sage: Gc
X + E_2 + (E_3+X*E_2) + (E_4+E_2(E_2)+E_2^2+E_2(X^2)+X*E_3+X^2*E_2) + (E_5+3*E_2*E_3+X*E_4+2*X*E_2(E_2)+4*X*E_2(X^2)+5*X^3*E_2+P_5+3*X*E_2^2+X^2*E_3) + (E_6+3*E_2*E_4+E_2(E_3)+8*X*E_2*E_3+E_3(E_2)+3*E_2*E_2(E_2)+10*E_2*E_2(X^2)+E_3^2+X^2*E_4+16*X^2*E_2^2+5*X^3*E_3+5*E_2(X*E_2)+21*X^4*E_2+X*P_5+2*P_6+2*Pb_6+2*E_2^3+X*E_5+12*X^2*E_2(X^2)+4*E_2(X^3)+2*E_3(X^2)+2*X^2*E_2(E_2)+8*X^6) + (E_7+3*E_2*E_5+3*E_3*E_4+X*E_6+8*X*E_2*E_4+4*E_3*E_2(E_2)+9*E_2^2*E_3+10*E_3*E_2(X^2)+2*X*E_3(E_2)+10*X*E_2*E_2(E_2)+27*X*E_2^3+3*X*E_3^2+X^2*E_5+39*X^2*E_2*E_3+5*X^3*E_4+2*X*E_2(E_3)+112*X^3*E_2^2+21*X^4*E_3+22*X*E_2(X*E_2)+76*X*E_2*E_2(X^2)+6*X^3*E_2(E_2)+2*E_2*P_5+193*X^5*E_2+2*X*P_6+10*X*E_3(X^2)+10*X*Pb_6+74*X^3*E_2(X^2)+2*P_7+50*X*E_2(X^3)+X^2*P_5+144*X^7) + O^8

You want connected graphs where any leaves are labelled with elements of sort Y?  Do the math (eg., Proposition 14 https://arxiv.org/abs/2505.03665, due to Gessel and Li)

sage: L2.<X, Y> = LazySpecies(QQ)
sage: E2 = E.restrict(2, 2)
sage: Gcleaves = (Gc(X*E(Y-X)) - X*Y + X^2 - E2(X))
sage: Gcleaves.truncate(6)
X + (E_3(X)+X*E_2(Y)) + (E_4(X)+E_2(E_2(X))+E_2(X)^2+X*Y*E_2(X)+E_2(X*Y)+X*E_3(Y)) + (E_5(X)+3*E_2(X)*E_3(X)+2*X*E_2(E_2(X))+2*X*E_2(X)^2+P_5(X)+2*X*E_2(X^2)+X*Y*E_3(X)+4*X^2*Y*E_2(X)+X*E_2(X)*E_2(Y)+2*X*E_2(X*Y)+X^2*Y*E_2(Y)+X*E_4(Y))
sage: Gcleaves.isotype_generating_series()
X + (X^3+X*Y^2) + (3*X^4+X^3*Y+X^2*Y^2+X*Y^3) + (11*X^5+5*X^4*Y+3*X^3*Y^2+X^2*Y^3+X*Y^4) + (61*X^6+29*X^5*Y+14*X^4*Y^2+5*X^3*Y^3+2*X^2*Y^4+X*Y^5) + O(X,Y)^7

Best wishes,

Martin