The bimodule of sets, functions and permutations, and its quotients

1. Introduction to the bimodule of sets, functions, and permutations
2. Quotients: the “twelvefold way”; the twelvefold way diagram
3. An example: $\homst {[4]} \Set {\{a,b\}}$
4. Division (quotient) as (tensor product) with (the terminal bimodule)

This situation is worth careful consideration because, not only is it fundamental to combinatorics,
but also because it is a model for many situations more complex than merely the category of sets $\Set$.

---

1. Introduction to the bimodule of sets, functions, and permutations

Let $\source \setX$ and $\target \setY$ be arbitrary sets in the category of sets $\Set$.
Consider the groups of permutations $\source{\boxed{\symsX}}$ and $\target{\boxed{\symtY}}$ of $\source \setX$ and $\target \setY$ respectively,
and also the set $\boxed{\SetXY}$ of all $|\settY|^{|\setsX|}$ functions from $\source \setX$ to $\target \setY$.
There are two actions:
The group $\symsX$ of permutations of $\setX$ acts on $\SetXY$ by precomposition, while
the group $S_\setY$ of permutations of $\setY$ acts on it by postcomposition: \[\begin{array}{c} {\source{S_\setX}} \times \SetXY & \source\to & \SetXY\\ \langle \ssigma ,f\rangle & \source\mapsto & \ssigma f\end{array} \mkern6em \hbox{and} \mkern6em \begin{array}{c} \SetXY \times \target{S_\setY} & \target\to & \SetXY\\ \langle f,\ttau \rangle & \target\mapsto & f\ttau . \end{array}\] These actions are each associative and unital.
Also they commute with each other:
mixed pre-post actions are of the form

$\source{\setX \xrightarrow{\sigma} \setX} \xrightarrow{f} \target{\setY \xrightarrow{\tau} \setY}$

which yields

$\smash{\begin{array}{} && \setsX & {} \rlap{\mkern-1em \xrightarrow[\smash{\mkern8em}]{\displaystyle \functionf\ttau}} &&& \settY \\ & \source{ \llap{\symsX\ni\sigma} \nearrow } & \Vert & \searrow \rlap{\mkern-1em\functionf} & \Vert & \target{ \nearrow \rlap{\tau\in\symtY} } \\ \setsX & {}\rlap{\mkern-1em \xrightarrow[\displaystyle \ssigma\functionf]{\mkern8em}} &&& \settY \\ \end{array}}$

yielding

$\setsX \xrightarrow{\displaystyle \ssigma\functionf\ttau} \settY$

where $\source{\sigma\in S_\setX}$, $f\in \SetXY$, and $\target{\tau\in {S_\setY}}$.
Since (function composition is associative), (the two actions commute): $(\ssigma f)\ttau = \ssigma (f\ttau)$, yielding $\ssigma\functionf\ttau$.

So in addition to (the two one-sided, single actions)
there is (a double, simultaneous action from both sides),
which may be represented either
as a triple product, with (the action actors coming from each side simultaneously): \[\begin{array}{c} \source{S_\setX \times {}} \SetXY \target{{} \times S_\setY} & \to & \SetXY\\ \langle \ssigma, f, \ttau \rangle &\mapsto &\ssigma f \ttau\\ \end{array}\] or as a binary product, with (one factor itself being a product), and with (the joint, combined, again simultaneous, action coming from the right): \[\begin{array}{c} \SetXY \times (\source{S_\setX\op} \times \target{S_\setY}) &\to &\SetXY\\ \bigl\langle f, \langle \ssigma,\ttau \rangle \bigr\rangle &\mapsto & \ssigma f \ttau .\\ \end{array}\] (Associativity of the two-sided action) is (the vertical left hand equality) in \[\begin{array}{cl} \bigl\langle \source{\sigma'}, \langle \ssigma, f, \ttau \rangle, \target{\sigma'} \bigr\rangle & \xlongequal{\text{action}} \bigl\langle \source{\sigma'}, \ssigma f \ttau , \target{\sigma'} \bigr\rangle \xlongequal{\text{action}} \source{\sigma'}(\ssigma f \ttau) \target{\tau'}\\ \llap{\scriptstyle \text{action assoc }}\Vert\rlap{\text{ ???}}\\ \bigl\langle \source{\sigma'\sigma}, f, \target{\tau\tau'} \bigr\rangle & \xlongequal{\text{action}} \source{(\sigma'\sigma)} f \target{(\tau\tau')} .\end{array}\] (Equality of the right-hand sides) follows from (the associativity of function composition), and associativity of the action follows.

In the action where (the action actors both come from the right),
the ${}^{\rm op}$ is necessary (to make the action associative),
as shown by the following, where (the desired associativity of the action) is again (the vertical equality on the left).

$\smash{\begin{array}{} \setsX & \xrightarrow[\smash{\mkern3em}]{\displaystyle \functionf} & \settY \\ \source{\llap\ssigma \uparrow} && \target{\downarrow\rlap\ttau} \\ \setsX && \settY \\ \source{\llap{\ssigma'} \uparrow} && \target{\downarrow \rlap{\ttau'}} \\ \setsX && \settY \\ \end{array}}$

