Eulerian number

Eulerian number

:"This page discusses a topic in combinatorics. For "Euler numbers" in number theory see Euler number."

In combinatorics the Eulerian number "E"("n", "m"), or

:left langle {natop m} ight angle,

is the number of permutations of the numbers 1 to "n" in which exactly "m" elements are greater than the previous element (permutations with "m" "ascents").

Basic properties

For a given value of "n", the index "m" in "E"("n", "m") can take values from 0 to "n" − 1. For fixed "n" there is a single permutation which has 0 ascents; this is the falling permutation ("n", "n" − 1, "n" − 2, ..., 1). There is also a single permutation which has "n" − 1 ascents; this is the rising permutation (1, 2, 3, ..., "n"). Therefore "E"("n", 0) and "E"("n", "n" − 1) are 1 for all values of "n".

Reversing a permutation with "m" ascents creates another permutation in which there are "n" − "m" − 1 ascents. Therefore "E"("n", "m") = "E"("n", "n" − "m" − 1).

Values of "E"("n", "m") can be calculated "by hand" for small values of "n" and "m". For example

:

For larger values of "n", "E"("n", "m") can be calculated using the recursion formula

:E(n,m)=(n-m)E(n-1,m-1) + (m+1)E(n-1,m).

For example

:E(4,1)=(4-1)E(3,0) + (1+1)E(3,1)=3 imes 1 + 2 imes 4 = 11.

Values of "E"("n", "m") up to "n" = 9 are OEIS|id=A008292:

:

The above arrangement is called the Euler triangle or Euler's triangle, and it shares some common characteristics with Pascal's triangle.

Closed-form expression

A closed-form expression for "E"("n", "m") is

:E(n,m)=sum_{k=0}^{m}(-1)^k inom{n+1}{k} (m+1-k)^n.

ummation properties

It is clear from the combinatoric definition that the sum of the Eulerian numbers for a fixed value of "n" is the total number of permutations of the numbers 1 to "n", so

:sum_{m=0}^{n-1}E(n,m)=n!.

The alternating sum of the Eulerian numbers for a fixed value of "n" is related to the Bernoulli number "B""n"+1

:sum_{m=0}^{n-1}(-1)^{m}E(n,m)=frac{2^{n+1}(2^{n+1}-1)B_{n+1{n+1}.

Other summation properties of the Eulerian numbers are:

:sum_{m=0}^{n-1}(-1)^mfrac{E(n,m)}{inom{n-1}{m=0,

:sum_{m=0}^{n-1}(-1)^mfrac{E(n,m)}{inom{n}{m=(n+1)B_{n},

where "B""n" is the "n"th Bernoulli number.

Identities

The Eulerian numbers are involved in the generating function for the sequence of "n"th powers

:sum_{k=1}^{infty}k^n x^k = frac{sum_{m=0}^{n-1}E(n,m)x^{m+1{(1-x)^{n+1.

The Eulerian numbers are also involved in Worpitzky's identity, which expresses "x""n" as the sum of generalised binomial coefficients

:x^n=sum_{m=0}^{n-1}E(n,m)inom{x+m}{n}.

References

*MathWorld|title=Eulerian Number|urlname=EulerianNumber
*MathWorld|title=Worpitzky's Identity|urlname=WorpitzkysIdentity
* [http://www.mathpages.com/home/kmath012/kmath012.htm Eulerian Numbers] at "MathPages"
* [http://www.cecm.sfu.ca/organics/papers/buhler/paper/html/node5.html Counting Periodic Juggling Patterns] by Joe Buhler, David Eisenbud, Ron Graham, Colin Wright
*Graham, Knuth, Patashnik (1994). "Concrete Mathematics: A Foundation for Computer Science", Second Edition. Addison-Wesley, pp. 267–272.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Eulerian path — In graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the …   Wikipedia

  • number game — Introduction       any of various puzzles and games that involve aspects of mathematics.       Mathematical recreations comprise puzzles and games that vary from naive amusements to sophisticated problems, some of which have never been solved.… …   Universalium

  • Euler number — For other uses, see Euler number (topology) and Eulerian number. Also see e (mathematical constant),Euler number (physics) and Euler–Mascheroni constant. In mathematics, in the area of number theory, the Euler numbers are a sequence En of… …   Wikipedia

  • Bernoulli number — In mathematics, the Bernoulli numbers Bn are a sequence of rational numbers with deep connections to number theory. They are closely related to the values of the Riemann zeta function at negative integers. There are several conventions for… …   Wikipedia

  • List of topics named after Leonhard Euler — In mathematics and physics, there are a large number of topics named in honour of Leonhard Euler (pronounced Oiler ). As well, many of these topics include their own unique function, equation, formula, identity, number (single or sequence), or… …   Wikipedia

  • Nombre eulérien —  Ne pas confondre avec e, la base du logarithme naturel, aussi appelée occasionnellement nombre d Euler, ni avec les nombres d Euler. En mathématiques, et plus précisément en analyse combinatoire, le nombre eulérien A(n, m), est le nombre de …   Wikipédia en Français

  • Euler-Zahlen — Die nach Leonhard Euler benannte Euler Zahl An,k in der Kombinatorik, auch geschrieben als E(n,k) oder , ist die Anzahl der Permutationen (Anordnungen) von 1, …, n, in denen genau k Elemente größer als das vorhergehende sind, die also genau k… …   Deutsch Wikipedia

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • Triangular array — Not to be confused with Triangular matrix. The triangular array whose right hand diagonal sequence consists of Bell numbers In mathematics and computing, a triangular array of numbers, polynomials, or the like, is a doubly indexed sequence in… …   Wikipedia

  • Permutation — For other uses, see Permutation (disambiguation). The 6 permutations of 3 balls In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values.… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”