Multisets package

• To: mathgroup at smc.vnet.net
• Subject: [mg121467] Multisets package
• From: David Bevan <david.bevan at pb.com>
• Date: Fri, 16 Sep 2011 05:47:47 -0400 (EDT)
• Delivered-to: l-mathgroup@mail-archive0.wolfram.com

```In case this is of interest to anyone:

I've put together a package that defines functions Multisets and NumberOfMultisets. NumberOfMultisets supports symbolic calculations.

I've submitted it to the Wolfram Library Archive.

Here are some details and a few examples:

Multisets[list, k] gives a list of all multisets containing at most k elements from list.

Multisets[list, {k}] gives all multisets containing exactly k elements.

Multisets[list, {l, m}] gives all multisets containing between l and m elements.

Multisets[list, {l, m, d}] gives all multisets containing l, l+d, ..., m elements.

Multisets[list, {{k1, k2, ...}}] gives all multisets containing k1, k2, ...  elements.

Multisets[list, kspec, m] limits the result to multisets in which the multiplicity of each element is at most m.

Multisets[list, kspec, {l, m}] limits the result to multisets in which the multiplicity of each element is between l and m.

Multisets[list, kspec, {l, m, d}] limits the result to multisets in which the multiplicity of each element is restricted to l, l+d, ..., m.

Multisets[list, kspec, {{m1, m2, ...}}] limits the result to multisets in which the multiplicity of each element is restricted to m1, m2, ....

Multisets[list, kspec, mspec, c] limits the result to the first c multisets.

Multisets[n, kspec, ...] is equivalent to Multisets[Range[n], kspec, ...].

In Multisets[list, kspec, mspec, ...], a kspec or mspec of All corresponds to {0, Infinity}.

In Multisets[list, kspec, mspec, ...], a kspec or mspec of -k corresponds to {k, Infinity}.

NumberOfMultisets[list, kspec, mspec] is equivalent to Length[Multisets[list, kspec, mspec]].

Examples

Multisets with an odd number of elements:

Multisets[{a, b, c}, {1, 5, 2}]

{{a}, {b}, {c}, {a, a, a}, {a, a, b}, {a, a, c}, {a, b, b}, {a, b, c}, {a, c, c}, {b, b, b}, {b, b, c}, {b, c, c}, {c, c, c}, {a, a, a, a, a}, {a, a, a, a, b}, {a, a, a, a, c}, {a, a, a, b, b}, {a, a, a, b, c}, {a, a, a, c, c }, {a, a, b, b, b}, {a, a, b, b, c}, {a, a, b, c, c}, {a, a, c, c, c}, {a, b, b, b, b}, {a, b, b, b, c}, {a, b, b, c, c}, {a, b, c, c, c}, {a, c, c, c , c}, {b, b, b, b, b}, {b, b, b, b, c}, {b, b, b, c, c}, {b, b, c, c, c}, { b, c, c, c, c}, {c, c, c, c, c}}

The first 20 multisets with an even number of elements in which each element occurs an odd number of times:

Multisets[{0, 1}, {0, Infinity, 2}, {1, Infinity, 2}, 20]

{{0, 1}, {0, 0, 0, 1}, {0, 1, 1, 1}, {0, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 1, 1, 1}, {0, 0, 0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 0,0, 1}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 1}, {0, 0, 0, 0, 0, 1, 1, 1, 1, 1}, {0,0, 0, 1, 1, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1}}

The number of multisets containing up to 300 elements, none of which occur more than 100 times:

NumberOfMultisets[3, 300, 100]

1030301

Some symbolic calculations:

NumberOfMultisets[n, All, m]

(1+m)^n

Assuming[n > 0, NumberOfMultisets[n, {2n}, n]]

Binomial[3n-1, n-1] - n Binomial[2n-2, n-1]

NumberOfMultisets[a, {b}] / NumberOfMultisets[b, {a}] // FunctionExpand

a/b

Assuming[r >= 0 && k >= 0, NumberOfMultisets[3, {2r}, r+k]]

1/2 (2 - 3k^2 + 3r + r^2 + k(3 + 6r))  r >= 1+k
1 + 3r + 2r^2                          True

David Bevan
David.Bevan at pb.com

```

• Prev by Date: Re: How create new style sheet- Mathematica 8
• Next by Date: Re: Compilation: Avoiding inlining
• Previous by thread: Re: Interactive settings for ParamPlot3D. Mesh not quite working.
• Next by thread: Styling initialization cells