The FACTORIAL

 The sign ! After a positive integer is a very familiar sight for the students of elementary mathematics.

Factorial is defined only for positive integers, for a positive integer say n, its factorial value is represented as

 n! = 1*2*3.....*(n-1)*n

Factorial is the heartbeat of the counting problems i.e permutations and combinations and thats why it is so important to pay it a little more attention. We will start with some important attributes of factorials.

1. Factorial n represents the total number of ways in which any n distinct objects can be arranged in a row.

it is easy to deduce , let the positions be numbered from 1 to n , then first object can be placed in n number of ways, second object can be placed in (n-1) remaining number of ways..and so on so that for the last object only one place will be left.

Therefore total number of ways will be 

= n*(n-1)*......*3*2*1 = n!

Now again lets say we want to choose any r objects at a time from the above given group of n distinct objects, (n > r) .Then in how many ways it can be done? Here we are not talking about the order of placement of the chosen r objects.

Most of us know that answer to this is  n!/r!(n-r)! Which is also written as nCr and read as number of r-combination of the set to n distinct objects.

For proof , lets say that x is the desired number, then it is the number of ways in which r objects can be selected from the set of n distinct objects.

Lets take a single set to r such objects, these objects can be arranged among themselves in r! ways, and the remaining (n-r) objects can be arranged in (n-r)! ways, so total number of arrangements will be x*r!*(n-r)! Which happens to be equal to n! and that will give x, which is written as nCr.

2. The Product of any r consecutive integers is always divisible by r!

For proof lets say n is some positive integer and N is the product, i.e N=n*(n+1)*(n+2)*.....*(n+r-1)

N= (n+r-1)!/ (n-1)!

N/r! = (n+r-1)! * r! / (n-1)! = n+r-1 C r = An Integer, Which implies that N is divisible by r!

Here our proof is counting based because essentially we have equated the term N/r! To the number of ways in which r objects can be chosen from the set of (n+r-1) distinct objects.

Based on this it can be proved that if a is an odd number then , expression a(a^2 - 1) is divisible by 24 or 24|a(a^2 - 1)

3. n! also represent the total number of bijections possible from a set A to set B, each having n elements. A bijection is one-to-one and onto function.

A ={a1,a2,.......an} and B={b1,b2.......bn}

A function f is a bijection from set A to B if each element of set A is mapped uniquely to an element of set B. The mapping is one-to-one.

In general set A may be taken to have n elements and set B to have m elements. Then total number of functions possible from A to B is (m^n), it is just because every element of set A can be mapped in m ways. But the quantity (m^n) represents all the possible functions from A to B so to get the number of familiar type of functions from A to B , like the Total number of onto or one-to-one functions from A to B require further working.

4. Unique Prime factorization of n! 

A famous result is about the power of a prime number in the n!, let p be a prime number and we want to find out its highest power which divides the n!, then it is

= [n/p] + [n/p^2] +[n/p^3]+......

Where [  ] is the greatest integer function. 

In essence the number n! can be written as a product of powers of some prime numbers because of the fundamental theorem of arithmetic. 

The above formula precisely gives the value of that power for the corresponding prime number. 

Now If we take the number nCr, which is a positive integer as we all know since it has combinatorial significance. If nCr is an odd number then it means that its unique prime factorization doesnt contain the term 2 which translates into the following

Powers of 2 in n! = Powers of 2 in r! + Powers of 2 in (n-r)!

Let a = [n/2] + [n/4] + [n/8] +.....

b = [r/2] + [r/4] + [r/8] +.....

c = [n-r/2] + [n-r/4] + [n-r/8] +.....

So nCr is odd if a = b + c

nCr is even when  a > b + c

(Kindly note here that case  a < b + c doesn't happen in case you are wondering)

A bit generalization, instead of 2 lets take some prime p and let

a = [n/p] + [n/p^2] + [n/p^3] +.....

b = [r/p] + [r/p^2] + [r/p^3] +.....

c = [n-r/p] + [n-r/p^2] + [n-r/p^3] +.....

Then if a = b + c, then p doesn't divide nCr, i.e 'p' doesnt feature in the unique prime factorization of nCr.

Otherwise the term p^(a-b-c) will feature in the unique prime factorization of nCr.

(To be Contd...that was brief, will cover each point separately in detail)