MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

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