问计数交替排列

EN

交替置换是第一n 整数\{ 1 ... n \} 的置换，使得置换中相邻的值对在增减之间交替(反之亦然)。

等效地，它是一个排列，其中没有一个长度为> 2 的连续递增或递减值的“运行”。

例如，2 4 1 5 3 6是n = 6 的交替排列，因为2 < 4 、4 > 1 、1 < 5 、5 > 3 和3 < 6 ：每对在它们的相对比较中交替。

然而，1 3 2 4 6 5并不是一个有效的交替排列，因为它包含不断增加的序列2 4 6 ( 2 < 4 和4 < 6 )。

在这个挑战中，我们将考虑给定正整数n 的交替排列数。

例如，对于n = 4 ，存在4! = 24 排列，其中10 是交替排列：

1 3 2 4
1 4 2 3
2 1 4 3
2 3 1 4
2 4 1 3
3 1 4 2
3 2 4 1
3 4 1 2
4 1 3 2
4 2 3 1

您可能会注意到，每个置换都有一个副本，正好相反。因此，对于这个挑战，当有一对互为逆转的排列时，你应该只计算一次。

请注意，对于n = 1 ，只有一个置换，只有1，它没有明显的相反。因此，对于n = 1 ，输出仍然是1 。

对于n = 0 ，也只有一个置换，即空置换，但是您不需要处理它(我们只关心n \ge 1 )。

最后，您的任务是输出正整数n 的交替排列数的顺序，不包括反向重复。这个序列开始：

1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765

这是OEIS中的A000111 (在n = 0 之后)，它是A001250 (n = 1 之后)的一半。

规则

• 与标准的序列挑战一样，您也可以选择：
  • 接受一个输入n 并输出序列中的n 第四项
  • 接受一个输入n 并输出第一个n 术语
  • 无限期地输出序列，例如使用生成器

• 您可以使用0 -或1 -indexing
• 您可以使用任何标准I/O法
• 标准漏洞被禁止
• 这是密码-高尔夫，所以以字节为单位的最短代码获胜。