Math Challenge: Give a bijection between the positive integers and ...?

Question

Give a bijection between the positive integers and the set of finite multisets of the positive integers. What does positive integer does {1,1,2,3} map to in your bijection?

A multiset is a like a set but can contain multiple copies of each element.

Answer 1

Oh, this one's easy: let #(A, n) be the number of times n appears in the multiset A, and let p_n denote the nth prime number. Then define the function f from the set of finite multisets to ℕ by:

f(A) = [k=1, ∞]∏((p_k)^#(A, k))

Since A is a finite multiset, only finitely many of the #(A, k) will be nonzero, so this product is well-defined. It is also a bijection - surjectivity follows from the fact that every natural number has a prime factorization (including 1, since it is the empty product), and injectivity follows from the fact that the prime factorizations are unique.

Given the above function, f({1, 1, 2, 3}) = 2^2 * 3^1 * 5^1 = 60.