# Please send the proof of no:of ontofunctions. How can get the formula.

Nandana
110 Points
7 years ago
By using Exclusive & Inclusive formula , which states that
if A & B are any 2 sets then cardiality of AUB = card (A) + card (B ) – card (A inter B)
card(AUBUC) = card(A)+card(B)+card(C)-card(A inter B) – card (A inter C)- card (B inter C ) +card (A inter B inter C )
likewise if we derive for n sets then  it will be
card (A1 U A2 U A3 …. An ) = ∑i Ai – ∑i∑ jAi Aj + ∑i∑j∑k AiAjAk – ….+ (A1 inter A2 ...inter An) , by the help of this we can solve the problem
let’s take 2 sets having m, n elements & for on to function m>/=n
if  f : A → B  then total no. of functions possible are n^m but we have to elemenate the functions which do not include one of the “n” elements , so we have to exclude those
for that  nC1 (n-1) ^m , so this will become
n^m – nC1 (n-1)^ m
by taking the two of “m” are range,  then  nC2 (n-2)^m , but now the problem is the terms of
first term also included , that means we are removing one term twice , so we have to add this , likewise , we will continue upto n-1 elements
i.e .  n^m – nC1 (n-1) ^m + nC2 (n-2 )^m – ….… +(-1) ^(n-1) mCm-1  are the possibilities of on to functions possible from A to B
this is also written in simple way
nk=0 (-1) ^k mCk (n-k)^m .