Permutations Of Small And Large Elements

If the array is : 2,3,7,9; then the ways in which we can have permutations are: 2 7 3 9 2 9 3 7 3 7 2 9 3 9 2 7 7 9 2 3 so total ways are 5. Here the restriction is : Once an el

Solution 1:

This kind of permutation is called zigzag or alternating permutations

It is known that the number of such permutations of n elements might be described with recurrent formula:

A(n+1) = Sum(k=0..n){C(n,k)*A(k)*A(n-k)} / 2

where A(n) is number of permutation of n items, initial A[] = 1, C(n,k) is binomial coefficient

So we can fill array with calculated entries step-by step

functioncnk(n, k) {
  let res = 1;
  for (let i = 0; i < k; i++) 
    res = res * (n - i) / (i + 1);
  return res;
}

let m = 15;
let A = [1,1];
for (let i = 0; i < m-1; i++) {
  A.push(0);
}

for (let n = 2; n < m; n++) 
  for (let k = 0; k <= n; k++) 
    A[n + 1] += A[k] * A[n - k] * cnk(n, k) / 2;
    
console.log(A);

[1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765,
 22368256, 199360981, 1903757312]