How to get the collection of all functions from X to Y in SageMath

savecancel

Like this:

M = FiniteSetMaps(["a", "b"], [3, 4, 5]); M

Disclaimer : I know zilch about combinatirics. This problem might have elegant (and already programmed) solutions among the combinatorics tools of Sage. However, the problem seems simple enough to attempt a "naïve" solution.

A function from $X$ to $Y$ is the set of tuples $[ (x_i,y_j),...,i=1,\dots,n,j\in[0..n]]$, meaning that $x_i$ has $y_j$ as image, the notation $(x_i,y_0)$ denoting the case where $x_i$ has no image. Let $S_{n,m}$ the set of all functions from $X$ to $Y$ when X has $n$ elements and Y has $m$ elements.

1): the set $S_{1,m}$ is simply $[(x_1,y_j),j=0,...,m]$.

2): knowing $S_{n,m}$, one can simply build $S_{n+1,m}$ by adding (i. e. concatenating) to each of the functions in $S_{n,m}$ a member of $[(x_{n+1},y_j),j=0,...,m]$. In other words, S_{n+1,m}$ is the cartesian product of $S_{n,m}$ and $[(x_{n+1},y_j),j=0,...,m]$.

3): 1) and 2) are sufficient to build $S_{n,m}$ by recurrence on n. It results immediately that the cardinal is $(m+1)^n$, including the degenerate case where no element of $X$ has an image in $Y$.

The implementation, whose details depend of the planned use of the functions, is, as usual, left to the reader as an exercise ;-).