Then I was studying at 11th std when we were being introduced to 'Sets' my maths tutor at P.C.Thomas Classes told me that there was no 'real' formula for finding the number of partitions for a set of $x$ elements.But then I came across the Bell number which gave the number of partitions as a recurrence series.
But still I was not satisfied, Bell number was not really a formula and there was no explanation why it represent the number of partitions.
Nearly a year passed by, I learned many new things which included functions. Suddenly I had a insight that Surjective funtions beared a close relationship with set partitions.
Finally I arrived a the summation formula:
.jpg)
Proof:
A function $f:X->Y$ is said to be surjective if every element of $Y$ is a image of some element of $X$ .
($x$ & $y$ are respectively the number of elements in $X$ & $Y$).$\left ( x\geq y \right )$
The surjective functions are chosen because it is similar to the condition that partitions are non-empty subsets i.e. we assume elements of $y$ to be the subsets and we map the elements of $x$ to it.
We now find the number of surjections.(I'll add proof later)
The number of surjections is found to be:
$S(x,y)=\binom{y}{0}(y)^x-\binom{y}{1}(y-1)^x+\binom{y}{2}(y-2)^x-\binom{y}{3}(r-3)^x....$
$=\sum_{n=0}^{y-1}(-1)^n\binom{y}{n}(y-n)^x$
But there is a small problem in considering surjective functions for representing partitions of a set.A particular way of partitioning is represented $y!$ times.
So we need to divide $S(x,y)$ with $y!$ to obtain the number of partitions of $X$ into $y$ subsets.
$\frac{S(x,y)}{y!}$
Now to obtain the total number of partitions, we have to consider partitions having $1$ subset to $x$ subsets.
Therefore number of partitions is given by:
$\sum_{y=1}^{x}\frac{S(x,y)}{y!}=\sum_{y=1}^{x}\frac{\sum_{n=0}^{y-1}(-1)^n\binom{y}{n}(y-n)^x}{y!}$
But still I was not satisfied, Bell number was not really a formula and there was no explanation why it represent the number of partitions.
Nearly a year passed by, I learned many new things which included functions. Suddenly I had a insight that Surjective funtions beared a close relationship with set partitions.
Finally I arrived a the summation formula:
Where $x$ is the number of elements in the set.
Proof:
A function $f:X->Y$ is said to be surjective if every element of $Y$ is a image of some element of $X$ .
($x$ & $y$ are respectively the number of elements in $X$ & $Y$).$\left ( x\geq y \right )$
The surjective functions are chosen because it is similar to the condition that partitions are non-empty subsets i.e. we assume elements of $y$ to be the subsets and we map the elements of $x$ to it.
We now find the number of surjections.(I'll add proof later)
The number of surjections is found to be:
$S(x,y)=\binom{y}{0}(y)^x-\binom{y}{1}(y-1)^x+\binom{y}{2}(y-2)^x-\binom{y}{3}(r-3)^x....$
$=\sum_{n=0}^{y-1}(-1)^n\binom{y}{n}(y-n)^x$
But there is a small problem in considering surjective functions for representing partitions of a set.A particular way of partitioning is represented $y!$ times.
So we need to divide $S(x,y)$ with $y!$ to obtain the number of partitions of $X$ into $y$ subsets.
$\frac{S(x,y)}{y!}$
Now to obtain the total number of partitions, we have to consider partitions having $1$ subset to $x$ subsets.
Therefore number of partitions is given by:
$\sum_{y=1}^{x}\frac{S(x,y)}{y!}=\sum_{y=1}^{x}\frac{\sum_{n=0}^{y-1}(-1)^n\binom{y}{n}(y-n)^x}{y!}$
No comments:
Post a Comment