Counting Permutations with Given Number of Ascents

Let a permutation \(P\) of length \(n\) have an ascent at position \(i\) if \(P_i < P_{i+1}\). The number of ascents of \(P\) is the total number of indices \(i\) (with \(1 \le i \le n-1\)) where \(P_i < P_{i+1}\). Note that by definition, the maximum possible number of ascents is \(n-1\); thus for \(k=n\) the answer is always 0.

Given an integer \(n\) representing the length of the permutation, compute, for every integer \(k\) in the range \([0,n]\), the number of permutations whose number of ascents is exactly \(k\). The answer for each \(k\) should be printed in order from \(k=0\) to \(k=n\), separated by spaces.

The calculation involves the Eulerian numbers that satisfy the recurrence:

[ A(n,k)= (n-k) \cdot A(n-1,k-1) + (k+1) \cdot A(n-1,k), \quad \text{with } A(1,0)=1 ]

Note that by convention, \(A(n,k)=0\) for \(k \ge n\).

inputFormat

The input consists of a single integer \(n\) (\(1 \leq n \leq \text{small limit}\)), representing the length of the permutation.

For example:

3

outputFormat

Output \(n+1\) numbers separated by spaces. The \(i\)-th number (starting from index 0) is the number of permutations of \(n\) with exactly \(i\) ascents, for \(i = 0, 1, \dots, n\).

For example, for input 3 the output should be:

1 4 1 0

sample

1

1 0