# Proof: Permutations and Surjective Functions

• schaefera
In summary, the conversation discusses the relationship between the number of partitions of a finite set X into n subsets, denoted as f(n,m), and the number of surjective functions from X to a finite set Y, which is n!*f(n,m). The concept of a function being onto is also introduced, and it is noted that the number of ways to permute the elements of X could be related to f(n,m). It is suggested that the solution could involve creating a function from a partitioned version of X to Y, and that induction may not be necessary.
schaefera

## Homework Statement

Let X and Y be finite nonempty sets, |X|=m, |Y|=n≤m. Let f(n, m) denote the number of partitions of X into n subsets. Prove that the number of surjective functions X→Y is n!*f(n,m).

## Homework Equations

I know a function is onto if and only if every element of Y is mapped to by an element of X. That is, for all y in Y, there is an x in X such that f(x)=y. Clearly if f is a function and n≤m, a function from X to Y can be onto (but it doesn't have to be, for instance, all of X could map to the same Y).

## The Attempt at a Solution

I tried by induction, but got lost moving from n=k to n=k+1, so I'm not sure if that works. I think that f(n, m) has something to do with the number of ways to permute the elements of X... but not sure. This is before the lecture on combinations, so I'm not sure if we need to use that method.

Could it have something to do with creating a function from a partitioned version of X to Y?

No takers?

schaefera said:
Could it have something to do with creating a function from a partitioned version of X to Y?

Sure it could. You split X into subsets, each one of which maps into a unique element of Y. Then given a split (of which there are f(n,m)) you figure out how many ways there are to assign each subset to an element of Y. I don't think induction is really necessary here. Just explain it in words.

## 1. What is a permutation?

A permutation is a way of arranging a set of objects in a specific order. It is a bijective mapping of the set onto itself, meaning that each element appears exactly once in the arrangement.

## 2. How many permutations are possible for a set with n elements?

The number of permutations for a set with n elements is n factorial, denoted as n!. For example, if a set has 5 elements, there are 5! = 120 possible permutations.

## 3. What is a surjective function?

A surjective function is a function where every element in the range has at least one corresponding element in the domain. In other words, the function "covers" all of its range.

## 4. How are permutations and surjective functions related?

Permutations and surjective functions are related because every permutation of a set is a surjective function, and every surjective function can be represented as a permutation. This means that the number of surjective functions for a set with n elements is also n!.

## 5. Can a permutation be surjective if the set has more elements than its range?

No, a permutation cannot be surjective if the set has more elements than its range. This is because a surjective function must cover all elements in its range, and if the range has fewer elements than the set, some elements in the set will not have a corresponding element in the range.

Replies
1
Views
1K
Replies
8
Views
741
Replies
3
Views
969
Replies
2
Views
1K
Replies
3
Views
1K
Replies
4
Views
521
Replies
20
Views
3K
Replies
3
Views
2K
Replies
1
Views
964
Replies
9
Views
2K