Re: Distinct Compositions
- To: mathgroup at smc.vnet.net
- Subject: [mg20845] [mg20845] Re: Distinct Compositions
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Wed, 17 Nov 1999 03:41:03 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
I will answer the first question, which asks for the number of ordered
compositions of n into k distinct parts. (Compositions are partitions
where the parts can be zero.)
First define Q[n,k] to be the number of partitions of n into k distinct
nonzero parts. It is a good exercise to prove that Q[n,k] satisfies the
following properties, which we can then use to define Q[n,k] in
Mathematica:
Q[0,0] = 1
Q[n,k] = 0 if n < 0
Q[n,k] = Q[n-k,k] + Q[n-k,k-1]
As a check, we can define Q[n_]:=Sum[Q[n,k],{k,0,n}] and compare with the
results from the built-in command PartitionsQ. (In this message, the Q
ending on commands will indicate distinctness.) By the way, the
generating function for PartitionsQ is Product[1+x^i,{i,1,n}].
Now we can go from partitions into distinct parts to compositions into
distinct parts by noting that either 0 appears as one of the parts or
it doesn't.
NumberOfCompositionsQ[n_,k_]:=Q[n,k-1]+Q[n,k]
So far, everything has been unordered. Since the parts are distinct, we
can just permute.
NumberOfOrderedCompositionsQ[n_,k_]:=k! NumberOfCompositionsQ[n,k]
We get
NumberOfOrderedCompositionsQ[8,4] = 48, as confirmed by your example.
You can use the recursion above to write a command to get the
actual compositions themselves, rather than just the number.
Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill
rpratt at email.unc.edu
http://www.unc.edu/~rpratt/
On Mon, 15 Nov 1999, Eugene wrote:
> Hello,
> I need an efficient function (algorithm) to generate an object ?Distinct
> compositions of an integer?. I called so, since it is closed to
> ?Compositions? (from Combinatorica package). It should have the
> following properties:
> Sum [(all possible enumeration of) ?k? distinct integers ] = = N ; where
>
> N is a target integer and 0 <= each integer <= (limit) integer ?m? ; Ek
> distinct;
> In other words this is:
> All integer solutions to:
> Sum[E1+E2+?+Ek] = = N where 0 <= Ek <= m ; with the constraint each Ek
> is distinct
>
> Examples:
> *the target integer is N = 8 , k = 4 , m = N = 8:
> Sum[0,0,0,8] = = 8 is not a solution since there are more then one ?0?;
>
> Sum[0,1,2,5] = = 8 is a solution since all ?candidate? integers are
> distinct;
> Sum[2,1,0,5] = = 8 is a solution ( the order of the integers is
> different);
>
> The simplest way I know to do it is to generate all Compositions and
> then to exclude all repeated (non distinct) elements (this is working
> only when m = N):
>
> In[216]:=
> Select[Compositions[8,4],Length[#]==Length[Union[#]]&]
> Out[216]=
> {{0,1,2,5},{0,1,3,4},{0,1,4,3},{0,1,5,2},{0,2,1,5},{0,2,5,1},{0,3,1,4},{0,3,4,
>
>
> 1},{0,4,1,3},{0,4,3,1},{0,5,1,2},{0,5,2,1},{1,0,2,5},{1,0,3,4},{1,0,4,3},{
>
>
> 1,0,5,2},{1,2,0,5},{1,2,5,0},{1,3,0,4},{1,3,4,0},{1,4,0,3},{1,4,3,0},{1,5,
>
>
> 0,2},{1,5,2,0},{2,0,1,5},{2,0,5,1},{2,1,0,5},{2,1,5,0},{2,5,0,1},{2,5,1,
>
>
> 0},{3,0,1,4},{3,0,4,1},{3,1,0,4},{3,1,4,0},{3,4,0,1},{3,4,1,0},{4,0,1,3},{
>
>
> 4,0,3,1},{4,1,0,3},{4,1,3,0},{4,3,0,1},{4,3,1,0},{5,0,1,2},{5,0,2,1},{5,1,
>
> 0,2},{5,1,2,0},{5,2,0,1},{5,2,1,0}}
>
> This method is not efficient even for modest values of N, because the
> magnitude of growing of ?Compositions? is much faster then magnitude of
> growing of ?Distinct Compositions?:
>
> In[228]:=
> NumberOfCompositions[8,4]= =Binomial[8+4-1,8]= =
> Coefficient[Sum[x^i,{i,0,8}]^4,x^8]= =165
> Out[228]=
> True
>
> ***task1: Does someone know how to calculate ?number of Distinct
> Compositions? (generating function or Binomial expansion)?
>
> ***task2: Does someone know efficient algorithm( I mean ? faster then
> Backtracking) for generating ?Distinct Compositions?? (will an iterating
> algorithm be better)?
>
> Thank you for your time and any suggestions!
>
> Eugene
>
> PS:
>
> (Only for reference) I will place here the code for generating
> ?Compositions?.(there is a bijection between Compositions of an integer
> and k-subsets of the form KSubsets[Range[n+k-1],n] ):
>
> Compositions[n_Integer,k_Integer] :=
> Map[
> (Map[(#[[2]]-#[[1]]-1)&, Partition[Join[{0},#,{n+k}],2,1] ])&,
> KSubsets[Range[n+k-1],k-1]
> ]
>