A250035 Number of left-right-balanced permutations of {1, 2, ..., n}.

1, 0, 0, 8, 24, 0, 216, 4608, 20736, 0, 1267200, 30067200, 194918400, 0, 27840153600, 855119462400, 7276643942400, 0, 1869882900480000, 71740296069120000, 754326563880960000, 0, 303064905515581440000, 14020774294498836480000, 175480402397791518720000, 0

Offset

1,4

Comments

A permutation of {1, 2, ..., n} is left-right-balanced if the sum of its left half is equal to the sum of its right half. For example, {1, 4, 2, 3} is a left-right-balanced permutation of {1, 2, 3, 4} because sum( {1, 4} ) is equal to sum( {2, 3} ). Similarly, {1, 5, 3, 2, 4} is a left-right-balanced permutation of {1, 2, 3, 4, 5} because sum( {1, 5} ) is equal to sum( {2, 4} ).

From Robert Israel, Jan 14 2015: (Start)

For even n, a(n) = (n/2)!^2*b(n) where b(n) is the number of subsets of {1,2,...,n} of size n/2 whose sum is n*(n+1)/4. This is 0 if n == 2 mod 4.

For odd n, a(n) = (((n-1)/2)!)^2*Sum_{j=1..n} c(n,j), where c(n,j) is the number of subsets of {1,2,...,n} of size (n-1)/2 whose sum is n*(n+1)/4 - j/2 and which do not contain j.

Here j must be odd if n == 1 mod 4 and even if n == 3 mod 4.

(End)

Links

Robert Israel, Table of n, a(n) for n = 1..90

Robert C. Lyons, Python script, which calculates the terms via brute force.

Example

For n = 3, a(3) = 0 because none of the permutations of {1, 2, 3} are left-right-balanced.
For n = 4, a(4) = 8 because there are 8 left-right-balanced permutations of {1, 2, 3, 4}. One of them is {1, 4, 2, 3} because sum( {1, 4} ) is equal to sum( {2, 3} ).

Maple

S:= proc(n, t, s) option remember;
      if t > n then 0
      elif s > t*(2*n-t+1)/2 then 0
      elif t = 0 then 1
      elif s < n then procname(n-1, t, s)
      else procname(n-1, t, s) + procname(n-1, t-1, s-n)
     fi
end proc:
Sx:= proc(n, t, s, j) option remember;
      if j>=n then S(n-1, t, s)
      elif t > n then 0
      elif s > t*(2*n-t+1)/2 then 0
      elif t = 0 then 1
      elif s < n then procname(n-1, t, s, j)
      else procname(n-1, t, s, j) + procname(n-1, t-1, s-n, j)
     fi
end proc:
A:= proc(n) if n::even then ((n/2)!)^2*S(n, n/2, n*(n+1)/4)
  else (((n-1)/2)!)^2*add(Sx(n, (n-1)/2, n*(n+1)/4 - j/2, j) , j=1..n)
  fi
end proc:
seq(A(n), n=1..50); # Robert Israel, May 17 2015

Mathematica

S[n_, t_, s_] := S[n, t, s] = Which[t > n, 0, s > t(2n - t + 1)/2, 0, t == 0, 1, s < n, S[n-1, t, s], True, S[n-1, t, s] + S[n-1, t-1, s-n]];
Sx[n_, t_, s_, j_] := Sx[n, t, s, j] = Which[j >= n, S[n-1, t, s], t > n, 0, s > t(2n - t + 1)/2, 0, t == 0, 1, s < n, Sx[n-1, t, s, j], True, Sx[n - 1, t, s, j] + Sx[n-1, t-1, s-n, j]];
A[n_] := If[EvenQ[n], ((n/2)!)^2 S[n, n/2, n(n+1)/4], (((n-1)/2)!)^2 Sum[ Sx[n, (n-1)/2, n(n+1)/4 - j/2, j], {j, 1, n}]];
Array[A, 30] (* Jean-François Alcover, Oct 03 2020, after Robert Israel *)

Crossrefs

Cf. A056876.

Sequence in context: A233470 A334720 A172390 * A263630 A205376 A088448

Adjacent sequences: A250032 A250033 A250034 * A250036 A250037 A250038

Keyword

nonn

Author

Robert C. Lyons, Jan 14 2015

Extensions

a(13) to a(26) from Robert Israel, Jan 15 2015

Status

approved