Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

To resolve issues starting MATLAB on Mac OS X 10.10 (Yosemite) visit: http://www.mathworks.com/matlabcentral/answers/159016

Am I defining the permutation well?

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

0 Comments

rox

Products

No products are associated with this question.

4 Answers

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

1 Comment

rox on 6 May 2013

That actually works great for me! Thanks so much for all your help!!

Roger Stafford
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.

4 Comments

Roger Stafford on 4 May 2013

Please give a simple example of what you wish your 'euler' function to return with. I understood from your original statement that you only wanted a single eulerian number, not a set of permutations. Or possibly you wish it to return some kind of table of eulerian numbers? For example, if your hypothetical user specifies n = 7 and k = 4, do you wish it to return with P = 1191 or with 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]?

Roger Stafford on 4 May 2013

It has occurred to me that possibly you are trying to demonstrate that the eulerian numbers you obtain using the given recursion formula agree with the counts you observe with actual permutations from 'perms'. Is that the case?

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!

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

0 Comments

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

1 Comment

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.

Roger Stafford

Contact us