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