$$\begin{array}{cl} \bigl(f\langle\ssigma,\ttau \rangle\bigr)\langle\source{\sigma'},\target{\tau'}\rangle &\xlongequal{\text{action}} (\ssigma f \ttau)\langle\source{\sigma'},\target{\tau'}\rangle \xlongequal[\class{red}{*}]{\text{action}} \source{\sigma'}(\ssigma f \ttau)\target{\tau'}\\ \llap{\scriptstyle \text{action assoc }}\Vert\rlap{\text{ ???}}\\ f \bigl(\langle \ssigma,\ttau \rangle \langle\source{\sigma'},\target{\tau'}\rangle \bigr) & \xlongequal[\class{red}{*}]{\source{\text{composition in $\symsX\op$}}} f \langle \source{\sigma' \sigma}, \target{\tau \tau'} \rangle \xlongequal{\text{action}} \source{(\sigma'\sigma)} f \target{(\tau\tau')} \\ \end{array}$$ (The right-hand sides are again equal) by (the associativity of function composition in the diagram at right);
the desired associativity of (the action with right actors) follows.
Note that (the equalities where $\source{\sigma'}$ skips over $\ssigma$) are marked by (a $\class{red}{*}$).

$\begin{array}{} \functionf & \target{\xrightarrow[\mkern3em]{\displaystyle \ttau}} & \functionf\ttau \\ \llap\ssigma \big\downarrow && \llap\ssigma \big\downarrow \\ \big( \functiong = \ssigma\functionf \big) & \target{\xrightarrow[\displaystyle \ttau]{\mkern3em}} & \big( \functiong\ttau = (\ssigma\functionf)\ttau = \ssigma(\functionf\ttau) \big) \\ \end{array}$

Since the actions commute,
each action respects ((the equivalence relation) determined by (the other action)).
For example, if $f \source{{} \equiv_{S_\setX}} g$, then $\source{(\exists \sigma\in S_\setX)}(g= \ssigma f)$,
so, for all $\tau \in S_\setY$, and using the same $\sigma\in S_\setX$,
we have $g\ttau = (\ssigma f)\ttau = \ssigma(f\ttau)$, so $f\ttau \source{{} \equiv_{S_\setX}} g\ttau$.
The diagram, in the associated double groupoid, at right illustrates the situation.
And similarly if the roles of $\source \setX$ and $\target \setY$ are reversed.

Thus we have action maps $\source{\big(\symsX \backslash} \SetXY\source{\big)} \times \symtY \mathrel{\target{\xrightarrow{\text{action}}}} \source{\big(\symsX \backslash} \SetXY\source{\big)}$ and $\symsX \times \target{\big(} \SetXY \target{{} / \symtY \big)} \mathrel{\source{\xrightarrow{\text{action}}}} \target{\big(} \SetXY \target{{} / \symtY \big)}$,
and may form the two iterated quotients (quotients of quotients): $\boxed{ \source{( S_\setX \backslash } \SetXY \source) \target{/ S_\setY} }$ and $\boxed{ \source{S_\setX \backslash } \target( \SetXY \target{/ S_\setY )} }$ .

The five quotients of $\SetXY$ : two single, two iterated, one double

$\begin{array}{} \SetXY & {} \rlap{ \mkern-.5em\target{\xrightarrow[\mkern18em]{\displaystyle \functiont}} } &&& \mkern1em \SetXY \target{ / S_\setY} \\ &&&& \source{\big\downarrow} \\ \smash{\source{\llap\functions \Bigg\downarrow}} && \searrow \rlap\functionr && \source{S_\setX \backslash } \target( \SetXY \target{/ S_\setY )} \\ &&&& \wr\Vert \\ \source{S_\setX \backslash} \SetXY & {} \rlap{\mkern-.5em\target\longrightarrow} & \mkern1em \source{( S_\setX \backslash } \SetXY \source) \target{/ S_\setY} & \cong & \source{S_\setX \backslash} \SetXY \target{/ S_\setY} \\ \end{array}$

From either the two-sided action, $\langle \ssigma, f, \ttau \rangle \mapsto \ssigma f \ttau ,$
or the action of the product group ${\source{S_\setX}^{\text{op}}} \times {\target{S_\setY}}$, $\bigl\langle f, \langle \ssigma,\ttau \rangle \bigr\rangle \mapsto \ssigma f \ttau, $
on $\SetXY$
we have a third quotient, which we denote by $\boxed{\source{S_\setX \backslash} \SetXY \target{/ S_\setY}}$,
representing the result of dividing out simultaneously by the two actions,
with its quotient map $\SetXY \longrightarrow \source{S_\setX \backslash} \SetXY \target{/ S_\setY}$.
There are canonical bijections between all three quotient sets
which commute with their canonical quotient maps:

The surjections $\homst \setX \Surj \setY$ and injections $\homst \setX \Inj \setY$ form submodules of $\SetXY$,
with analogous diagrams concerning their quotients.

---

2. The “twelvefold way”

The double quotient square for $\SetXY$

$ \begin{array}{} \text{\{ ordered weak $\target \setY$-partitions of $\source \setX$ \}} && \text{\{ unordered weak $\target{|\setY|}$-partitions of $\source \setX$ \}} \\ {\wr\Vert} && \wr\Vert \\ \SetXY & {} \rlap{\mkern-7em\xrightarrow[\mkern16em]{\displaystyle \functiont}} & \mkern1.6em \SetXY \target/ \symtY \\ \smash{\source{\llap\functions \Bigg\downarrow}} & \searrow \rlap\functionr & \Bigg\downarrow \\ \symsX \source\backslash \SetXY \mkern2em & {} \rlap{\mkern-7em\xrightarrow{\mkern16em}} & \symsX \source\backslash \SetXY \target/ \symtY \\ \wr\Vert && \wr\Vert \\ \text{\{ ordered weak $\target{\setY}$-partitions of $\source{|\setX|}$ \}} && \text{\{ unordered weak $\target{|\setY|}$-partitions of $\source{|\setX|}$ \}} \\ \wr\Vert \\ \text{\{ weak $\source{|\setX|}$-multisets (values $\ge0$) on $\target \setY$ \}} \\ \end{array} $

The double quotient square for $\homst \setX \Surj \setY$

$ \begin{array}{} \text{\{ ordered strong $\target{\setY}$-partitions of $\source \setX$ \}} && \text{\{ unordered strong $\target{|\setY|}$-partitions of $\source \setX$ \}} \\ \wr\Vert && \wr\Vert \\ \homst \setX \Surj \setY & {} \rlap{\mkern-7em\xrightarrow[\mkern16em]{\displaystyle \functiont}} & \mkern1.6em \homst \setX \Surj \setY \target/ \symtY \\ \smash{\source{\llap\functions \Bigg\downarrow}} & \searrow \rlap\functionr & \Bigg\downarrow \\ \symsX \source\backslash \homst \setX \Surj \setY \mkern1.6em & {} \rlap{\mkern-7em\xrightarrow{\mkern16em}} & \symsX \source\backslash \homst \setX \Surj \setY \target/ \symtY \\ \wr\Vert && \wr\Vert \\ \text{\{ ordered strong $\target{\setY}$-partitions of $\source{|\setX|}$ \}} && \text{\{ unordered strong $\target{|\setY|}$-partitions of $\source{|\setX|}$ \}} \\ \wr\Vert \\ \text{\{ strong $\source{|\setX|}$-multisets (values $\ge1$) on $\target \setY$ \}} \\ \end{array} $

The double quotient square for $\homst \setX \Inj \setY$

$ \begin{array}{} \text{ \{ injections from $\source \setX$ to $\target \setY$ \}} && \text{$1$ or $\emptyset$ as $\source{|\setX|} \le {}$ or $\gt \target{|\setY|}$} \\ \Vert && \wr\Vert \\ \homst \setX \Inj \setY & {} \rlap{\mkern-10em\xrightarrow[\mkern16em]{\displaystyle \functiont}} & \mkern1.4em \homst \setX \Inj \setY / {\target{S_\setY}} \\ \smash{\source{\llap\functions \Bigg\downarrow}} & {} \rlap{\mkern-4em \searrow\rlap\functionr} & \Bigg\downarrow \\ {\source{S_\setX}} \backslash \homst \setX \Inj \setY \mkern1.6em & {} \rlap{\mkern-10em\xrightarrow{\mkern16em}} & {\source{S_\setX}} \backslash \homst \setX \Inj \setY / {\target{S_\setY}} \\ \wr\Vert && \wr\Vert \\ \text{\{ $\source{|\setX|}$-subsets ($\source{|\setX|}$-multisets with values $0$ or $1$) of $\target \setY$ \}} && \text{$1$ or $\emptyset$ as $\source{|\setX|} \le {}$ or $\gt \target{|\setY|}$ } \\ \end{array} $

Putting this all together, we have the three diagrams at the right for

• $\SetXY$ = all functions from $\source \setX$ to $\target \setY$,
• $\homst \setX \Surj \setY$ = surjections from $\source \setX$ to $\target \setY$, and
• $\homst \setX \Inj \setY$ = injections from $\source \setX$ to $\target \setY$,

showing the source, target, and double quotients
in each of the bimodules of functions, surjections, and injections.
These diagrams underlie
the “twelvefold way” of combinatorics.

Remark:
It is common (e.g., Stanley, EC, §1.9) in combinatorics to call
(the elements of the source set $\setX$) balls, and
(the elements of the target set $\setY$) boxes or urns.
Then (a function $\source\setX \to \target\setY$) is
(an assignment of balls to boxes, ball $\mapsto$ box),
and can be visualized physically,
as actually placing (physical balls) in (physical boxes or urns).

(The kernel-partition (or fibre) form)
used below to describe functions
amounts to showing, for each “box” its contents,
i.e., which “balls” are placed in it;
thus the $\{\elta,\eltb\}$-ordered partition $0,2,3 \mid 1$ means
balls $0,2,3$ go into box $\elta$,
while ball $1$ goes into box $\eltb$;
the word form for this function is $\elta\eltb\elta\elta$.
For pictorial examples, again see EC, §1.9.

---

The twelvefold way

$\bbox[navajowhite,10px,border:4px groove red]{ \begin{array}{} && & {} \mkern5em \rlap{\text{Injections}} &&&& {} \mkern7em \rlap{\text{All functions}} &&&& {} \mkern8em \rlap{\text{Surjections}} \\ && & \settY & & \target{|\setY|} & \mkern4em & \settY & & \target{|\setY|} & \mkern4em & \settY & & \target{|\setY|} \\ \setsX,\settY && & \boxed{\begin{array}{} \cattwo, \setsX, \settY\\ \homst \setX \Inj \setY\\ {\target{|\setY|}}^{\source{\underline{|\setX|}}} \\ \end{array} } && && \boxed{\begin{array}{} \text{weak}, \setsX, \settY\\ \SetXY\\ {\target{|\setY|}}^{\source{|\setX|}} = \displaystyle\target{\sum_{i=0}^{|\setY|}} \source{{|\setX| \brace \target i}}\target{i!}\target{{|\setY| \choose i}}\\ \end{array} } && && \boxed{\begin{array}{} \text{strong}, \setsX, \settY\\ \homst \setX \Surj \setY\\ \displaystyle{\source{|\setX|} \brace \target{|\setY|}}\target{|\setY|!}\\ \end{array} } \\ & \setsX & & & \target\searrow &&& & \target\searrow && {} \rlap{\mkern3em \source{\boxed{\boxed{\text{U = $\setsX$}}}}} & & \target\searrow \\ && \setsX,\target{|\setY|} & \raise2ex\hbox{$\smash{\source{\Bigg\downarrow}}$} && \llap{\lower6ex\hbox{$\boxed{\boxed{\text{L} = \cattwo}}\mkern.1em$}} \boxed{\begin{array}{} \cattwo, \setsX, \target{|\setY|} \\ \homst \setX \Inj \setY \target/ \symtY\\ [\source{|\setX|}\leq\target{|\setY|}] \\ \end{array} } && \raise2ex\hbox{$\smash{\source{\Bigg\downarrow}}$} && \llap{\lower6ex\hbox{$\boxed{\boxed{\text{C = weak}}} \mkern.2em$}} \boxed{\begin{array}{} \text{weak}, \setsX, \target{|\setY|} \\ \SetXY \target/ \symtY\\ \displaystyle\target{\sum_{i=0}^{|\setY|}} {\source{|\setX|} \brace \target i}\\ \end{array} } \rlap{\mkern.5em \target{\boxed{\boxed{\text{B = $\settY$}}}} } && \raise2ex\hbox{$\smash{\source{\Bigg\downarrow}}$} && \llap{\lower6ex\hbox{$\boxed{\boxed{\text{R = strong}}} \mkern.2em$}} \boxed{\begin{array}{} \text{strong}, \setsX, \target{|\setY|} \\ \homst \setX \Surj \setY \target/ \symtY\\ \displaystyle {\source{|\setX|} \brace \target{|\setY|}} \end{array} } \\ \source{|\setX|},\settY && & \boxed{\begin{array}{} \cattwo, \source{|\setX|}, \settY\\ \symsX \source\backslash \homst \setX \Inj \setY\\ \displaystyle {\target{|\setY|} \choose \source{|\setX|}}\\ \end{array} } && \lower3ex\hbox{$\smash{\source{\Bigg\downarrow}}$} && \boxed{\begin{array}{} \text{weak}, \source{|\setX|}, \settY\\ \symsX \source\backslash \SetXY\\ \displaystyle \bigg(\mkern-.35em {\target{{|\setY|}} \choose \source{|\setX|}} \mkern-.35em\bigg) = {\source{|\setX|}+\target{|\setY|}-1 \choose \target{|\setY|-1}} \end{array} } && \lower3ex\hbox{$\smash{\source{\Bigg\downarrow}}$} && \llap{\target{\boxed{\boxed{\text{F = } \target{|\setY|}}}} \; } \boxed{\begin{array}{} \text{strong}, \source{|\setX|}, \settY\\ \symsX \source\backslash \homst \setX \Surj \setY\\ \displaystyle \bigg(\mkern-.35em {\target{{|\setY|}} \choose \source{|\setX|} - \target{|\setY|}} \mkern-.35em\bigg) = \displaystyle {\source{|\setX|-1} \choose \target{|\setY|-1}} \end{array} } && \lower3ex\hbox{$\smash{\source{\Bigg\downarrow}}$} \\ & |\setsX| & & & \target\searrow &&& & \target\searrow && {} \rlap{\mkern3em \source{\boxed{\boxed{\text{D = } \source{|\setX|}}}}} & & \target\searrow \\ && \source{|\setX|},\target{|\setY|} & && \boxed{\begin{array}{} \cattwo, \source{|\setX|}, \target{|\setY|} \\ \symsX \source\backslash \homst \setX \Inj \setY \target/ \symtY\\ [\source{|\setX|}\leq\target{|\setY|}]\\ \end{array} } &&& & \boxed{\begin{array}{} \text{weak}, \source{|\setX|}, \target{|\setY|} \\ \symsX \source\backslash \SetXY \target/ \symtY\\ \displaystyle\target{\sum_{i=0}^{|\setY|}} \functionp_{\target i} (\source{|\setX|})\\ \end{array} } &&& & \boxed{\begin{array}{} \text{strong}, \source{|\setX|}, \target{|\setY|} \\ \symsX \source\backslash \homst \setX \Surj \setY \target/ \symtY\\ \functionp_{\target{|\setY|}} (\source{|\setX|})\\ \end{array} } & \\ \end{array} }$

The numerical formulae above are valid when $\setX$ and $\setY$ are finite nonempty sets, so that $\target{|\settY|-1\geq 0}$.
For slight variants which are valid even when $\target{|\settY|} = 0$ (i.e., when $\settY = \emptyset$), see the Wikipedia article.

The $\langle \source{|\setX|}, \settY \rangle$-cases: $\settY$-ordered partitions of the finite positive integer $\source{\numbern=|\setX|}$

Assume $\settY$ is linearly ordered with $\target{|\setY|=\numberk}$, a finite positive integer.

Strong $\numberk$-ordered partitions of $\numbern$, $1\leq\numberk\leq\numbern$.
Write ($\source\numbern$ dots in a row).
There are ($\source{\numbern-1}$ spaces) between (the $\source\numbern$ dots).
Choose $\target{\numberk-1}$ of (those $\source{\numbern-1}$ spaces), and place (a divider “$|$” (a “bar”)) in each of (the chosen $\target{\numberk-1}$ spaces).
The result is that (the $\source\numbern$ dots) are divided into ($\target\numberk$ non-empty groups).
There are ${\source{\numbern-1} \choose \target{\numberk-1}} = {\source{|\setX|-1} \choose \target{|\setY|-1}}$ ways of making (the choices described above).
For each ($\numberk$-ordered strong partition of $\numbern$) there is (a unique such choice) which (delivers the partition).
And note that any choice from the $\source{\numbern-1}$ inter-dot spaces yields a strong partition, thus there are $2^{\source{\numbern-1}}$ strong partitions in all.

Weak $\numberk$-ordered partitions of $\numbern$, arbitrary finite positive $\numberk$.
In this case, write ($\source\numbern+\target\numberk-1$ dots in a row).
Choose $\target{\numberk-1}$ of those dots, and replace (those chosen $\target{\numberk-1}$ dots) with (the divider symbol “$|$” (the “bar”)).
The result is again a division of (the $\source\numbern$ dots) into ($\target\numberk$ groups), but now (some of those groups may be empty).
There are ${\source\numbern+\target{\numberk-1} \choose \target{\numberk-1}} = {\source{|\setX|}+\target{|\setY|}-1 \choose \target{|\setY|-1}}$ ways of making (the choices described), yielding all possible (weak $\target\numberk$-ordered partitions of $\source\numbern$).

---

3. An example: $\homst {[4]} \Set {\{a,b\}}$

The double quotient square for $\homst {(\setX=[4])} \Set {(\setY=\{a,b\})}$

$ \begin{array}{} \text{\{ ordered weak $\target{\{\elta,\eltb\}}$-partitions of $\source {[4]}$ \}} && \text{\{ unordered weak $\target 2$-partitions of $\source {[4]}$ \}} \\ \llap{(\#=16)\;} {\wr\Vert} && \wr\Vert \rlap{\;(\#=8)} \\ \mkern.5em \homst {[4]} \Set {\{a,b\}} & {} \rlap{\mkern-6em\xrightarrow{\mkern14em}} & \mkern3em \homst {[4]} \Set {\{a,b\}} / \target{S_{\{a,b\}}} \\ \Bigg\downarrow && \Bigg\downarrow \\ \mkern.5em {\source{S_{[4]}}} \backslash \homst {[4]} \Set {\{a,b\}} \mkern2em & {} \rlap{\mkern-6em\xrightarrow{\mkern14em}} & \mkern1.5em {\source {S_{[4]}}} \source\backslash \homst {[4]} \Set {\{a,b\}} \target/ {\target{S_{\{a,b\}}}} \\ \llap{(\#=5)\;} {\wr\Vert} && \wr\Vert \rlap{\;(\#=3)} \\ \text{\{ ordered weak $\target{\{\elta,\eltb\}}$-partitions of $\source 4$ \}} && \text{\{ unordered weak $\target 2$-partitions of $\source 4$ \}} \\ \Vert && \Vert \\ \source{\{4+0, 3+1, 2+2, 1+3, 0+4 \}} && \source{\{4+0, 3+1, 2+2\}} \\ \wr\Vert \\ \text{\{ weak $\source 4$-multisets on $\target {\{a,b\}}$ \}} \\ \Vert \\ \{\target a^4 \target b^0, \target a^3 \target b^1, \target a^2 \target b^2, \target a^1 \target b^3, \target a^0 \target b^4\} \\ \end{array} $

There is a certain abstractness about
talking about arbitrary sets $\source \setX$ and $\target \setY$.
Let's see what all this means in a case where we can easily
both represent and count
{ the elements of the function sets $\SetXY$ and $\homst \setX \Surj \setY$ }.
In particular,
we take ($\source{\setX = [4] \equiv \{0,1,2,3\}}$) and ($\target{\setY = \{a,b\}}$),
so functions $\functionf : \source{[4]} \to \target{\{\elta,\eltb\}}$
can be represented as
four-letter words in the alphabet $\target{\{\elta,\eltb\}}$, e.g. $\target{\elta\eltb\elta\elta}$;
then $|\SetXY| = \target{|\setY|}^{\source{|\setX|}} = {\target 2}^{\source 4} = 16$
and $|\homst \setX \Surj \setY| = 14$ (all but the two constant functions).
Then (the double quotient square for $\homst {(\setX=[4])} \Set {(\setY=\{a,b\})}$)
becomes the diagram at right.
The contents of the various sets in the diagram
are described in detail below.

The source quotient: ${\source{S_{[4]}}} \backslash \homst {[4]} \Set {\{a,b\}} \cong \catI \tensor_{\source{S_{[4]}}} \homst {[4]} \Set {\{a,b\}}$

$\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{lcccccccc} &&& \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} } \\ && \displaystyle { \source{0,1,2 \mid 3} \brack \target{aaab} } & \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & \displaystyle { \source{0 \mid 1,2,3} \brack \target{abbb} }\\ && \displaystyle { \source{0,1,3 \mid 2} \brack \target{aaba} } & \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & \displaystyle { \source{1 \mid 0,2,3} \brack \target{babb} }\\ & \displaystyle { \source{0,1,2,3 \mid {}} \brack \target{aaaa} } && \class{red}\bullet && \displaystyle { \source{{} \mid 0,1,2,3} \brack \target{bbbb} }\\ && \displaystyle { \source{0,2,3 \mid 1} \brack \target{abaa} } & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} } & \displaystyle { \source{2 \mid 0,1,3} \brack \target{bbab} }\\ && \displaystyle { \source{1,2,3 \mid 0} \brack \target{baaa} } & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} } & \displaystyle { \source{3 \mid 0,1,2} \brack \target{bbba} }\\ &&& \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\[2ex] \hline \source{\text{size of $S_{[4]}$-orbit}} & \source 1 & \source 4 & \source 6 & \source 4 & \source 1\\ \source{\text{size of $S_{[4]}$-stabilizer}} & \source{4!0!} & \source{3!1!} & \source{2!2!} & \source{1!3!} & \source{0!4!}\\ \source{\text{template (set form)}} & \source{\{\cdotp\cdotp\cdotp\cdotp\} \{\}} & \source{\{\cdotp\cdotp\cdotp\} \{\cdotp\}} & \source{\{\cdotp\cdotp\} \{\cdotp\cdotp\}} & \source{\{\cdotp\} \{\cdotp\cdotp\cdotp\}} & \source{\{\} \{\cdotp\cdotp\cdotp\cdotp\}} \\ \source{\text{template (divider form)}} & \source{\cdotp\cdotp\cdotp\cdotp \mid {}} & \source{\cdotp\cdotp\cdotp \mid \cdotp} & \source{\cdotp\cdotp \mid \cdotp\cdotp} & \source{\cdotp \mid \cdotp\cdotp\cdotp} & \source{{} \mid \cdotp\cdotp\cdotp\cdotp} \\ \text{partition (binary form)} & \source{0000}\target1 & \source{000}\target1\source0 & \source{00}\target1\source{00} & \source0\target1\source{000} & \target1\source{0000}\\ \text{ordered weak $\target2$-partitions of }\source4 & \source4 \target+ \source0 & \source3 \target+ \source1 & \source2 \target+ \source2 & \source1 \target+ \source3 & \source0 \target+ \source4\\ \text{weak $\source 4$-multisets on }\target{\{a,b\}} & \target a^{\source 4}\source b^{\target 0} & \target a^{\source 3}\target b^{\source 1} & \target a^{\source 2}\target b^{\source 2} & \target a^{\source 1}\target b^{\source 3} & \target a^{\source 0}\target b^{\source 4}\\[2ex] \target{\text{size of BLOCK $S_{\{a,b\}}$-stabilizer}} & \target 1 & \target 1 & \target 2 & \target 1 & \target 1 \\ \target{\text{size of BLOCK $S_{\{a,b\}}$-orbit}} & \target 2 & \target 2 & \target 1 & \target 2 & \target 2 \\ \end{array}}$

