set-partitions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "[//]: # (Long-Title: Set Partitions: Grouping Elements of Sets, Pairwise Disjoint Sets, Properties, Equivalence Classes and Relations, and Bell, Catalan, and Stirling numbers.)\n",
    "    \n",
    "[//]: # (Short-Title: Set Partitions)\n",
    "    \n",
    "[//]: # (Keyword: Set partitions)\n",
    "\n",
    "[//]: # (Keyword: Bell Numbers)\n",
    "    \n",
    "[//]: # (Keyword: Catalan Numbers)\n",
    "    \n",
    "[//]: # (Keyword: Stirling Numbers)\n",
    "    \n",
    "[//]: # (Keyword: Equivalence Class)\n",
    "    \n",
    "[//]: # (Keyword: Equivalence Relations)\n",
    "\n",
    "[//]: # (Keyword: Pairwise Disjoint)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Set Partitions\n",
    "\n",
    "Grouping elements of a set into non-empty subsets in a way that every element is included in exactly one one subset is called partitioning of a set. <br>\n",
    "\n",
    "The intersection of any two subsets in the partition is an empty set. <br> \n",
    "\n",
    "In other words, the subsets in the partition are said to be pairwise disjoint.<br> <br> <br>\n",
    "\n",
    "\n",
    "\n",
    "Example: <br>\n",
    "\n",
    "The set $A = \\{1,2,3\\}$ has the following five partitions: <br>\n",
    "\n",
    "$\\{\\{1\\} , \\{2\\} , \\{3\\}\\}$ is a partition, which is also written as $1|2|3$ <br> <br>\n",
    "\n",
    "The other four partitions are: <br>\n",
    "\n",
    "$\\{\\{1,2\\},\\{3\\}\\}$ or $1 2 | 3$ <br>\n",
    "\n",
    "$\\{\\{1,3\\},\\{2\\}\\}$ or $1 3 | 2$ <br>\n",
    "\n",
    "$\\{\\{1\\},\\{2,3\\}\\}$ or $1 | 3  2$ <br>\n",
    "\n",
    "$\\{\\{1,2,3\\}\\}$ or $1 2 3$  <br>\n",
    "\n",
    "Note : Partitions should not contain the null set, an element should appear in exactly one partition, and every element should appear in same partition. <br> <br> <br>\n",
    "\n",
    "\n",
    "\n",
    "Formally, let $A$ be a set and $A_{1},A_{2},A_{3}, ... ,A_{n}$ be its subsets. the subsets form a partition on $A$, if the following three conditions hold: <br>\n",
    "\n",
    "(1)  $A_{1} \\cup A_{2} \\cup A_{3} \\cup ... \\cup A_{n} = A$ <br>\n",
    "\n",
    "(2)  $A_{i} \\neq \\emptyset$ for all i <br>\n",
    "\n",
    "(3) $A_{i} \\cap A_{j} = \\emptyset$ for all $i \\neq j$ <br> <br> <br>\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Example: <br> \n",
    "\n",
    "Consider the following set of phone numbers (written in a format used in the United States): <br>\n",
    "\n",
    "Phones = {252-328-9680, 704-978-4243, 336-521-1121, 704-888-0102, 336-678-1415, 252-968-1212} <br> \n",
    "\n",
    "We deliver an equivalence relation to decoupe the set into its equivalence classes. <br>\n",
    "\n",
    "Therefore, the equivalence classes are: <br>\n",
    "\n",
    "$\\{252-328-9680, 252-968-1212\\}$ <br>\n",
    "\n",
    "$\\{704-978-4342, 704-888-0102\\}$ <br>\n",
    "\n",
    "$\\{336-521-1121, 336-678-1415\\}$ <br> \n",
    "\n",
    "Note that all elements (i.e., phone numbers) in an equivalence class have the \"same area code.\" <br> <br> <br>\n",
    "\n",
    "\n",
    "\n",
    "Equivalence classes form a partition on the set Phones. <br>\n",
    "\n",
    "The subsets of the partion are: <br>\n",
    "\n",
    "$\\{\\{252-328-9680, 252-968-1212\\}$, <br>\n",
    "\n",
    "$\\{704-978-4342, 704-888-0102\\}$, <br>\n",
    "\n",
    "$\\{336-521-1121, 336-678-1415\\} \\}$ <br> <br> <br>\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Confirm that above subsets are a partition by verifying: <br> <br>\n",
    "\n",
    "$(i)$ Each phone number appears in only one subset. <br> <br>\n",
    "$(ii)$ Every phone number appears in same subset. <br> <br> \n",
    "$(iii)$ No subset is a null set. <br> <br> \n",
    "\n",
    "We also verify that the relation \"same area code\" is an equivalence on the set Phones. <br> <br> <br>\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "A relation R on a set A is an equivalence relation if it has the following three properties: <br> <br>\n",
    "\n",
    "$(i)$ Reflexive, if $x \\in A$, then $(x,x) \\in R$ <br> <br>\n",
    "\n",
    "$(ii)$ Symmetric, if $(x,y) \\in R$, then $(y,x) \\in R $ <br> <br>\n",
    "\n",
    "$(iii)$ Transitive, if $(x,y) \\in R$ and if $(y,z) \\in R$, then $(x,z) \\in R$ <br> <br> <br>\n",
    "\n",
    "\n",
    "\n",
    "It is easy to verify that the relation \"Same area code\" satisfies all three properties, hence, it is an equivalence relation. <br>\n",
    "\n",
    "The relation is reflexive. Let $x$ be any element of the set phones. It is obvious that any phone number and itself will have the same area code. <br>\n",
    "\n",
    "The relation is symmetric. Let $x$ and $y$ be any two elements of the set Phones, if $x$ and $y$ have the same area code, it is also true that $y$ and $x$ have the same area code. <br>\n",
    "\n",
    "The relation is transitive. Let $x$, $y$ and $z$ be any three elements of the set phones.<br>\n",
    "\n",
    "If $x$ and $y$ have the same area code and $y$ and $z$ have the same area code, then $x$ and $z$ must have the same area code.(by transitive properties). <br> <br> <br>\n",
    "\n",
    "\n",
    "\n",
    "The total number of partitions of an n-element set is the Bell number, $B_{n}$ <br>\n",
    "\n",
    "The first few Bell numbers are $B_{0} = 1,B_{1} = 1,B_{2} = 2,B_{3} = 5,B_{4} = 15$ and $B_{5} = 52$ <br> \n",
    "\n",
    "Bell numbers satisfies the recursion <br>\n",
    "\n",
    "$$B_{n+1} = \\sum_{k=0}^{n}\\binom{n}{k}B_{k}$$ <br> \n",
    "\n",
    "Note: $\\binom{n}{k}$ is the binomial coefficience and is given by $\\binom{n}{k} = \\frac{n!}{k!(n-k)!}$ <br> <br> <br>\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "The Stirling number of the second kind (or Stirling partition number) gives the number of ways to partition a set of $n$ objects into $k$ non-empty subsets, denoted $S(n,k)$. <br> \n",
    "\n",
    "$S(n,k)$ is computed as: <br>\n",
    "\n",
    "$$s(n,k) = \\frac{1}{k!}\\sum_{i=0}^{k}(-1)^{i}\\binom{k}{i}(k-i)^{n}$$ <br> \n",
    "\n",
    "A non-crossing partition of a set $A$ is a partition in which no two blocks \"cross\" each other. <br> <br>\n",
    "\n",
    "\n",
    "\n",
    "If the elements $a$ and $b$ belongs to one block and elements $i$ and $j$ belongs to another block, then $a$ $i$ $b$ $j$ is a crossing partition whereas $a$ $i$ $j$ $b$ and $a$ $b$ $i$ $j$ are noncrossing. <br>\n",
    "\n",
    "Note: $a$ $i$ $j$ $b$ is non-crossing as the arches connecting $a$ and $b$, and $i$ and $j$ do not cross each other. <br> <br>\n",
    "\n",
    "\n",
    "\n",
    "The Catalan number, denoted $C_{n}$, gives the number of non-crossing partitions of an n-element set <br>\n",
    "\n",
    "$$C_{n} = \\frac{1}{n+1}\\binom{2n}{n}$$ <br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Edit Metadata",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}