A combinatorial interpretation for certain plethysm and Kronecker coefficients

We give explicit positive combinatorial interpretations for the plethysm coefficients $⟨s_{\mu }[s_{\nu }],s_{\lambda }⟩$, when $\lambda$ has at most two rows, as counting certain marked trees. In the special case $\mu =(n)$, this also yields a combinatorial interpretation for the corresponding rectangular Kronecker coefficient $g(\lambda ,(n^k),(n^k))$. While it is easy to express these quantities as differences of counting problems in the complexity class $\mathrm{F}\mathrm{P}$, putting the problem in $\mathrm{\#}\mathrm{P}$, our interpretations give a positive counting formula over explicit marked trees.