# Difference between revisions of "Factorial"

(problems) |
|||

Line 1: | Line 1: | ||

The '''factorial''' is an important function in [[combinatorics]] and [[analysis]], used to determine the number of ways to arrange objects. | The '''factorial''' is an important function in [[combinatorics]] and [[analysis]], used to determine the number of ways to arrange objects. | ||

− | + | == Definition == | |

The factorial is defined for [[positive integer]]s as <math>n!=n \cdot (n-1) \cdots 2 \cdot 1 = \prod_{i=1}^n i</math>. Alternatively, a [[recursion|recursive definition]] for the factorial is <math>n!=n \cdot (n-1)!</math>. | The factorial is defined for [[positive integer]]s as <math>n!=n \cdot (n-1) \cdots 2 \cdot 1 = \prod_{i=1}^n i</math>. Alternatively, a [[recursion|recursive definition]] for the factorial is <math>n!=n \cdot (n-1)!</math>. | ||

− | + | == Additional Information == | |

By [[mathematical convention|convention]], <math>0!</math> is given the value <math>1</math>. | By [[mathematical convention|convention]], <math>0!</math> is given the value <math>1</math>. | ||

Line 11: | Line 11: | ||

The [[gamma function]] is a generalization of the factorial to values other than [[nonnegative integer]]s. | The [[gamma function]] is a generalization of the factorial to values other than [[nonnegative integer]]s. | ||

− | == | + | ==Prime Factorization== |

− | + | {{main|Prime factorization}} | |

Since <math>n!</math> is the product of all positive integers not exceeding <math>n</math>, it is clear that it is divisible by all | Since <math>n!</math> is the product of all positive integers not exceeding <math>n</math>, it is clear that it is divisible by all | ||

primes <math>p\le n</math>, and not divisible by any prime <math>p>n</math>. But what is the power of a prime <math>p\le n</math> | primes <math>p\le n</math>, and not divisible by any prime <math>p>n</math>. But what is the power of a prime <math>p\le n</math> | ||

Line 27: | Line 27: | ||

(<math>7^3=343</math> is already greater than <math>100</math>). | (<math>7^3=343</math> is already greater than <math>100</math>). | ||

− | + | == Uses == | |

The factorial is used in the definitions of [[combinations]] and [[permutations]], as <math>n!</math> is the number of ways to order <math>n</math> distinct objects. | The factorial is used in the definitions of [[combinations]] and [[permutations]], as <math>n!</math> is the number of ways to order <math>n</math> distinct objects. | ||

− | === | + | ==Problems== |

+ | ===Introductory=== | ||

+ | *{[{intro}}} | ||

+ | ([[2007 iTest Problems/Problem 6|Source]]) | ||

+ | ===Intermediate=== | ||

+ | *Let <math>P </math> be the product of the first <math>100</math> [[positive integer | positive]] [[odd integer]]s. Find the largest integer <math>k </math> such that <math>P </math> is divisible by <math>3^k .</math> | ||

+ | ([[2006 AIME II Problems/Problem 3|Source]]) | ||

+ | ===Olympiad=== | ||

+ | *Let <math>p_n (k) </math> be the number of permutations of the set <math>\{ 1, \ldots , n \} , \; n \ge 1 </math>, which have exactly <math>k </math> fixed points. Prove that <center><math>\sum_{k=0}^{n} k \cdot p_n (k) = n!</math>.</center> | ||

+ | ([[1987 IMO Problems/Problem 1|Source]]) | ||

− | |||

− | |||

− | === See | + | === See Also == |

*[[Combinatorics]] | *[[Combinatorics]] | ||

+ | |||

+ | [[Category:Combinatorics]] |

## Revision as of 21:00, 14 January 2008

The **factorial** is an important function in combinatorics and analysis, used to determine the number of ways to arrange objects.

## Contents

## Definition

The factorial is defined for positive integers as . Alternatively, a recursive definition for the factorial is .

## Additional Information

By convention, is given the value .

The gamma function is a generalization of the factorial to values other than nonnegative integers.

## Prime Factorization

*Main article: Prime factorization*

Since is the product of all positive integers not exceeding , it is clear that it is divisible by all primes , and not divisible by any prime . But what is the power of a prime in the prime factorization of ? We can find it as the sum of powers of in all the factors ; but rather than counting the power of in each factor, we shall count the number of factors divisible by a given power of . Among the numbers , exactly are divisible by (here is the floor function). The ones divisible by give one power of . The ones divisible by give another power of . Those divisible by give yet another power of . Continuing in this manner gives

for the power of in the prime factorization of . The series is formally infinite, but the terms converge to rapidly, as it is the reciprocal of an exponential function. For example, the power of in is just ( is already greater than ).

## Uses

The factorial is used in the definitions of combinations and permutations, as is the number of ways to order distinct objects.

## Problems

### Introductory

- {[{intro}}}

(Source)

### Intermediate

- Let be the product of the first positive odd integers. Find the largest integer such that is divisible by

(Source)

### Olympiad

- Let be the number of permutations of the set , which have exactly fixed points. Prove that
.

(Source)