An exploration of https://oeis.org/A001761 in Haskell.

A001761.hs

import Text.Printf (printf)
import Data.List (insertBy, delete)

-- Problem
-- ========
--
-- Using numbers `[1...n]`, form all sequences of length `2 * n` such that:
--
--   1. Every number appears exactly twice.
--   2. For any x < y, both occurrences of x must either precede or follow the
--      second occurrence of y.
--
-- Solution
-- ========
--
-- We maintain two sets of numbers as the current state: the set of "unstarted
-- events" has all the numbers that haven't occurred at all so far, and the set
-- of "started events" are the numbers that have occurred exactly once.
--
-- From the current state, either of the following may happen:
--
-- 1. the least number in the set of started events may "end", i.e. occur the
--    second time and delete from the set of started events, or
-- 2. any of the unstarted events may start, i.e. occur the first time and thus
--    move to the set of started events.
--
-- The following code actually represents the latter occurrence of a number with
-- its negative counterpart to make it easier to distinguish when the pair ends.
-- For an answer to the original problem, replace `perms` with
-- `map (map abs) . perms`.
perms :: Int -> [[Int]]
perms n = permsFrom [1..n] []

-- permsFrom unstarted started = [permutation0, permutation1, ...]
permsFrom :: [Int] -> [Int] -> [[Int]]
permsFrom [] ys = [ys]
permsFrom xs ys = ending ys ++ [x:ns | x <- xs, ns <- starting x]
    where
        starting x = permsFrom (delete x xs) $ insertBy (flip compare) (-x) ys
        ending []     = []
        ending (z:zs) = [z:ns | ns <- permsFrom xs zs]

-- Compute `length . perms` or the number of sequences that would be returned by
-- `perms n` for the given `n`. The result is equal to `(2 * n)! / (n + 1)!`.
-- See: https://oeis.org/A001761
nPerms :: Integer -> Integer
nPerms n = (2 * n) `nPr` pred n

-- The binomial coefficient, or the `r`-permutations of `n`.
nCr :: Integer -> Integer -> Integer
n `nCr` 0 = 1
n `nCr` r | n < r = 0
          | r < 0 = 0
          | otherwise = (pred n `nCr` pred r) * n `div` r

-- The `r`-permutations of `n`.
nPr :: Integer -> Integer -> Integer
n `nPr` 0 = 1
n `nPr` r | n < r = 0
          | r < 0 = 0
          | otherwise = (pred n `nPr` pred r) * n

-- Print the solution for a given number `n`. It's a good idea to keep `n`
-- smaller than 7, as the number of permutations will grow explosively fast.
example :: Int -> IO ()
example = putStr . unlines . map (unwords . map (printf "% 3d")) . perms

-- Print the result for `n = 6`.
main :: IO ()
main = example 6