Eulerian numbers
- To: mathgroup at smc.vnet.net
- Subject: [mg30570] Eulerian numbers
- From: kaimano <unrealkaiman at libero.it>
- Date: Wed, 29 Aug 2001 01:40:15 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
I was studying Eulerian numbers and after having defined my own function I
saw something very strange about the computational time
Here is my definition....( i know, it lacks the control of the parameters to
be integers... )
myEulerian[n_, k_] := k*myEulerian[n - 1, k] + (n - k + 1)myEulerian[n - 1,
k - 1];
myEulerian[n_, 1] = 1;myEulerian[0, k_] = If[k == 1, 1, 0];
and here is an example.
myEulerian[5, 3]
66
after that I imported the package Combinatorica to make a comparison with
the function Eulerian[...] defined in it.
<< DiscreteMath`Combinatorica`
Timing[Eulerian[200, 11]]
{4.41667 Second,
1899050754604760049211351181228068537387060655311436868149953520589342707921
57\
9044568570549268967678130407612627284545917662510239121246135277121321969173
87\
09541822824645767929887525587548776228868638648561016}
Timing[myEulerian[200, 11]]
{0.466667 Second,
1899050754604760049211351181228068537387060655311436868149953520589342707921
57\
9044568570549268967678130407612627284545917662510239121246135277121321969173
87\
09541822824645767929887525587548776228868638648561016}
With my surprise my function is much faster.
How can this be?
I gave a look inside the Combinatorica.m package and found the definition of
Eulerian.
Eulerian[n_Integer, k_Integer] := Eulerian1[n, k]
Eulerian1[0, k_Integer] := If[k == 1, 1, 0]
Eulerian1[n_Integer, k_Integer] :=
Eulerian1[n, k] = k Eulerian1[n - 1, k] + (n - k + 1) Eulerian1[n - 1, k -
1]
Why does it lack a definition like
Eulerian1[n_, 1] = 1;
that would speed up a lot the program?
Am I not seeing other difficulties?
Thanks
Tiziano Mosconi