eulerian2 - Maple Help

combinat

 eulerian2
 second order Eulerian numbers

 Calling Sequence eulerian2(n, k)

Parameters

 n, k - non-negative integers

Description

 • The eulerian2(n, k) command counts the number of permutations ${\mathrm{pi}}_{1}{\mathrm{pi}}_{2}\mathrm{...}{\mathrm{pi}}_{2n}$ of the multi-set $\left[1,1,2,2,\mathrm{...},n,n\right]$ having two properties:
 1 All numbers between the two occurrences of $m$ are greater than $m$.
 2 There are k ascents, namely, k places where ${\mathrm{pi}}_{j}<{\mathrm{pi}}_{j+1}$.
 • This function can be computed via the recurrence

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

 • Second-order Eulerian numbers are important because of their connection with Stirling numbers. For integers $m$ and $0\le n$ we have:

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

 $\left|\mathrm{Stirling1}\left(m,m-n\right)\right|$ = ${\left(-1\right)}^{n}\mathrm{Stirling1}\left(m,m-n\right)$ = ${\sum }_{k=0}^{n}\mathrm{eulerian2}\left(n,k\right)\left(\genfrac{}{}{0}{}{m+k}{2n}\right)$

Examples

 > $\mathrm{with}\left(\mathrm{combinat}\right):$
 > $\mathrm{Matrix}\left(\left[\mathrm{seq}\left(\left[\mathrm{seq}\left(\mathrm{eulerian2}\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}& {2}& {0}& {0}& {0}& {0}\\ {1}& {8}& {6}& {0}& {0}& {0}\\ {1}& {22}& {58}& {24}& {0}& {0}\\ {1}& {52}& {328}& {444}& {120}& {0}\end{array}\right]$ (1)

References

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