eulerian1 - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim

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.

 See Also