计算欧拉数

Question

欧拉数 A(n, m)是[1, 2, ..., n]的排列数，确切地说，m元素大于前一个元素。这些也被称为上升。例如，如果是n = 3，则[1, 2, 3]的排列数为3！=6

1 2 3
 < <  2 elements are greater than the previous

1 3 2
 < >  1 ...

2 1 3
 > <  1 ...

2 3 1
 < >  1 ...

3 1 2
 > <  1 ...

3 2 1
 > >  0 ...

因此，A(3, m)在[0, 1, 2, 3]中的m输出将是

A(3, 0) = 1
A(3, 1) = 4
A(3, 2) = 1
A(3, 3) = 0

另外，这是OEIS序列A173018。

规则

• 这是密码-高尔夫，所以最短的代码获胜。
• 输入的n将是非负整数，而m将是范围[0, 1, ..., n]中的整数。

测试用例

n   m   A(n, m)
0   0   1
1   0   1
1   1   0
2   0   1
2   1   1
2   2   0
3   0   1
3   1   4
3   2   1
3   3   0
4   0   1
4   1   11
4   2   11
4   3   1
4   4   0
5   1   26
7   4   1191
9   5   88234
10  5   1310354
10  7   47840
10  10  0
12  2   478271
15  6   311387598411
17  1   131054
20  16  1026509354985
42  42  0

Answer 1

果冻，8 字节数

Œ!Z>2\Sċ

在网上试试！ (需要一段时间)或验证较小的测试用例。

是如何工作的

Œ!Z>2\Sċ  Main link. Arguments: n, m

Œ!        Generate the matrix of all permutations of [1, ..., n].
  Z       Zip/transpose, placing the permutations in the columns.
   >2\    Compare columns pairwise with vectorizing greater-than.
          This generates a 1 in the column for each rise in that permutation.
      S   Compute the vectorizing sum of the columns, counting the number of rises.
       ċ  Count how many times m appears in the computed counts.

Answer 2

马蒂尔，10字节

:Y@!d0>s=s

在网上试试！

解释

以输入n=3，m=1为例。您可以放置一个%符号，从那时起注释掉代码，从而看到中间结果。例如，链接显示第一步之后的堆栈。

:      % Input n implicitly. Push [1 2 ... n]
       % STACK: [1 2 ... n]
Y@     % Matrix of all permutations, one on each row
       % STACK: [1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1]
!      % Transpose
       % STACK: [1 1 2 2 3 3; 2 3 1 3 1 2; 3 2 3 1 2 1]
d      % Consecutive differences along each column
       % STACK: [1 2 -1 1 -2 -1; 1 -1 2 -2 1 -1]
0>     % True for positive entries
       % STACK: [1 1 0 1 0 0; 1 0 1 0 1 0]
s      % Sum of each column
       % STACK: [2 1 1 1 1 0]
=      % Input m implicitly. Test each entry for equality with m
       % STACK: [0 1 1 1 1 0]
s      % Sum. Implicitly display
       % STACK: 4

Answer 3

Python，53字节

t=lambda n,k:n and(n-k)*t(n-1,k-1)-~k*t(n-1,k)or k==0

来自OEIS的递归。将布尔True输出为1 (当n==k时)。