some_random_permutations_problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Interesting problem of finding the probability of getting r distinct numbers from n samples!\n",
    "\n",
    "Question: You have a set containing r distinct numbers say 0,1,2,...,r. You pick n (n>r) samples from this set with replacement (Equal probability of picking any number). What is the probability that in these n samples, you will have all of these r distinct numbers. Note: rest (n-r) samples can be anything, we want probability of having atleast r unique samples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from IPython.display import Math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Here, Brute-Force is applied to find the number of sets with 4 distinct numbers.\n",
    "## n = 6, r = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of sets possible with 4 distinct numbers when 6 samples are drawn is 1560.\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "r = 4\n",
    "n = 6\n",
    "for a in range(r):\n",
    "    for b in range(r):\n",
    "        for c in range(r):\n",
    "            for d in range(r):\n",
    "                for e in range(r):\n",
    "                    for f in range(r):\n",
    "                        if(len(np.unique([a,b,c,d,e,f]))==r):\n",
    "                            count += 1\n",
    "#                             print([a,b,c,d])\n",
    "print(\"Number of sets possible with %d distinct numbers when %d samples are drawn is %d.\"%(r,n,count))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Now, we can also calculate it using combintorics for r=4,n=6 i.e. \n",
    "$$\\sum_{i=1}^{n-r+1} \\sum_{j=i+1}^{n-r+2} \\sum_{k=j+1}^{n-r+3} r^i * (r-1)^{j-i} * (r-2)^{k-j} * (r-3)^{n-k}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of sets possible with 4 distinct numbers when 6 samples are drawn is 1560.\n",
      "Probability of getting atleast one unique set is  0.380859375\n"
     ]
    }
   ],
   "source": [
    "r = 4\n",
    "n = 6\n",
    "count = 0\n",
    "for i in range(1, n-r+2):\n",
    "    for j in range(i+1, n-r+3):\n",
    "        for k in range(j+1, n-r+4):\n",
    "            count += r**i * (r-1)**(j-i) * (r-2)**(k-j) * (r-3)**(n-k)\n",
    "print(\"Number of sets possible with %d distinct numbers when %d samples are drawn is %d.\"%(r,n,count))\n",
    "print(\"Probability of getting atleast one unique set of %d numbers is \" %r, count/(r**n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Similarly, for r=3, n=6 the formula is,\n",
    "$$\\sum_{i=1}^{n-r+1} \\sum_{j=i+1}^{n-r+2} \\sum_{k=j+1}^{n-r+3} r^i * (r-1)^{j-i} * (r-2)^{k-j} * (r-3)^{n-k}$$\n",
    "\n",
    "This boils down to:\n",
    "$$\\sum_{i=1}^{n-r+1} \\sum_{j=i+1}^{n-r+2} r^i * (r-1)^{j-i} * (r-2)^{n-j}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of sets possible with 3 distinct numbers when 6 samples are drawn is 540.\n",
      "Probability of getting atleast one unique set of 3 numbers is  0.7407407407407407\n"
     ]
    }
   ],
   "source": [
    "r = 3\n",
    "n = 6\n",
    "count = 0\n",
    "for i in range(1, n-r+2):\n",
    "    for j in range(i+1, n-r+3):\n",
    "        count += r**i * (r-1)**(j-i) * (r-2)**(n-j)\n",
    "print(\"Number of sets possible with %d distinct numbers when %d samples are drawn is %d.\"%(r,n,count))\n",
    "print(\"Probability of getting atleast one unique set of %d numbers is \"%r, count/(r**n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Brute-Force verification for this scenario is simple as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of sets possible with 3 distinct numbers when 6 samples are drawn is 540.\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "r = 3\n",
    "n = 6\n",
    "for a in range(r):\n",
    "    for b in range(r):\n",
    "        for c in range(r):\n",
    "            for d in range(r):\n",
    "                for e in range(r):\n",
    "                    for f in range(r):\n",
    "                        if(len(np.unique([a,b,c,d,e,f]))==r):\n",
    "                            count += 1\n",
    "#                             print([a,b,c,d])\n",
    "print(\"Number of sets possible with %d distinct numbers when %d samples are drawn is %d.\"%(r,n,count))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## We can play around between this, but we need to note that the combinatoric formulation also becomes tedious for large r, though brute force becomes tedious for both large n.\n",
    "\n",
    "## A pattern that can be observed is that, we need to sum r-1 times in combinatoric formulation. This can be extended for large r and large n by adding more summations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}