MathGroup Archive 2009

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

Search the Archive

Re: compositions with the restricted set of integers

  • To: mathgroup at
  • Subject: [mg105161] Re: [mg105143] compositions with the restricted set of integers
  • From: danl at
  • Date: Mon, 23 Nov 2009 06:50:17 -0500 (EST)
  • References: <>

>  IntegerPartitions has a useful option restricting the values of
> partitions.
> For example, IntegerPartitions[6,2,{1,2,3,4,5,6}] . Does it exist for
> Compositions?
> What I am looking for is a substitute for  a lengthy and inefficient
> approach described below. We through n dice.  How many outcomes
> *outs*correspond to the face total equal
> *sum*?
> I am aware about the recursive approach, but prefer to describe it in
> terms
> of integer partitioning (or compositions).
> *Here is my intellectually insulting solution:*
> outs[sum_, thr_] :=
>   Length[Flatten[
>     Permutations /@
>      Cases[IntegerPartitions[sum, thr, {1, 2, 3, 4, 5, 6}],
>       Table[_, {thr}]], 1]];
> Mapping with  permutations seems especially silly.
> Is there a version of Compositions with the similar restrictive option
> ({1,
> 2, 3, 4, 5, 6})?
> I would appreciate any other suggestions as well.
> Thanks
> Michael

I'm not sure this addresses your question, but a good way to do such
computations is via generating functions.

If each die has m outcomes, numbering 1-m, and we have some give number of
throws, then the number of ways to get a given sum can be found as:

countsums[sum_, throws_, m_] :=
 SeriesCoefficient[(z*(1 - z^m)/(1 - z))^throws, {z, 0, sum}]

This example agrees with your outs[30,8].

In[7]:= countsums[30, 8, 6]
Out[7]= 125588

This example does not go into recursion, run out of memory, or in other
ways cause trouble.

In[8]:= countsums[300, 80, 6]
Out[8]= 1986180404791119810432501428481165305715190860615069661053632

Daniel Lichtblau
Wolfram Research

  • Prev by Date: A little C program calling MathLink
  • Next by Date: Re: Plot3d causes crash with radeon driver and Debian testing
  • Previous by thread: compositions with the restricted set of integers
  • Next by thread: Re: compositions with the restricted set of integers