Ask Your Question

# 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

## 2 answers

Sort by » oldest newest most voted

Like this:

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

more

## Comments

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)
( 2018-12-03 15:10:33 -0600 )edit

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

## Comments

Thanks for the theory!

( 2018-12-04 01:34:54 -0600 )edit

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2018-12-03 06:36:11 -0600

Seen: 384 times

Last updated: Dec 04 '18