Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Falling and rising factorials
Summary
In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial
The rising factorial (sometimes called the Pochhammer function, Pochhammer polynomial, ascending factorial, rising sequential product, or upper factorial) is defined as
The value of each is taken to be 1 (an empty product) when These symbols are collectively called factorial powers.
The Pochhammer symbol, introduced by Leo August Pochhammer, is the notation (x)_n , where n is a non-negative integer. It may represent either the rising or the falling factorial, with different articles and authors using different conventions. Pochhammer himself actually used (x)_n with yet another meaning, namely to denote the binomial coefficient
In this article, the symbol (x)_n is used to represent the falling factorial, and the symbol x^(n) is used for the rising factorial. These conventions are used in combinatorics,
although Knuth's underline and overline notations and are increasingly popular.
In the theory of special functions (in particular the hypergeometric function) and in the standard reference work Abramowitz and Stegun, the Pochhammer symbol (x)_n is used to represent the rising factorial.
When x is a positive integer, (x)_n gives the number of n-permutations (sequences of distinct elements) from an x-element set, or equivalently the number of injective functions from a set of size n to a set of size x. The rising factorial x^(n) gives the number of partitions of an n-element set into x ordered sequences (possibly empty).
The first few falling factorials are as follows:
The first few rising factorials are as follows:
The coefficients that appear in the expansions are Stirling numbers of the first kind (see below).
When the variable x is a positive integer, the number (x)_n is equal to the number of n-permutations from a set of x items, that is, the number of ways of choosing an ordered list of length n consisting of distinct elements drawn from a collection of size x.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (6)
Related concepts (28)
Stirling's approximation
In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of . It is named after James Stirling, though a related but less precise result was first stated by Abraham de Moivre. One way of stating the approximation involves the logarithm of the factorial: where the big O notation means that, for all sufficiently large values of , the difference between and will be at most proportional to the logarithm.
Generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers (an) by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem.
Stirling numbers of the first kind
In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed points as cycles of length one). The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices. This article is devoted to specifics of Stirling numbers of the first kind.
Related courses (4)
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
CS-320: Computer language processing
We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in
ME-201: Continuum mechanics
Continuum conservation laws (e.g. mass, momentum and energy) will be introduced. Mathematical tools, including basic algebra and calculus of vectors and Cartesian tensors will be taught. Stress and de
Related lectures (36)
Environment instead of SubstitutionsCS-210: Functional programming
Presents an environment-based interpreter for recursive functions, optimizing evaluation through parameter bindings and eliminating the need for explicit substitutions.
Complexity of Algorithms: Advanced Big-O FactsCS-101: Advanced information, computation, communication I
Covers big-O estimates for factorial function and combinations of functions.
Combinatorics: Counting MethodsMATH-236: Probability and statistics II
Introduces combinatorics and counting methods for determining possible outcomes in various scenarios, illustrated with examples.