Dividing out by
(permutations of the source $\setX = \source{[4]}$),
$\SetXY \longrightarrow {\source{S_\setX\backslash{}}} \SetXY$,
i.e., indistinguishable source elements or balls,
can be visualized via the figure at right,
which shows all ${\target 2}^{\source 4}=16$ functions
from $\source{[4]=\{0,1,2,3\}}$ to $\target{\{a,b\}}$,
i.e., the elements of $\homst {[4]} \Set {\{a,b\}} = {\target{\{a,b\}}}^{\source{[4]}}$.
It shows each function
first in ordered kernel-partition (or fibre) form
($\target a$ component of the partition (or fibre)
to the left of the divider “$\mid$” (the “bar”),
$\target b$ component on the right),
then on the next line
the representation of the function
as a four letter word in the alphabet $\{a,b\}$.
(The columns) are precisely
{the orbits of $\homst {[4]} \Set {\{a,b\}}$ under
the left (pre-) $\source{S_{[4]}}$-action},
thus are precisely
{the elements of
the left quotient set $\source{S_{[4]} \backslash} \homst {[4]}\Set {\{a,b\}}$}.
Thus the $\symsX$-quotient map
($\SetXY \longrightarrow {\source{S_\setX\backslash{}}} \SetXY$)
takes (each function) into
(its column in the table).
(The bottom rows of the table) show
some information about each column/$\symsX$-orbit,
namely, its size and
the size of the stabilizers of its elements,
and some alternative ways of describing
the column/$\symsX$-orbit, i.e.,
some total invariants of the column/$\symsX$-orbit:
(the ordered weak $\target{\{\elta,\eltb\}}$-partitions of $\source 4$) and (the weak $\source 4$-multisets on $\target{\{a,b\}}$).

