One‐Pass Bubble Sort Reversal

Problem Description

On Valentine’s Day, Biadocy was treated very badly, and after hearing the upper‐class duke and a child say, "Every day with you is like Valentine’s Day," he finally found a chance to retaliate. He took a line of n lovers numbered from \(1\) to \(n\) arranged in an arbitrary order and ran the following pseudocode on them:

The pseudocode is a single pass of an adjacent-swap sorting algorithm (similar to one pass of bubble sort) defined as follows: for i from 1 to \(n-1\), if the element at position i is greater than the element at position i+1, then swap them. After this pass, the array becomes \(r\). Biadocy wants to know in how many ways the initial permutation can be chosen so that after executing this one pass the resulting sequence is sorted in increasing order, i.e. \(r = [1, 2, \ldots, n]\).

Explanation:

• The algorithm works as follows:
  for \(i = 1\) to \(n-1\):
      if \(a[i] > a[i+1]\) then swap \(a[i]\) and \(a[i+1]\).
• For example, when \(n=3\) the permutation [3, 1, 2] will be processed as:
  i=1: compare 3 and 1 (swap) \(\to [1, 3, 2]\)
  i=2: compare 3 and 2 (swap) \(\to [1, 2, 3]\), which is sorted.

It turns out that a necessary and sufficient condition for the initial permutation \(p\) to become sorted after one pass is that every inversion in \(p\) is corrected by an adjacent swap. Equivalently, the permutation must be one that can be obtained by performing a sequence of adjacent swaps (possibly overlapping) on the sorted array \( [1,2,\dots,n] \) such that the one‐pass procedure exactly reverses the swaps.

A detailed analysis leads to the following recurrence for the number of valid initial permutations \(f(n)\):

[ \begin{cases} f(0)=1,\[6pt] f(1)=1,\[6pt] f(2)=2,\[6pt] f(3)=4,\[6pt] f(n)=2\cdot f(n-2)+2\cdot f(n-3) \quad \text{for } n\ge 4. \end{cases} ]

You are given an integer \(n\) and you must output \(f(n)\): the number of initial permutations of \(\{1, 2, \ldots, n\}\) that will be sorted in exactly one adjacent-swap pass as described above.

inputFormat

The input is a single integer \(n\) (\(1 \le n \le 40\) for example) representing the number of lovers.

outputFormat

Output a single integer: the number of valid initial permutations such that after one pass of the adjacent-swap algorithm the sequence is sorted in increasing order.

sample

1

1