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