Counting Partitions and Bijections

[Curiouspoet]

Homework Statement

(A) Find and prove a bijection between the set of all functions from [n] to [3] and the set of all integers from 1 to 3ⁿ.
(B) How many set partitions of [n] into two blocks are there?
(C) How many set partitions of [n] into (n-1) blocks are there?
(D) How many set partitions of [n] into (n-2) blocks are there?
(E) How many ways can we split a group of 10 people into two groups of size 3 and one group of size 4?

Homework Equations

The Attempt at a Solution

I'm not sure how to handle partitions of a set being mapped to another set. Could someone give me an idea of what definitions I would consider? I know (E) is done by equivalence relations and we could show two groups of size 3 are equal to each other, but I'm not sure how to use that. I'd like to know what method of attack I need to use to solve these problems, I'd assume it's similar for all of them?

 

[kurt.physics]

For (A), there is a bijection between the set of all functions from [n] to [3] and the set of all integers from 1 to 3n. This can be proven by constructing a function f that maps each function g from [n] to [3] to an integer. Specifically, define f(g) = x such that x is the integer whose decimal expansion is composed of the numbers in the range [3] that g takes on. For example, if g = {1 → 2, 2 → 3, 3 → 1}, then f(g) = 231. This is a bijection since each function has a unique corresponding integer, and each integer corresponds to a unique function. For (B), there are 2^n-1 ways to partition a set of n elements into two blocks. This can be proven by induction. The base case holds as n = 1, and for n > 1, there are 2^(n-1) ways to partition the set into two blocks, and each of these partitions can be split further into two blocks, resulting in 2^n-1 ways. For (C), there are (n-1)! ways to partition a set of n elements into n-1 blocks. This can be proven by counting the number of ways we can divide the set into n-1 blocks. We can choose any element from the set to be the first block, then any of the remaining n-1 elements to be the second block, then any of the remaining n-2 elements to be the third block, and so on until we have n-1 blocks. This can be done in (n-1)! ways, which is the number of ways to partition the set into n-1 blocks. For (D), there are (n-1)!/(2!(n-3)!) ways to partition a set of n elements into n-2 blocks. This can be proven by counting the number of ways we can divide the set into n-2 blocks. We can choose any two elements from the set to be the first block, then any of the remaining n-3 elements to be the second block, then any of the remaining n-4 elements to be the third block, and so on until we have n-2 blocks. This can be done in (n-1)!/(2!(n-3)!)