# Combinatorial Questions about Multisets

I was looking at this question over at StackOverflow and I came up with a couple questions about multisets.

Firstly, consider the multisets under isomorphism:

• there's 1 of cardinality 1; {a:1}
• there's 2 of cardinality 2; {a:2}, {a:1,b:1}
• there's 3 of cardinality 3; {a:3}, {a:2,b:1}, {a:1,b:1,c:1}
• there's 5 of cardinality 4; {a:4}, {a:3,b:1}, {a:2,b:2}, {a:2,b:1,c:1}, {a:1,b:1,c:1,d:1}
• there's 7 of cardinality 5; {a:5}, {a:4,b:1}, {a:3,b:2}, {a:3,b:1,c:1}, {a:2,b:2,c:1}, {a:2,b:1,c:1,d:1}, {a:1,b:1,c:1,d:1,e:1}
• How many are there of cardinality n?

Secondly, given two multisets of cardinality n, (X,f) and (Y,g), where X and Y are sets and f and g are multiplicity functions, how many multisets (X × Y,h) are there such that:

• ∀ x ∈ X, f(x) = ∑y ∈ Y h(x,y)
• ∀ y ∈ Y, g(y) = ∑x ∈ X h(x,y)
-
There are eleven of cardinality 6, so clearly the answer is that they follow the progression of the primes! Just kidding. These are the partition numbers: oeis.org/A000041 –  Jonah Ostroff Jan 24 '11 at 21:54
@Jonah Ostroff: Well when you put it that way, it seems obvious. I feel a bit silly for not thinking of them, especially since they were on slashdot just the other day. –  user1596 Jan 24 '11 at 22:07