For surjections, simply omit the two outer columns.

Now consider (the action of $\symtY = \target{S_{\{a,b\}}}$) on both (the total space $\homst {[4]} \Set {\{a,b\}}$) and (its source quotient ${\source{S_{[4]}\backslash{}}} \homst {[4]} \Set {\{a,b\}}$).
(The columns of the table) have been so ordered that (the $\source{S_{\{a,b\}}}$-action) on (the total space $\homst {[4]} \Set {\{a,b\}}$)
amounts to reflection in (the dot $\class{red}\bullet$ which is at the center of the table).
The key point is that (reflection in the center dot $\class{red}\bullet$) (respects the columns), i.e., it takes (functions\words in the same column) into (functions\words in the same column).
Thus (the central reflection on the 16 points) passes to (a reflection on the five columns), namely, (reflection in (the vertical axis through the center of the table)).
That reflection (swaps the four outer columns), but (fixes the center column).
Thus (the resulting iterated quotient $\source{( S_{[4]} \backslash } \homst {[4]} \Set {\{a,b\}} \source) / \target{S_{\{a,b\}}}$) has three elements ($\symtY$-orbits of $\symsX$-orbits):
{ the pair of outer columns, the pair of next-to-outer columns, and the center column }.

---

The target quotient:
$\target( \homst {[4]} \Set {\{a,b\}} \target{/ S_{\{a,b\}} )} \cong \homst {[4]} \Set {\{a,b\}} \tensor_{\target{S_{\{a,b\}}}} \catI$

