combinat - Maple Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : combinat : combinat/eulerian1

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}\phantom{\rule[-0.0ex]{5.0px}{0.0ex}}\mathrm{eulerian1}\left(n,k\right)\mathrm{binomial}\left(x+k,n\right)$

$m!\mathrm{Stirling2}\left(n,m\right)={\sum }_{k=0}^{n}\phantom{\rule[-0.0ex]{5.0px}{0.0ex}}\mathrm{eulerian1}\left(n,k\right)\mathrm{binomial}\left(k,n-m\right)$

 $\mathrm{eulerian1}\left(n,k\right)$ = ${\sum }_{m=0}^{k}\phantom{\rule[-0.0ex]{5.0px}{0.0ex}}{\left(-1\right)}^{m}\mathrm{binomial}\left(n+1,m\right){\left(k+1-m\right)}^{n}$ = ${\sum }_{m=0}^{n}\phantom{\rule[-0.0ex]{5.0px}{0.0ex}}{\left(-1\right)}^{n-m-k}m!\mathrm{binomial}\left(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}{rrrrrr}{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.