eulerian1 - Maple Help

combinat

 eulerian1
 first order Eulerian numbers

 Calling Sequence eulerian1(n, k)

Parameters

 n, k - non-negative integers

Description

 • The eulerian1(n, k) command counts the number of permutations of ${\mathrm{pi}}_{1}{\mathrm{pi}}_{2}\mathrm{...}{\mathrm{pi}}_{n}$ of $\left\{1,2,\mathrm{...},n\right\}$ that have k ascents, namely, k places where ${\mathrm{pi}}_{j}<{\mathrm{pi}}_{j+1}$.
 • This function can be computed via the recurrence

$\mathrm{eulerian1}\left(n,k\right)=\left(k+1\right)\mathrm{eulerian1}\left(n-1,k\right)+\left(n-k\right)\mathrm{eulerian1}\left(n-1,k-1\right)$

 • It also satisfies the following identities:

${x}^{n}={\sum }_{k=0}^{n}\mathrm{eulerian1}\left(n,k\right)\left(\genfrac{}{}{0}{}{x+k}{n}\right)$

$m!\mathrm{Stirling2}\left(n,m\right)={\sum }_{k=0}^{n}\mathrm{eulerian1}\left(n,k\right)\left(\genfrac{}{}{0}{}{k}{n-m}\right)$

 $\mathrm{eulerian1}\left(n,k\right)$ = ${\sum }_{m=0}^{k}{\left(-1\right)}^{m}\left(\genfrac{}{}{0}{}{n+1}{m}\right){\left(k+1-m\right)}^{n}$ = ${\sum }_{m=0}^{n}{\left(-1\right)}^{n-m-k}m!\left(\genfrac{}{}{0}{}{n-m}{k}\right)\mathrm{Stirling2}\left(n,m\right)$

Examples

 > $\mathrm{with}\left(\mathrm{combinat}\right):$
 > $\mathrm{Matrix}\left(\left[\mathrm{seq}\left(\left[\mathrm{seq}\left(\mathrm{eulerian1}\left(n,k\right),k=0..5\right)\right],n=0..5\right)\right]\right)$
 $\left[\begin{array}{cccccc}{1}& {0}& {0}& {0}& {0}& {0}\\ {1}& {0}& {0}& {0}& {0}& {0}\\ {1}& {1}& {0}& {0}& {0}& {0}\\ {1}& {4}& {1}& {0}& {0}& {0}\\ {1}& {11}& {11}& {1}& {0}& {0}\\ {1}& {26}& {66}& {26}& {1}& {0}\end{array}\right]$ (1)

References

 R.L. Graham, D.E. Knuth, O. Patashnik, "Concrete Mathematics", Addison-Wesley, Reading, Mass., 1989.