X, Y, and Z are sets with the cardinality of each set being l, m, and n, respectively with l < m < n. I'm trying to figure out how many possible 1-1 functions there are of the form of f∘g, with g: X → Y and f: Y → Z.
I know 1-1 (injective) essentially means that no two distinct elements in the domain map to the same element in the codomain.
For context this is for my discrete math class and we have most recently covered combinations and permutations. Any help is appreciated.
No harm in assuming, for now, that $X$ has the form $$ X = \{1, 2, \ldots, l\}. $$ To construct $g$, we need to pick from $Y$ a (yet unpicked) element. There are: $m$ choices for $g(1)$, $(n-1)$ choices for $g(2)$, etc.. Therefore, the number of ways to construct $f$ is: $$ m \, (m-1) \, \ldots \, (m - l + 1) = {m! \over (m-l)!}. $$
Each such $g$, therefore, identifies the following $l$ elements in $Y$: $$ g(1), \; g(2), \; \ldots \;, \; g(l). $$ Let's put then in a set: $$ Y_{g} = \{ g(1), \; g(2), \; \ldots \;, \; g(l) \}. $$ Thus, $Y_{g}$ is a subset of $Y$.
Next, how many choices of $f$ are there that are 1-to-1 on the subset $Y_{g}$? (We don't really care what $f$ does on the rest of $Y$.) To construct such an $f$, proceed in two phases: (i) count the ways to construct a 1-to-1 mapping from $Y_{g}$ to $Z$, then (ii) count the ways to construct an arbitrary mapping from $Y \setminus Y_{g}$ to $Z$.