$$\begin{array}{cc} \displaystyle { \source{0,1,2,3 \mid {} } \brack \target{aaaa} } \displaystyle { \source{ {} \mid 0,1,2,3} \brack \target{bbbb} } \end{array}$$		$\{\,4+0,0+4\,\}$	$\{\,4,0\,\}$
$$\begin{array}{cc} \displaystyle { \source{0,1,2 \mid 3} \brack \target{aaab} } & \displaystyle { \source{3 \mid 0,1,2} \brack \target{bbba} }\\ \displaystyle { \source{0,1,3 \mid 2} \brack \target{aaba} } & \displaystyle { \source{2 \mid 0,1,3} \brack \target{bbab} }\\ \displaystyle { \source{0,2,3 \mid 1} \brack \target{abaa} } & \displaystyle { \source{1 \mid 0,2,3} \brack \target{babb} }\\ \displaystyle { \source{1,2,3 \mid 0} \brack \target{baaa} } & \displaystyle { \source{0 \mid 1,2,3} \brack \target{abbb} }\\ \end{array}$$		$\{\,3+1,1+3\,\}$	$\{\,3,1\,\}$
$$\begin{array}{cc} \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} } & \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\ \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} }\\ \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} }\\ \end{array}$$		$\{\,2+2\,\}$	$\{\,2,2\,\}$

For dividing out by (permutations of the target $\target{\setY = \{a,b\}}$),
$\SetXY \mathrel{\target\longrightarrow} \SetXY {\target{{}/S_\setY}}$, i.e., indistinguishable target elements or boxes,
we have a similar figure, at right.
Here (the $\target{S_\setY}$-orbits) are arranged in rows;
thus ((the $\target{S_{\setY}}$-quotient map) onto (the $\target{S_{\setY}}$-orbits)) is now simply (taking the row).

(The source permutation group $\source{S_\setX = S_{[4]}}$) acts, not only on (the elements of $\SetXY$),
but also on (their $\symtY$-orbits): $\symsX \times \target{\big(} \SetXY \target{{} / \symtY \big)} \mathrel{\source\longrightarrow} \target{\big(} \SetXY \target{{} / \symtY \big)}$.
{The orbits of $\SetXY \target/ \symtY $ under that ($\source{\symsX = S_{[4]}}$)-action}
are {the three blocks of rows separated by horizontal rules} —
these are the three elements of the set of $\symsX$-orbits of $\symtY$-orbits, $\source{S_\setX \backslash} \target{\big(} \SetXY \target{{} / S_\setY \big)}$.
They correspond to the three unordered weak $\target 2$-partitions of $\source 4$: $\source{4+0, 3+1, 2+2}$.

The key point again is that
there are bijections between (the iterated quotients) and (the double quotient)
i.e., between {blocks of columns}, {blocks of rows}, and (the orbits of the two-sided action),
rendering commutative the five-quotient diagram $$\begin{array}{} \smash{\SetXY} & {} \rlap{ \mkern-.5em \smash{\target{\xrightarrow[\mkern18em]{\displaystyle \functiont}} } } &&& \mkern1em \SetXY \target{ / S_\setY} \\ &&&& \source{\big\downarrow} \\ \smash{\source{\llap{\functions} \Bigg\downarrow}} && \searrow \rlap{\raise1ex\functionr} && \smash{ \source{S_\setX \backslash } \target( \SetXY \target{/ S_\setY )} } \\ &&&& \wr\Vert \\ \source{S_\setX \backslash} \SetXY & {} \rlap{\mkern-.5em\target\longrightarrow} & \mkern1em \source{( S_\setX \backslash } \SetXY \source) \target{/ S_\setY} & \cong & \source{S_\setX \backslash} \SetXY \target{/ S_\setY} & , \\ \end{array}$$ namely the evident bijections between (the three-element sets) listed on (three rows below).
Note how (the double quotient), in the middle row, flattens (the iterated quotients),
replacing (orbits of orbits) with just (orbits).

