MathGroup Archive 1998

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

Search the Archive

from Compositions to trees

  • To: mathgroup at
  • Subject: [mg14214] from Compositions to trees
  • From: Wouter Meeussen <eu000949 at>
  • Date: Wed, 7 Oct 1998 03:00:44 -0400
  • Sender: owner-wri-mathgroup at

hi all,

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

for instance :  Compositions[3,3] returns

*** 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
-- start with any composition like Compositions[3,3] above, -- now
replace any integer k larger than 1 by Compositions[k-1,3], and 'thread
   over the enveloping head. 


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

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


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

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 :


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}]]

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

  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.



Dr. Wouter L. J. MEEUSSEN
w.meeussen.vdmcc at
eu000949 at

  • 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