Am I defining the permutation well?

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

Answer 1

[Roger Stafford]

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

[rox]

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

Answer 2

[Roger Stafford]

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.

[rox]

Thanks a lot, your code worked perfectly on its own! However, what I need is to generate matrices of permutations where the columns increase by one more than the previous, I'm not sure if you understand me so here's a link to get the idea http://en.wikipedia.org/wiki/Eulerian_number.

Now I integrated your code into the one I wrote this is what I have:

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(n-k,k+1); % 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

I do get several matrices yet the columns do not increase by one each time. I'm really stuck on this one!

[Roger Stafford]

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]

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]

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 3

[rox]

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 4

[Roger Stafford]

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]

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.