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