$\mkern-3em \begin{array}{cccccccccl} {} \rlap{\mkern19em \text{The quotients as sets of sets (of sets), and some invariants of those sets}} \\ && \Big\{ & \source{\big\{0123\mid{}\big\}}& , & \source{\big\{\mkern.5em 012\mid3 \mkern1em,\mkern1em 013\mid2 \mkern1em,\mkern1em 023\mid1 \mkern1em,\mkern1em 123\mid0\mkern.5em\big\}} & , & \source{\big\{\mkern1em 01\mid23 \mkern1em,\mkern1em 02\mid13 \mkern1em,\mkern1em 03\mid12 \mkern1em\big\}} & \Big\} & \text{unordered parts. of $[4]$} \\ \source{S_\setX \backslash } \target( \SetXY \target{/ S_\setY )}& = & \Big\{ & \big\{ \{\elta^4,\eltb^4\} \big\} & , & \big\{ \{\elta^3\eltb,\eltb^3\elta\}, \{\elta^2\eltb\elta,\eltb^2\elta\eltb\}, \{\elta\eltb\elta^2,\eltb\elta\eltb^2\}, \{\eltb\elta^3,\elta\eltb^3\} \big\} & , & \big\{ \{\elta^2\eltb^2,\eltb^2\elta^2\}, \{\elta\eltb\elta\eltb,\eltb\elta\eltb\elta\}, \{\elta\eltb^2\elta, \eltb\elta^2\eltb\} \big\} & \Big\} & \text{$\symsX$-orbits of $\symtY$-orbits} \\ \source{S_\setX \backslash} \SetXY \target{/ S_\setY} & = & \Big\{ & \big\{ \elta^4,\eltb^4 \big\} & , & \big\{ \elta^3\eltb, \elta^2\eltb\elta, \elta\eltb\elta^2, \eltb\elta^3, \elta\eltb^3, \eltb\elta\eltb^2, \eltb^2\elta\eltb, \eltb^3\elta \big\} & , & \big\{ \elta^2\eltb^2, \elta\eltb\elta\eltb, \elta\eltb^2\elta, \eltb\elta^2\eltb, \eltb\elta\eltb\elta, \eltb^2\elta^2 \big\} & \Big\} & \text{$\source{\symsX\op} \rightadj\times \symtY$-orbits} \\ \source{( S_\setX \backslash } \SetXY \source) \target{/ S_\setY} & = & \Big\{ & \big\{ \{\elta^4\},\{\eltb^4\} \big\} & , & \big\{ \{\elta^3\eltb, \elta^2\eltb\elta, \elta\eltb\elta^2, \eltb\elta^3\}, \{\elta\eltb^3, \eltb\elta\eltb^2, \eltb^2\elta\eltb, \eltb^3\elta\} \big\} & , & \big\{ \{\elta^2\eltb^2, \elta\eltb\elta\eltb, \elta\eltb^2\elta, \eltb\elta^2\eltb, \eltb\elta\eltb\elta, \eltb^2\elta^2\} \big\} & \Big\} & \text{$\symtY$-orbits of $\symsX$-orbits} \\ && \Big\{ & \source{\big\{4+0,0+4\big\}} & , & \source{\big\{\mkern3em 3+1 \mkern3em , \mkern3em 1+3 \mkern3em\big\}} & , & \source{\big\{\mkern4em 2+2 \mkern4em\big\}} & \Big\} & \text{ordered parts. of $4$} \\ && \Big\{ & \source{4+0} & , & \source{3+1} & , & \source{2+2} & \Big\} & \text{unordered parts. of $4$} \\ \end{array}$

For further information, see the post “The fiber product at work (in elementary combinatorics)”.

---

References

EC, Stanley, Richard P., Enumerative Combinatorics I, 1986/2011
W, Wikipedia, “Twelvefold way”
FPAW, “The fiber product at work (in elementary combinatorics)”, 2019
DG12W, “Double groupoids and the twelvefold way”, 2016
PF, “The parts of a function”, 2016
CFP, “Classifying functions by their parts”, 2016
QKA, “The quotient-kernel adjunction”, 2016
KQFC, “Kernels, quotients, and function composition”, 2019

Double groupoids and the twelvefold way

Fact: The $2^4 = 16$ functions from $\source{[4]=\{0,1,2,3\}}$ to $\target{\{a,b\}}$,

• when quotiented by the permutation group of the source, $S_4$,
  divide into five equivalence classes;
• when quotiented by the permutation group of the target, $S_{\{a,b\}}$,
  divide into eight equivalence classes;
• when quotiented by both,
  divide into three equivalence classes.

Challenge: Find a way to visualize those classes and the relations between them.

Solution: Apply the following construction of a double groupoid to $\homst {[4]} \Set {\{a,b\}}$. (The result.)

---

The general construction

Let $\source X$ and $\target Y$ be arbitrary sets in the category of sets, $\Set$.
Let $\boxed{\source{S_X}}$ and $\boxed{\target{S_Y}}$ be their respective groups of permutations.
Form a double groupoid as follows.

• Its 0-cells are all the functions from $\source X$ to $\target Y$,
  namely, the elements of the function set $\boxed{\homst X \Set Y}$.
• There is a vertical 1-cell for each $\boxed{\langle \source\sigma, f \rangle \in \symsX \times \homst X \Set Y = V}$.
• There is a horizontal 1-cell for each $\boxed{\langle f, \target\tau \rangle \in \homst X \Set Y \times \symtY = H}$.
• $\begin{array}{c} f & \target{\xrightarrow{\displaystyle \text{t-}\tau}} & f\target\tau\\ \source{\llap{\text{s-}\sigma} \Big\downarrow} & \langle \source\sigma, f, \target\tau \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma}}\\ \source\sigma f & \target{\xrightarrow[\displaystyle \text{t-}\tau]{}} & \source\sigma f \target\tau \end{array}$
  The sources and targets of the 1-cells are as shown in the square for 2-cells.
• There is a 2-cell for each triple $\boxed{\langle \source\sigma, f, \target\tau \rangle \in \source{S_X} \times \homst X \Set Y \times \target{S_Y}}$,
  having (horizontal and vertical source and target) as in (the square at right):
• Vertical and horizontal composition of 1-cells is obvious,
  while vertical and horizontal composition of 2-cells is by pasting.
• Vertical and horizontal associativity and identity are obvious.
• $\begin{array}{c} f & \target{\xrightarrow{\displaystyle \text{t-}\tau}} & f\target\tau & \target{\xrightarrow{\displaystyle \text{t-}\tau'}} & f\target{\tau\tau'}\\ \source{\llap{\text{s-}\sigma} \Big\downarrow} & \langle \source\sigma, \target\tau \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma}} & \langle \source\sigma, \target{\tau'} \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma}}\\ \source\sigma f & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau}}} & \source\sigma f \target\tau & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau'}}} & \source\sigma f \target{\tau\tau'}\\ \source{\llap{\text{s-}\sigma'} \Big\downarrow} & \langle \source{\sigma'}, \target\tau \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma'}} & \langle \source{\sigma'}, \target{\tau'} \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma'}}\\ \source{\sigma'\sigma} f & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau}}} & \source{\sigma'\sigma} f \target\tau & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau'}}} & \source{\sigma'\sigma} f \target{\tau\tau'}\\ \end{array} = \qquad \begin{array}{c} f & \target{\xrightarrow{\displaystyle \text{t-}\tau\tau'}} & f\target{\tau\tau'}\\ \source{\llap{\text{s-}\sigma\sigma'} \Big\downarrow} & \langle \source{\sigma\sigma'}, \target{\tau\tau'} \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma\sigma'}}\\ \source{\sigma'\sigma} f & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau\tau'}}} & \source{\sigma'\sigma} f \target{\tau\tau'}\\ \end{array}$
  Finally,
  the compatibility of horizontal with vertical composition
  is shown by the square at right, of four compatible squares.
  Whether
  you first horizontally compose the top and bottom halves,
  then vertically compose the result,
  or first vertically compose the right and left halves,
  then horizontally compose the result,
  you get the same resulting square as shown.

