MathGroup Archive 2004

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

Search the Archive

RE: RE: Re: doing things on a procedural way and doing them on a functional way

  • To: mathgroup at smc.vnet.net
  • Subject: [mg47010] RE: [mg46991] RE: [mg46988] Re: doing things on a procedural way and doing them on a functional way
  • From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
  • Date: Sat, 20 Mar 2004 03:50:22 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

A remark to add...

>-----Original Message-----
>From: Wolf, Hartmut 
To: mathgroup at smc.vnet.net
>Sent: Friday, March 19, 2004 7:36 AM
>To: mathgroup at smc.vnet.net
>Subject: [mg47010] [mg46991] RE: [mg46988] Re: doing things on a procedural way
>and doing them on a functional way
>
>
>
>>-----Original Message-----
>>From: Paul Abbott [mailto:paul at physics.uwa.edu.au]
To: mathgroup at smc.vnet.net
>To: mathgroup at smc.vnet.net
>>Sent: Thursday, March 18, 2004 10:38 AM
>>To: mathgroup at smc.vnet.net
>>Subject: [mg47010] [mg46991] [mg46988] Re: doing things on a procedural 
>>way and doing them on a functional way
>>
[...]
>>
>>I can't help but feel that there should be an elegant way to do this 
>>using Distribute ...
>>
>>Cheers,
>>Paul
>>
[...]
>
>You're completely right,
>the solution, I published yesterday, also works with 
>distribute (instead of Outer):
>
>In[32]:= nocnac[{arg_}, op_] := {arg}
>In[33]:=
>nocnac[{args__}, op_] := 
>  Flatten[ReplaceList[{args}, {a__, b__} :> 
>        Distribute[op[nocnac[{a}, op], nocnac[{b}, op]], List]], 1]
>
>
[...]


Effectively both solutions are the same, as for Distribute you always can
find an equivalent expression with Outer, e.g.:

In[164]:= Distribute[List[{1, 2}, {{3, 4}, 5}, 6], List]
Out[164]=
{{1, {3, 4}, 6}, {1, 5, 6}, {2, {3, 4}, 6}, {2, 5, 6}}

...this is by definition the same as

In[170]:= Distribute[List[{1, 2}, {{3, 4}, 5}, {6}], List]
Out[170]=
{{1, {3, 4}, 6}, {1, 5, 6}, {2, {3, 4}, 6}, {2, 5, 6}}

...functionally equivalent to

In[166]:= Flatten[Outer[List, {1, 2}, {{3, 4}, 5}, {6}, 1], 2]
Out[166]=
{{1, {3, 4}, 6}, {1, 5, 6}, {2, {3, 4}, 6}, {2, 5, 6}}


You may have observed that my first solution using Outer doesn't work with
List, whereas that one above with Distribute does. This is not a problem of
Outer, I just have been a bit careless with levels (at Flatten and Outer).
This code also works with List:

In[143]:=
nocnac[{arg_}, op_] := {arg}

nocnac[{args__}, op_] := 
  Flatten[ReplaceList[{args}, {a__, b__} :>
        Outer[op, nocnac[{a}, op], nocnac[{b}, op], 1]
      ], 2]




>
>
>In[39]:= Length[nocnac[Range[#], op]] & /@ Range[10]
>Out[39]=
>{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862}
>
>
[...]

>
>I don't know, but assume that this can be expressed simply 
>through some sort of combinatorical numbers. 


Yes, indeed, it is given by

In[171]:= Binomial[2 #, #]/(# + 1) & /@ Range[0, 9]
Out[171]=
{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862}

...and the numbers
  
  c[n_] := Binomial[2n, n]/(n + 1)


are called the Catalan numbers. See e.g.
http://www.research.att.com/~njas/sequences/
and my observation...

>
>In[57]:= nc[#]/nc[# - 1] & /@ Range[2, 30] // N
>Out[57]=
>{1., 2., 2.5, 2.8, 3., 3.14286, 3.25, 3.33333, 3.4,
> 3.45455, 3.5, 3.53846, 3.57143, 3.6, 3.625, 3.64706,
> 3.66667, 3.68421, 3.7, 3.71429, 3.72727, 3.73913,
> 3.75, 3.76, 3.76923, 3.77778, 3.78571, 3.7931, 3.8}
>
[...]
>
>The conjecture of course is, that asymtotically nc[n] ~ 4^n.
>

is nothing else than the simple fact

In[182]:= Limit[2n (2n - 1)/(n (n + 1)), n -> Infinity]
Out[182]= 4


--
Hartmut Wolf


  • Prev by Date: FW: Question on Ordering
  • Next by Date: Re: Re: doing things on a procedural way and doing them on a functional way
  • Previous by thread: RE: Re: doing things on a procedural way and doing them on a functional way
  • Next by thread: Re: doing things on a procedural way and doing them on a functional way