4
$\begingroup$

For $a,b,c \in \mathbb{N}$ let $[a] := \{1,...,a\}$ and suppose a map $h: [a] \rightarrow [c]$ is given. How many choices $(f,g)$ for maps $f: [a] \rightarrow [b]$ and $g: [b] \rightarrow [c]$ are there such that $f \circ g = h$?

It seems to me that there should be a nice graph-theoretical argument that I'm not seeing. By symmetry, the formula shouldn't depend on the exact choice of $h$, but only on the 'degrees' $e_j := h^{-1}(j), \, j \in \{1,...,c\}$ and of course $a,b,c$.

Any help is much appreciated.


Edit: Thanks to Peter Taylor's comment and by taking out some symmetry the formula $$ {a \choose e_1,...,e_c} \sum\limits_{\substack{d_1,...,d_c \in \mathbb{N}_0 \\ d_1+...+d_c=b}} {b \choose d_1,...,d_c} \prod\limits_{i=1}^c d_i^{e_i} $$ seems to be what I was looking for. Here $0^0$ is treated as $1$.

$\endgroup$
1
  • $\begingroup$ Let $h^{\rightarrow}$ denote the image of $h$. Let $h^*(x)$ denote the preimage of $x$ under $h$. Then it's $$\sum_{g: [b] \to [c]} \prod_{x \in h^{\rightarrow}} |g^*(x)|^{|h^*(x)|}$$ where for most choices of $a,b,c,h$ we find that most terms of the sum are zero. $\endgroup$ Aug 23, 2022 at 9:55

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.