There are then four groupoids:

• A discrete one, consisting only of the 0-cells (one for each function).
• The source groupoid, consisting of the 0-cells and the $\text{s}$-labeled 1-cells,
  specifying how permutations of the source act on functions.
• The target groupoid, consisting of the 0-cells and the $\text{t}$-labeled 1-cells,
  specifying how permutations of the target act on functions.
• The source-target double groupoid, consisting of all the 0-cells, 1-cells, and 2-cells.
  The 2-cells specify how simultaneous permutations of the source and target
  act on functions.

The discrete one is a subgroupoid of all the other groupoids;
the source and target groupoids are subgroupoids of the source-target double groupoid.

The connected components of these four groupoids
are the four parts of the “twelvefold way” for arbitrary functions.
The other eight parts of the “twelvefold way”
are the connected components of
the groupoids defined for surjective and injective functions.

The permutation groups act on surjective and injective functions
just as they act on arbitrary functions,
and we can repeat the above construction on those classes of functions.

---

The specific case of $\homst {[4]} \Set {\{a,b\}}$

Apply the above construction to $\homst {[4]} \Set {\{a,b\}}$.

(The connected components of the double groupoid) are in (the three cells of the figure below).
The component labeled $\{4,0\}$ contains two functions,
the component labeled $\{3,1\}$ contains eight functions,
the component labeled $\{2,2\}$ contains six functions
(each appearing twice in the graphic, connected by $=$ signs,
due to the fact that, for (this component of (the source-target groupoid)),
(target-permutations) remain in (the same connected component of (the source groupoid))).
Note that in (this source-target component) prefixes have been added to the permutations,
so that (in the event that there is overlap between the elements of the source and target)
it can be determined unambiguously whether (a given permutation) is (of the source or target).

[The connected components of the groupoid using (permutations of the source)] are (the columns).
There are five such components (columns), with column headers
$$\langle 4, 0 \rangle, \quad \langle 0, 4 \rangle, \quad \langle 3, 1 \rangle, \quad \langle 1, 3 \rangle,\quad \hbox{and}\quad \langle 2, 2 \rangle .$$

The connected components of the groupoid using (permutations of the target) are connected by (arrows labeled $\target(a,b)$):
five horizontal arrows in the first two cells and
three of the vertical arrows in the third cell,
thus (eight components) of (the target groupoid).
(Because (target permutations) stabilize (this connected component of (the source groupoid)).)

$\{4,0\}$	$\{3,1\}$	$\{2,2\}$
\[\begin{array}{c} \source{\langle 4, 0 \rangle} & \target{\xrightarrow{\text{t-}(a,b)}} & \source{\langle 0, 4 \rangle} \\[8ex] \hline \boxed{\displaystyle { \source{0,1,2,3 \mid {}} \brack \target{aaaa} }} & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{{} \mid 0,1,2,3} \brack \target{bbbb} }\\ \end{array}\]	\[\begin{array}{c} \source{\langle 3, 1 \rangle} & \target{\xrightarrow{\text{t-}(a,b)}} & \source{\langle 1, 3 \rangle} \\[8ex] \hline \boxed{\displaystyle { \source{0,1,2 \mid 3} \brack \target{aaab} }} & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{3 \mid 0,1,2} \brack \target{bbba} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,1,3 \mid 2} \brack \target{aaba} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{2 \mid 0,1,3} \brack \target{bbab} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,2,3 \mid 1} \brack \target{abaa} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{1 \mid 0,2,3} \brack \target{babb} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{1,2,3 \mid 0} \brack \target{baaa} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0 \mid 1,2,3} \brack \target{abbb} }\\ \end{array}\]	\[\begin{array}{c} & \source{\langle 2, 2 \rangle} &\\[8ex] \hline \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} } & = & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)}\Big\uparrow} && \target{\Big\uparrow\rlap{\scriptstyle \text{t-}(a,b)}}\\ \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & = & \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} }\\ \source{\llap{\scriptstyle \text{s-}(1,2)}\Big\uparrow}\\ \boxed{\displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }} & = & \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)^2}\Big\downarrow\rlap{\scriptstyle \text{s-}(0,2)(1,3)}} && \target{\Big\downarrow\rlap{\scriptstyle \text{t-}(a,b)}}\\ \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} } & = & \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)}\Big\downarrow}\\ \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} } & = & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)^2}\Big\downarrow\rlap{\scriptstyle \text{s-}(0,2)(1,3)}} && \target{\Big\downarrow\rlap{\scriptstyle \text{t-}(a,b)}}\\ \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & = & \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} }\\ \end{array}\]

Answering the challenge posed at the beginning, we see that
{the $\target2^{\source4}=16$ functions from $\source{[4]}$ to $\target{\{a,b\}}$} decompose unambiguously into
(the three connected components) of (the source-target groupoid) associated with (the unordered weak $\target 2$-partitions of $\source 4$) $$\{4,0\}, \{3,1\}, \{2,2\} .$$ Each of these three components may be decomposed either into
components of (the source groupoid) or (the target groupoid).
For example,
the eight elements of the $\{3,1\}$ component of the source-target groupoid
can be divided either into

• two ((four-element components) of (the source groupoid)) associated with the two $\{3,1\}$-multisets $a^3b^1$ and $a^1b^3$, or
• four ((two-element components) of (the target groupoid)) associated with the four $\{3,1\}$-partitions of $\{0,1,2,3\}$ $$0,1,2\mid 3,\quad 0,1,3\mid 2,\quad 0,2,3\mid 1, \quad 1,2,3\mid 0 .$$

---

$\{2,2\}$

$\{2,2\}$

\[\begin{array}{c} & \source{\langle 2, 2 \rangle} & \\[8ex] \hline \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\uparrow} && \source{\Big\uparrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} }\\ \source{\llap{\scriptstyle\text{s-}(1,2)}\Big\uparrow} && \source{\Big\uparrow\rlap{\scriptstyle\text{s-}(1,2)}}\\ \boxed{\displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }} & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} }\\ \end{array}\]

\[\begin{array}{c} && \source{\langle 2, 2 \rangle} && \\[8ex] \hline && \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} } & = & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} }\\ && \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\uparrow} && \target{\Big\uparrow\rlap{\scriptstyle\text{t-}(a,b)}}\\ && \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & = & \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} }\\ && \source{\llap{\scriptstyle\text{s-}(1,2)}\Big\uparrow}\\ && \boxed{\displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }} & = & \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }\\ && \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow}\\ \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & = & \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } && \target{\Bigg\downarrow\rlap{\scriptstyle\text{t-}(a,b)}}\\ && \source{\llap{\scriptstyle(\text{s-}0,1,2,3)}\Big\downarrow}\\ \target{\llap{\scriptstyle\text{t-}(a,b)}\Bigg\downarrow} && \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} } & = & \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\ && \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow}\\ \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} } & = & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} }\\ \end{array}\]

The table at right shows
two ways to depict the $\{2,2\}$-component
with the source and target 1-cells orthogonal to each other,
so that
permutations of the source are shown vertically and
permutations of the target are shown horizontally.
To make this possible, each function appears twice.

---

