# Error in code or need more runtime?

Hello everyone,

I would like to compute the number of sub-multisets (of a particular cardinality) of a multiset. The "mother" multiset contains exactly 2 copies of the numbers 0 through 52 (it has cardinality 106), and I would like to compute the number of distinct sub-multisets of size 14. I am attempting to do this with Sage (of course), and the code I am trying to use is as follows:

S = range(53); S.extend(range(53))

// This makes my mother set of two copies of the numbers 0 through 52

Hands = Subsets(S, 14, submultiset=true); Hands.cardinality()

// This defines a set of the sub-multisets of size 14, and then outputs their cardinality.

When I run this (in the Sage Notebook running inside Oracle VirtualBox with 2gb of allotted RAM), it gives me a small green rectangle that changes the cursor to a 'watch' as if it's still running. It's been like this for over and hour now. Is there an error in my code or should I expect such a calculation to take a 'long' time? I'm not familiar with 'large' calculations such as this one.

edit retag close merge delete

Sort by » oldest newest most voted

You can kill the computation, for Sage is apparently trying to build all of these sets in order to count them. This is the default behaviour (and not always a very good idea) when no .cardinality() method has been implemented specifically for this problem.

Here, the number of submultiset of [0..52] containing at most twice the same element is at least the number of subsets of 53, i.e. at least 2^53. That is already too much.

If you know how this value should be computed, however, you are welcome to add this missing feature into Sage !

http://www.sagemath.org/doc/developer/

more

@Nathann's answer explains that with your code, Sage is not calculating the number but enumerating all submultisets, which in this case just takes too long.

For your particular counting problem, you can use compositions (also known as ordered partitions). You can iterate through compositions of 14 with maximum part 2, (there are 610 of them), and count each of them with an appropriate weight (some binomial coefficient) to account for the number of ways to choose which numbers the parts refer to.

sage: C = Compositions(14,outer=[2]*53)
sage: C.cardinality()
610
sage: sum(binomial(53,len(c)) for c in C)
48204860086530

more