Asked by rox
on 3 May 2013

Hi,

I am trying to create a function which generates a Eulerian number for given n and k. This number should be generated by the recurrence relation

P(i,j)=(j+1).*P(i-1,j)+(i-j).*P(i-1,j-1)

I am getting an answer from Matlab yet I don't know if it is correct because I defined P by P=Perms([ones(i):i j]) since I know the first column should be made up of ones. I'm not sure if I defined P for P(i,j) correctly.

Any help please? Thanks a lot!!

function [P]=euler(~)

n=input(' Enter the number n '); % user enters the number to be generated k=input(' Enter the number k '); % user enters the number to be generated

for i=1:n; % defining the number n inputted by the user as a vector in ters of i so as for the function to work out all the terms up to n for j=2:k; % defining the number n inputted by the user as a vector in ters of i so as for the function to work out all the terms up to n P=perms([ones(i):i j]); %defining P

if i>=0 && j==0; %constraints for first iteration P(i,j)=1; %answer of first iteration

elseif j>=i && i>=0; %constraints for second iteration P(i,j)=0; %answer of second iteration end end end

for i=1:n; %once again we define i and j for the recurrence relation. Note that i and j start from 2 since when any one of them is 1, for j=2:k; %then i-1=0 or j-1=0, which result in P(0,1) or P(1,0). But zero is not allowed as a column number, hence i and j begin from 2. P=perms([ones(i):i j]) if j<=i; %constraints for the recurrence relation P(i,j)=(j+1).*P(i-1,j)+(i-j).*P(i-1,j-1) %the recurrence relation end end end end

*No products are associated with this question.*

Answer by Roger Stafford
on 5 May 2013

Accepted answer

As it stands, your wish to generate that table using that formula with a matlab array P cannot be realized because its first column corresponds to a j-index value of zero, and matlab does not allow zero indices in its arrays. You can, however, define an array Q as being Q(i,j+1) = P(i,j) and generate Q instead. Your formula would then become

Q(i,j+1) = (j+1)*Q(i-1,j+1)+(i-j)*Q(i-1,j)

With that understanding, do this:

N = 9; % <-- Choose whatever value you wish for the table size N Q = [ones(N,1),zeros(N,N-1)]; for i = 2:N for j = 1:i-1 Q(i,j+1) = (j+1)*Q(i-1,j+1)+(i-j)*Q(i-1,j); end end

Answer by Roger Stafford
on 4 May 2013

Your problem will be greatly simplified if you compute only those Euler numbers actually required in the recursion formula for generating the Euler number with parameters (n,k). These can all be arranged in a rectangular n-k by k+1 matrix of values and the value in the last row of the last column will be the desired Euler number.

Let the integer parameter values n and k be given with n >= 1 and 0 <= k < n.

A = ones(n-k,k+1); % Initialize first row and first column to all ones for r = 2:n-k for c = 2:k+1 A(r,c) = r*A(r,c-1)+c*A(r-1,c); % <-- The transformed recursion formula end end P = A(end,end); <-- This is the desired Euler number for (n,k).

For example, with n = 12 and k = 5, you will get P = 162512286.

Show 1 older comment

Roger Stafford
on 4 May 2013

Roger Stafford
on 4 May 2013

rox
on 5 May 2013

No not exactly, I defined the first section using 'perms' because I just didn't know how else to define P for the first part because I kept getting an error like this

Attempted to access P(0,2); index out of bounds because numel(P)=1.

What I want is just like you said, a table of eulerian numbers with for instance 'a P which gives a list of all 1,191 of those permutations of 1:7 which have exactly 4 "ascents" such as with [1,3,4,7,5,6,2]?' Thanks a lot for the help!

Answer by rox
on 5 May 2013

I'm not sure but I think I got it, I replaced the parameters n and k by r and c and I get a table of numbers..

function [P]=euler(n,k) n=input(' Enter the number n '); % user enters the number to be generated k=input(' Enter the number k '); % user enters the number to be generated for r=1:n; % defining the number n inputted by the user as a vector in ters of i so as for the function to work out all the terms up to n for c=2:k; % defining the number n inputted by the user as a vector in ters of i so as for the function to work out all the terms up to n A=ones(n-k,k+1); % Initialize first row and first column to all ones

if n>=0 && k==0 %constraints for first iteration A(r,c)=1; %answer of first iteration elseif k>=n && n>=0 %constraints for second iteration A(r,c)=0; %answer of second iteration end end P=A(end,end) end for r=2:n-k; for c=2:k+1; A=ones(r,c); % Initialize first row and first column to all ones if n>=1 && 0<=k<n %constraints for the recurrence relation A(r,c)=r.*A(r,c-1)+c.*A(r-1,c) % <-- The transformed recursion formula end end P=A(end,end) %<-- This is the desired Euler number for (n,k). end end

Answer by Roger Stafford
on 5 May 2013

As I stated earlier, the code I wrote assumed that you wanted only a single number returned by your 'euler' function, namely the value of the eulerian number for n and k - that is, the count of all permutations of 1:n for which there are exactly k "ascents".

Obtaining a list of such permutations is quite a different matter and requires more computation. Suppose n and k have been given.

P = perms(1:n); % First get all permutations of 1:n P = P(sum(diff(P,1,2)>0,2)==k,:); % P is now your desired list of permutations C = size(P,1); % C is the corresponding eulerian number

This is a brute force counting of the eulerian number and is of course much less efficient for sizable n and k values than making use of the recursion formula, in spite of the brevity of code.

As to returning an entire table of eulerian numbers you need to define what sort of table you wish to obtain.

rox
on 5 May 2013

What I need is a table similar to the one below, yet it must be worked out using the recurrence relation I defined above:

P(i,j)=(j+1).*P(i-1,j)+(i-j).*P(i-1,j-1)

Now I also need to input the first two iterations for certain parameters of n and k

if n>=0 && k==0 %constraints for first iteration A(r,c)=1; %answer of first iteration elseif k>=n && n>=0 %constraints for second iteration A(r,c)=0; %answer of second iteration 1 1 1 4 1 1 11 11 1 1 26 66 26 1 1 57 302 302 57 1 1 120 1191 2416 1191 120 1 1 247 4293 15619 15619 4293 247 1 1 502 14608 88234 156190 88234 14608 502 1

This is what I require, and I am obtaining a similar triangular array, yet the values are different, they are mainly composed of 1's.

Opportunities for recent engineering grads.

## 0 Comments