You are Here: Home >< Maths

if n= {1,2... n} how many functions are there from n to n? watch

1. little unsure
2. (Original post by Trackstar)
little unsure
Well, 1 can map to any of 1..n, 2 can map to any of 1..n, 3 can map to ...

It's a problem in combinatorics.
3. (Original post by atsruser)
Well, 1 can map to any of 1..n, 2 can map to any of 1..n, 3 can map to ...

It's a problem in combinatorics.
yes, i thought n^2 but apparently its n^n
4. (Original post by Trackstar)
yes, i thought n^2 but apparently its n^n
Each choice of mapping for 1,2, .., n is independent of the others. So if there are n for each, how many in total?

Maybe consider a more general but also more specific example: how many maps are there from {1, 2} to {1, 2, 3}? We can map 1 to 1,2, or 3, and we can map 2 to 1,2, or 3 independently, so in total ...
5. (Original post by atsruser)
Each choice of mapping for 1,2, .., n is independent of the others. So if there are n for each, how many in total?

Maybe consider a more general but also more specific example: how many maps are there from {1, 2} to {1, 2, 3}? We can map 1 to 1,2, or 3, and we can map 2 to 1,2, or 3 independently, so in total ...
yeah, so what i cant get my head around is that because 1 maps to all of 1,2,..n and so does 2, 3 etc and this happens n times it would just be n*n n^2
6. (Original post by Trackstar)
and this happens n times it would just be n*n n^2
This isn't right. If I want to count the mappings from {1,2,3} to {1,2,3,4}, then there are 4 choices for 1, 4 choices for 2, 4 choices for 3. Each of these can be made independently. So how many in total are there? Think of making a tree of combinations - how many branches would you need at each stage?
7. (Original post by atsruser)
This isn't right. If I want to count the mappings from {1,2,3} to {1,2,3,4}, then there are 4 choices for 1, 4 choices for 2, 4 choices for 3. Each of these can be made independently. So how many in total are there? Think of making a tree of combinations - how many branches would you need at each stage?
okay, are you saying that you then have to include all the different combinations in which {1,2,3} can map to {1,2,3,4} say 1-2, 2-3, 3-4 is one, 1-4, 2-3, 3-1 is another.
8. (Original post by Trackstar)
okay, are you saying that you then have to include all the different combinations in which {1,2,3} can map to {1,2,3,4} say 1-2, 2-3, 3-4 is one, 1-4, 2-3, 3-1 is another.
Actually forget the tree of combinations idea - I don't think that's a good way to represent things. However, yes, you are thinking along the right lines. Have you heard of the fundamental counting principle in combinatorics? If not, you should google it.

Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: October 6, 2017
Today on TSR

Edexcel C2 Core Unofficial Markscheme!

Find out how you've done here

Poll
Useful resources

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

How to use LaTex

Writing equations the easy way

Study habits of A* students

Top tips from students who have already aced their exams

Chat with other maths applicants