The reader may question why it is necessary to label the 1-cells with $\source{\text{s-}}$ and $\target{\text{t-}}$
when the groupoid to which the 1-cell belongs is, in the cases so far considered,
already indicated by the permutation,
and also by color and orientation (horizontal or vertical) of the 1-cell.

As to the color, some readers may be color-blind; also, colors generally don't appear in prints.
As to the permutations being distinguishable, that will not always be the case.

Consider the case where $\source X = \target Y$.
In such a case all the permutations are permutations of the same set,
thus it is necessary to have some way of distinguishing
whether they are intended to act by precomposition or postcomposition.
The $\source{\text{s-}}$ and $\target{\text{t-}}$ prefixes do just that.

$\begin{array}{c} \functionf & = & \displaystyle { \source{0,2 \mid 1,3} \brack \target{0101} } & \target{\xrightarrow{\displaystyle\text{t-}(0,1)}} & \displaystyle { \source{1,3 \mid 0,2} \brack \target{1010} } & = & \functiong\\ && \source{\llap{\text{s-}(0,1,2,3)} \Bigg\downarrow} && \source{\Bigg\downarrow \rlap{\text{s-}(0,1,2,3)}}\\ \functiong & = & \displaystyle { \source{1,3 \mid 0,2} \brack \target{1010} } & \target{\xrightarrow{\displaystyle\text{t-}(0,1)}} & \displaystyle { \source{0,2 \mid 1,3} \brack \target{0101} } & = & \functionf\\ \end{array}$

As to the possibility of using horizontal versus vertical orientation
to distinguish between a permutation acting on the source or target,
consider the double groupoid associated to $\source X = \target Y = \{0,1,2,3\}$,
i.e., $S_{\{0,1,2,3\}}$ acting on both sides of $\homst {\{0,1,2,3\}} \Set {\{0,1,2,3\}}$,
and in that double groupoid, consider the 2-cell at right.
Note that (both of the intermediate 0-cells) are the same, namely (the function $\target 1010$).
Thus (both the top and left 1-cells) have (exactly the same source and target);
we may say that (they are parallel 1-cells) in (the double groupoid),
and depict (the commonality of their sources and targets) through the diagram

$\displaystyle { \source{0,2 \mid 1,3} \brack \target{0101} } \mathrel{ \source{\xrightarrow[\smash{\mkern7em}]{\displaystyle\text{s-}(0,1,2,3)}} \atop \target{\xrightarrow[\displaystyle\text{t-}(0,1)]{\smash{\mkern7em}}} } \displaystyle { \source{1,3 \mid 0,2} \brack \target{1010} } $

where the prefixes are necessary
to specify whether permutations are acting via pre- or post- composition

$\begin{array}{} \source{[4]} & \xrightarrow{\displaystyle 0101} & \target{[4]} \\ \source{\llap{(0,1,2,3)}\Big\downarrow} & \searrow \rlap{\mkern-2em 1010} & \target{\Bigg\downarrow\rlap{(0,1)}} \\ \source{[4]} & \xrightarrow[\displaystyle 0101]{} & \target{[4]} \\ \end{array}$

Note that this situation corresponds to an automorphism of $\functionf = 0101$ in the arrow category of $\Set$:

---

References

“The bimodule of sets, functions and permutations, and its quotients”, 2019

---

The above post was initially created on 2016-06-27.
The construction of the double groupoid is certainly not original,
it is just an adaption of the standard construction of a double category from a mere category,
restricted to functions from a set $X$ to a set $Y$ and permutations of those two sets.

Modules in combinatorics

Consider (the totally disconnected groupoid $\boxed\Perm$ of permutations of sets),
which (considered as a category) is a subcategory of (the category $\Set$): $\quad \Perm \subset \Set$.
Recall that any category, say $\calC$, is a left-right bimodule over itself, via its hom bifunctor: $\smash{ \quad \calC\op \times \calC \xrightarrow{\textstyle \hom - \calC -} \Set }\;$.
In particular (the category $\Set$) is a left-right bimodule over itself: $(\functionf,\functiong,\functionh) \mapsto \functionf\functiong\functionh$.
By restriction of scalars, $\Set$ is a bimodule over (its groupoid subcategory $\Perm$): $\smash{ \quad \Perm\op\times\Perm \xrightarrow{\textstyle \hom - \Set -} \Set \; : \; (\sigma, \tau) \mapsto ( \hom \sigma \Set \tau \; : \; \functionf \mapsto \sigma \functionf \tau ) } \;$.
(Analogy: In algebra, any ring is a left-right bimodule (Wikipedia, nLab) over each of its subrings.)

Take the left, right, and left-right quotients of $\Set$ by $\Perm$.
This yields [(the first four parts) of (the "twelvefold way")] .

Now consider the subcategories of surjections, $\boxed\Surj$, and, of injections, $\boxed\Inj$, of the category $\Set$.
Each is closed under both left and right actions of $\Perm$, thus is a sub-$\Perm$-bimodule.
Applying the same (quotient by $\Perm$) constructions to (those two submodules) gives [(the other eight parts) of (the twelvefold way)].

We can present the twelvefold way as a table:

The Twelvefold Way

Module, with scalars	Module, without scalars	Left Quotient indistinguishable balls	Right Quotient indistinguishable boxes	Left-Right Quotient indistinguishable balls and boxes
$(\Perm, \Set)$	$\Set$	$\Perm\backslash\Set$	$\Set/\Perm$	$\Perm\backslash\Set/\Perm$
$(\Perm, \Surj)$	$\Surj$	$\Perm\backslash\Surj$	$\Surj/\Perm$	$\Perm\backslash\Surj/\Perm$
$(\Perm, \Inj)$	$\Inj$	$\Perm\backslash\Inj$	$\Inj/\Perm$	$\Perm\backslash\Inj/\Perm$

---

Consider the intersection of the submodules $\Surj$ and $\Inj$, the groupoid $\smash{\boxed\Bij}$ of bijections of sets
(which of course contains $\Perm$ as a subgroupoid: $\Perm \subset \Bij \subset \Surj,\Inj \subset \Set$).
Given any three equipotent sets, say $\setX$, $\setY$, and $\setZ$,
consider commutative triangles in $\Bij$ with those fixed sets as vertices.
Fixing one side of such a triangle to a specific (internal) bijection
sets up (an external bijection between the possible fill-ins for the other two sides).
Thus, for example, choosing (an internal bijection from $\setX$ to $\setY$)
sets up (an external bijection from $\hom \setY \Set \setZ$ to $\hom \setX \Set \setZ$),
which restricts to (an external bijection from $\hom \setY \Bij \setZ$ to $\hom \setX \Bij \setZ$).

If we have an arbitrary finite set $\setY$, of size $n$,
let $\setX = \mathbf n$, the canonical linear order of size $n$.
Then

choosing a particular linear ordering of $\setY$ (a specific element of $\hom {\mathbf n} \Bij \setY$) sets up
an external bijection from {permutations of $\setY$ ($\hom \setY \Perm \setY = \hom \setY \Bij \setY$)} to {linear orders on $\setY$ ($\hom {\mathbf n} \Bij \setY$)},

a result which is frequently used, e.g., rather extensively in Stanley, Enumerative Combinatorics.

---

References

[CKVW] Carboni, A.; Kelly, G. M.; Verity, D.; Wood, R. J. (1998). "A 2-Categorical Approach To Change Of Base And Geometric Morphisms II". Theory and Applications of Categories. 4 (5): 82–136.