       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:
replace any integer k larger than 1 by Compositions[k-1,3], and 'thread
it'

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

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