Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)
share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.