Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1998
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1998

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

Search the Archive

from Compositions to trees

  • To: mathgroup at smc.vnet.net
  • Subject: [mg14214] from Compositions to trees
  • From: Wouter Meeussen <eu000949 at pophost.eunet.be>
  • Date: Wed, 7 Oct 1998 03:00:44 -0400
  • Sender: owner-wri-mathgroup at wolfram.com

hi all,

in  DiscreteMath`Combinatorica` lives  ?Compositions
"Compositions[n,k] gives a list of all compositions of integer n into k
parts."

for instance :  Compositions[3,3] returns
{{0,0,3},{0,1,2},{0,2,1},{0,3,0},{1,0,2},{1,1,1},{1,2,0},{2,0,1},{2,1,0},{3,
0,0}}

*** item 1 ***
is the definition of "Compositions[n,k]" generally known in the
mathematical community,
or is it limited to Mathematica adepts? like a 'proprietary' definition?


*** item 2 ***
the length of the list generated by "Compositions[i,j]" is
Binomial[i+j-1,j-1] ; not a particiularly earth-shaking finding, but it
took a couple of hours to get it. I can't even "prove" it.

*** item 3 ***
a rather elegant construction allows the construction of trees from
compositions:
-- start with any composition like Compositions[3,3] above, -- now
replace any integer k larger than 1 by Compositions[k-1,3], and 'thread
it'
   over the enveloping head. 

example:

let's use head t for a tree, and let's make it a tri-furcating tree.
then Compositions[3,3] translates to 
{t[0,0,3],t[0,1,2],t[0,2,1],t[0,3,0],t[1,0,2],
t[1,1,1],t[1,2,0],t[2,0,1],t[2,1,0],t[3,0,0]}

the first element, being t[0,0,3], becomes 
    Sequence@@  Thread[t[0,0,Compositions[2,3]]]   =

   t[0,0,{0,0,2}],t[0,0,{0,1,1}],t[0,0,{0,2,0}],
   t[0,0,{1,0,1}],t[0,0,{1,1,0}],t[0,0,{2,0,0}]

and its first element t[0,0,{0,0,2}] becomes
   t[0,0,{0,0,{0,0,1}}],t[0,0,{0,0,{0,1,0}}],t[0,0,{0,0,{1,0,0}}]

since the "2" is burried too deep inside the argument of t, I do not see
how Thread
can be used here. A pure function mapping over the compositions list is
a (clumsy) work-around ( see function definitions below )

The link with trees becomes aparent if we define '0' as a leaf, and '1'
as a node bearing three leaves (equivalent to {0,0,0} ).

-- although the principle can be called 'elegant', its implementation in
Mathematica is a real headache. This was so surprising to me that I
thought I'd mention it to this forum. Knowing the insides of
Mathematica should allow a 'neat' implementation.
(Allan, are you there?)

this is my 'unelegant' way :

<<DiscreteMath`Combinatorica`

t[argu__/;(!FreeQ[{argu},z])]:=Flatten at Module[{qq=1},
		yy=(yyy[argu] /.z[q_]:>(qq=q;temp));
     Function[{temp},Evaluate at yy]/@ Compositions[qq-1,Length[{argu}]]
/.yyy->w] 

w[argu__/;(!FreeQ[{argu}, p_Integer /;((pp=p)>1)])]:=
  Flatten[ReplacePart[x[argu] ,z[pp],
          Position[x[argu], p_Integer /;(p>1) ]//First] /.
x->t]//Flatten

hedgehog[a_,b_]:=
  Flatten[Apply[w, Compositions[a-1,b], {1}] /. p_Integer /;(p>1) ->z[p]

		(* /. 1:>Table[0,{b}] *)  ] /.w->t


-------  testing -------

hedgehog[5,2] should give the 42 binary trees with 5 nodes & 6 leaves.
These can be compared to other sources.

hedgehog[4,3] gives the 55 ternary trees with 4 nodes & 9 leaves. I have
no reference source to check these against. Hope they're right.

------------------------


wouter.




 
Dr. Wouter L. J. MEEUSSEN
w.meeussen.vdmcc at vandemoortele.be
eu000949 at pophost.eunet.be



  • Prev by Date: Complex Hadamard Matrix
  • Next by Date: Series of a Root object
  • Previous by thread: Re: Complex Hadamard Matrix
  • Next by thread: Re: from Compositions to trees