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

Let $X={1,2,…,n}$ and $Y={1,2,…,m}$. Is there any way to get the set of all functions from $X$ to $Y$ in SageMath?

edit retag close merge delete

Sort by » oldest newest most voted Like this:

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

more

Exactly the right tool. To further illustrate:

For $n = 2$, $m = 3$:

sage: M = FiniteSetMaps([1 .. 2], [1 .. 3]); M
Maps from {1, 2} to {1, 2, 3}
sage: for f in M: print(f)
map: 1 -> 1, 2 -> 1
map: 1 -> 1, 2 -> 2
map: 1 -> 1, 2 -> 3
map: 1 -> 2, 2 -> 1
map: 1 -> 2, 2 -> 2
map: 1 -> 2, 2 -> 3
map: 1 -> 3, 2 -> 1
map: 1 -> 3, 2 -> 2
map: 1 -> 3, 2 -> 3


For $n = 3$, $m = 2$

sage: M = FiniteSetMaps([1 .. 3], [1 .. 2]); M
Maps from {1, 2, 3} to {1, 2}
sage: for f in M: print(f)
map: 1 -> 1, 2 -> 1, 3 -> 1
map: 1 -> 1, 2 -> 1, 3 -> 2
map: 1 -> 1, 2 -> 2, 3 -> 1
map: 1 -> 1, 2 -> 2, 3 -> 2
map: 1 -> 2, 2 -> 1, 3 -> 1
map: 1 -> 2, 2 -> 1, 3 -> 2 ...
(more)

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 ;-).

more