Is it possible to set rules for calculating permutations of column vectors?

Forgive me as I am pretty rusty with my MATLAB and general coding.

I am working on some combonitorics and group theory stuff for a math class and essentially need to be able to calculate the number of possible permutations of a column tableau (just a vector in this case) given a set of rules on how that column can be constructed and a given number of elements. This is what I have so far, it just calculates the total number of permutations for each vector and puts those values in a vector of their own.

n=input('Input n value\n');
A=zeros(1,n);
for i=1:n;
    v=[1:i]';
    P=perms(v1);
    A(i)=size(P,1);
end

Here are the rules I want to create for how each permutation is allowed to be created:

Starting from the top element of the column and moving down, entries can decrease in value by exactly 1, or they can increase by any amount. For example, for n=5, a valid permutation could be v=[2, 1, 4, 3, 5]' (notice each subsequent entry either decreases by 1, or increases by some other amount) but an INVALID permutation could be something like v=[5, 3, 2, 1, 4]' (notice 5 decreases to 3, which is a decrease by 2 which is not allowed). I want to be able to create every VALID permutation given an n-value and then count the number of permutations created. Again, I am a little rusty at coding and I hope this makes sense! Thanks in advance!

[James Tursa]

How large can n be?

[badscience]

n can be any size. Essentially the conjecture states that the number of tableaux of shape 1^n (meaning just the number of possible permutations of this column vector) that follow these rules is 2^(n-1).

I am just trying to write some code that will show this is true for whatever n you want to choose.

[James Tursa]

For large n you might not have enough RAM or computer time to actually construct all of the possibilities. Are you just looking for generic code to do this for "small enough" n to give you a good feeling about the conjecture?

[badscience]

Thats exactly it. I know this will be pretty memory intensive so I wont be able to to really large n, but yes, I am tasked with "Convincing my professor that this is true without actually proving it" so I am writing code that will do this for "reasonable" n-values.

[badscience]

Essentially what I am struggling to do is to code in the set of "rules" on how each permutation can be constructed. I am sure it will not involve using the perms function.

[James Tursa]

Why not? Has your instructor forbidden you from using the perms function?

[badscience]

No not at all, but since there are those rules I have to impliment, I am not sure if I will be able to use the perms function. Maybe there is a way MatLab can use the perms function, then go through and count the "Valid" Permutations from the vector of all permutations.

[James Tursa]

Exactly ... see below.

Answer 1

[James Tursa]

Use the diff( ) function to calculate all of the permutations, and then count the number of valid ones. E.g.,

    P = perms(1:i);
    A(i) = sum(all(diff(P,1,2)<=1,2));

This code will, of course, blow up your RAM for large n.

[badscience]

so in your example, diff(P,1,2) is calculating the difference between adjascent elements of P, and then it is counting the number of times the difference between adjascent elements of P is less than 1?

[badscience]

I just played around with it and got it to work exactly as needed. Thanks for your help, I really appreciate it!

Answer 2

[John D'Errico]

No, it is not possible to set rules on permutations. At least not unless you write the code to compute those permutations. You have several options.

• Generate all permutations, throwing out those that are inadmissable under the rules you have been given. This will fail miserably if the number of elements is at all large. What is large? the number of permutations of n elements is factorial(n). Do you really want to deal with trillions of permutations? 15 is not that many elements either.

factorial(15)
ans =
   1.3077e+12

• Do it constructively. Consider a set like [1 2 3 4 5 6]. Each permutation will start with some element. So which permutations can start with 6? By your rules, that can be ONLY the permutation [6 5 4 3 2 1]. (Not difficult to prove.) Next, which permutations can start with 5? Thus 5 can only be followed by 4 or 6 from that set. But then 6 CANNOT be followed by any other number. So any permutation that starts with 5 can only start [5 4...]. What then can follow 4? Again, you will find only one valid sequence. [5 4 3 2 1 6]. You can use similar logic starting from 4. There you will find sequences like [4 3 2 1 5 6] and [4 3 2 1 6 5]. I'd bet you can see the pattern now.
• At some point, you might think about this as a graph theory problem. Thus for n elements, create the matrix which describes which elements can follow other elements of the set. So G(i,j) = 1 ONLY if element j can follow element i. G(i,j) = 0 otherwise. For the 6 elements [1:6], the matrix decsribing the edges of that graph would be:

G = triu(ones(6),-1) - eye(6)
G =
     0     1     1     1     1     1
     1     0     1     1     1     1
     0     1     0     1     1     1
     0     0     1     0     1     1
     0     0     0     1     0     1
     0     0     0     0     1     0

Now your problem reduces to counting the number of Hamiltonian circuits that exist for that graph.

I imagine there are other ways you could solve this.

[badscience]

I have some code written with help from James in another answer which calculates all permutations and counts the "valid" ones, but as we are aware, this is not really a good method for large n. It workks really well for small n, but my computer starts chugging around n=11. So I am trying to do this constructiveley. I think starting with this graph theory approach as you suggested may be a good idea.

Thanks for the response!