PKxIoO= Discrete Mathematics/Ch1_1.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter1 - Set Theory"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex1.7 Pg 9"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"To find : number of mathematics students taking atleast one of the languages French(F),German(G) and Russian(R)\n",
"the number of students studying atleast one of the languages : 100\n"
]
}
],
"source": [
"print 'To find : number of mathematics students taking atleast one of the languages French(F),German(G) and Russian(R)'\n",
"F=65# #number of students studying French\n",
"G=45# # number of students studying German\n",
"R=42# #number of students studying Russian\n",
"FandG=20# #number of students studying French and German\n",
"FandR=25# #number of students studying French and Russian\n",
"GandR=15# #number of students studying German and Russian\n",
"FandGandR=8# #number of students studying French,German and Russian\n",
"#By inclusion-exclusion principle\n",
"ForGorR=F+G+R-FandG-FandR-GandR+FandGandR#\n",
"print 'the number of students studying atleast one of the languages :',ForGorR\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex1.8 Pg 10"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"In a college, 120 mathematics students can opt for either French(F),German(G) or Russian(R)\n",
"using inclusion-exclusion principle:\n",
"number of students studying French or German or Russian 100\n",
"number of students studying French and German but not Russian 12\n",
"number of students studying French and Russian but not German 17\n",
"number of students studying German and Russian but not French 7\n",
"number of students studying Only French 28\n",
"number of students studying Only German 18\n",
"number of students studying Only Russian 10\n",
"number of students not studying any of the languages 20\n"
]
}
],
"source": [
"print 'In a college, 120 mathematics students can opt for either French(F),German(G) or Russian(R)'\n",
"n=120# #total number of students\n",
"F=65# #number of students studying French\n",
"G=45# #number of students studying German\n",
"R=42# #number of students studying Russian\n",
"FandG=20# #number of students studying French and German\n",
"FandR=25# #number of students studying French and Russian\n",
"GandR=15# #number of students studying German and Russian\n",
"FandGandR=8# #number of students studying French,German and Russian\n",
"print 'using inclusion-exclusion principle:'\n",
"ForGorR=F+G+R-FandG-FandR-GandR+FandGandR# \n",
"print 'number of students studying French or German or Russian',ForGorR\n",
"FGnR=FandG-FandGandR# \n",
"print 'number of students studying French and German but not Russian',FGnR\n",
"FRnG=FandR-FandGandR #\n",
"print 'number of students studying French and Russian but not German',FRnG\n",
"GRnF=GandR-FandGandR # \n",
"print 'number of students studying German and Russian but not French',GRnF\n",
"OF=F-FGnR-FandGandR-FRnG # \n",
"print 'number of students studying Only French',OF\n",
"OG=G-FGnR-FandGandR-GRnF# \n",
"print 'number of students studying Only German',OG\n",
"OR=R-FRnG-FandGandR-GRnF# \n",
"print 'number of students studying Only Russian',OR\n",
"k=n-ForGorR# \n",
"print 'number of students not studying any of the languages',k\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex1.13 Pg 12"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"number of members of powerset P which are proper subsets of x are: 1023\n"
]
}
],
"source": [
"x=10# #number of members of set X\n",
"P=2**x #number of members of the power set of X\n",
"q=P-1##x itself is not the proper subset.Hence it isn't counted\n",
"print 'number of members of powerset P which are proper subsets of x are:',q"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex1.14 Pg 12"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"number of different salads that can be prepared using the given eatables 31\n"
]
}
],
"source": [
"A=[1,2,3,4,5]# #eatables for salad preparation 1=onion,2=tomato,3=carrot,4=cabbage,5=cucumber\n",
"p=len(A)# #total number of eatables available \n",
"n=2**p-1# #no salad can be made without atleast one of the eatables.Hence null set isn't counted\n",
"print 'number of different salads that can be prepared using the given eatables',n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex1.18 Pg 13"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"P(1) 1\n",
"P(2) 5\n",
"P(1)=U(1) and P(2)=U(2)\n",
"hence Un=3**n-2**n for all n belonging to N\n"
]
}
],
"source": [
"U1=1# #given\n",
"U2=5# #given\n",
"P=[]#\n",
"for I in range(0,2):\n",
" i=I+1\n",
" P.append(3**i-2**i)\n",
" print \"P(%s)\"%(i),P[I]\n",
"print 'P(1)=U(1) and P(2)=U(2)'#\n",
"print 'hence Un=3**n-2**n for all n belonging to N'"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
PKxIT4E;; Discrete Mathematics/Ch3_1.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter3 - Functions & Algorithms"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex3.8 Pg 60"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"the value of 4! is : 24\n"
]
}
],
"source": [
"def recur_factorial(n):\n",
" if n == 1:\n",
" return n\n",
" else:\n",
" return n*recur_factorial(n-1)\n",
"\n",
"a=4\n",
"p=recur_factorial(a)\n",
"print 'the value of 4! is : ',p\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex3.10 Pg 63"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"the polynomial(p) is : 2*x**3 - 7*x**2 + 4*x - 15\n",
"f(a) at a= 5 is : 80\n"
]
}
],
"source": [
"from sympy import symbols, solve\n",
"x = symbols('x')\n",
"p = 2*x**3-7*x**2+4*x-15\n",
"print 'the polynomial(p) is : ',p\n",
"# Let x=5\n",
"x=5\n",
"p = 2*x**3-7*x**2+4*x-15\n",
"print \"f(a) at a= 5 is : \",p\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
PKxI͝&& Discrete Mathematics/Ch5_1.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter 5 - Vectors & Matrices"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex5.2 Pg 103"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"u+v = [[ 3 -2 4]]\n",
"5*u = [[ 10 15 -20]]\n",
"-v = [[-1 5 -8]]\n",
"2*u-3*v = [[ 1 21 -32]]\n",
"dot product of the two vectors, k = u.v = [[-45]]\n",
"norm or length of the vector u = 5.3852\n"
]
}
],
"source": [
"from __future__ import division\n",
"from numpy.linalg import det,norm\n",
"from numpy import mat, add, dot, multiply, inner\n",
"u=mat([[2,3,-4]])\n",
"v=mat([[1,-5,8]])\n",
"print \"u+v = \",add(u,v)\n",
"print \"5*u = \",multiply(5,u)\n",
"print \"-v = \",multiply(-1,v)\n",
"print \"2*u-3*v = \",add(multiply(2,u),multiply(-3,v))\n",
"print 'dot product of the two vectors, k = u.v = ',inner(u,v)\n",
"l=norm(u)# \n",
"print 'norm or length of the vector u = ',round(l,4)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex5.3 Pg 104 "
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2*u-3*v =\n",
"[[ 1]\n",
" [ 9]\n",
" [-2]]\n",
"The dot product of the two vectors u and v is: [[20]]\n",
"norm or length of the vector u = 7.0711\n"
]
}
],
"source": [
"from __future__ import division\n",
"from numpy.linalg import det,norm\n",
"from numpy import mat, add, dot, multiply, inner\n",
"u=mat([[5],[3],[-4]])\n",
"v=mat([[3],[-1],[-2]])\n",
"print \"2*u-3*v =\\n\",add(multiply(2,u),multiply(-3,v))\n",
"print 'The dot product of the two vectors u and v is:', sum(multiply(u,v))\n",
"l=norm(u)#\n",
"print 'norm or length of the vector u = ',round(l,4)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex5.5 Pg 105"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The addition of the two matrices A and B is:\n",
"[[ 5 4 11]\n",
" [ 1 1 -2]]\n",
"\n",
"The multiplication of a vector with a scalar is:\n",
"[[ 3 -6 9]\n",
" [ 0 12 15]]\n",
"\n",
"2*A-3*B = \n",
"[[-10 -22 -18]\n",
" [ -3 17 31]]\n"
]
}
],
"source": [
"from __future__ import division\n",
"from numpy.linalg import det,norm\n",
"from numpy import mat, add, dot, multiply, inner\n",
"A=mat([[1,-2,3],[0,4,5]])\n",
"B=mat([[4,6,8],[1,-3,-7]])\n",
"k=add(A,B)\n",
"print 'The addition of the two matrices A and B is:\\n',k\n",
"m=multiply(3,A)\n",
"print '\\nThe multiplication of a vector with a scalar is:\\n',m\n",
"p=add(multiply(2,A),multiply(-3,B))\n",
"print \"\\n2*A-3*B = \\n\",p"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex5.6 Pg 106"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"product of a and b is : [[8]]\n",
"product of p and q is: [[32]]\n"
]
}
],
"source": [
"from __future__ import division\n",
"from numpy.linalg import det,norm\n",
"from numpy import mat, add, dot, multiply, inner\n",
"a=mat([[7,-4,5]])\n",
"b=mat([[3,2,-1]])\n",
"k=inner(a,b)\n",
"print 'product of a and b is : ',k\n",
"p=mat([[6,-1,8,3]])\n",
"q=mat([[4,-9,-2,5]])\n",
"l=inner(p,q)\n",
"print 'product of p and q is:',l"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex5.7 Pg 107"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"A*B = \n",
"[[ 17 -6 14]\n",
" [ -1 2 -14]]\n",
"A*B = \n",
"[[ 5 2]\n",
" [15 10]]\n",
"B*A = \n",
"[[23 34]\n",
" [-6 -8]]\n",
"matrix mulitplication is not commutative since AB may not be equal to BA\n"
]
}
],
"source": [
"from __future__ import division\n",
"from numpy.linalg import det,norm\n",
"from numpy import mat, add, dot, multiply, inner\n",
"A=mat([[1 ,3],[2, -1]])\n",
"B=mat([[2, 0, -4],[5, -2, 6]])\n",
"print \"A*B = \\n\", dot(A,B)\n",
"A=mat([[1, 2],[3, 4]])\n",
"B=mat([[5, 6],[0, -2]])\n",
"print \"A*B = \\n\",dot(A,B)\n",
"print \"B*A = \\n\", dot(B,A)\n",
"print 'matrix mulitplication is not commutative since AB may not be equal to BA'\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex5.8 Pg 109"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"for the function f(x)=2x**2-3x+5,f(A) is :\n",
"[[ 16. -18.]\n",
" [-27. 61.]]\n",
"for the function g(x)=x**2+3x-10,g(A) is\n",
"[[ 0. 0.]\n",
" [ 0. 0.]]\n"
]
}
],
"source": [
"from __future__ import division\n",
"from numpy.linalg import det,norm\n",
"from numpy import mat, add, dot, multiply, inner\n",
"from numpy import identity as idt\n",
"A=mat([[1, 2],[3, -4]])\n",
"A2=dot(A,A) #multiplying A by itself\n",
"A3=dot(A2,A)\n",
"f=add(add(multiply(2,A2),multiply(-3,A)),multiply(5,idt(2)))\n",
"print 'for the function f(x)=2x**2-3x+5,f(A) is :\\n',f\n",
"g=add(add(A2,multiply(3,A)),multiply(-10,idt(2)))\n",
"print 'for the function g(x)=x**2+3x-10,g(A) is\\n',g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex5.9 Pg 110"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"A*b = \n",
"[[1 0 0]\n",
" [0 1 0]\n",
" [0 0 1]]\n",
"since A*B is identity matrix,A and B are invertible and inverse of each other\n"
]
}
],
"source": [
"from __future__ import division\n",
"from numpy.linalg import det,norm\n",
"from numpy import mat, add, dot, multiply, inner\n",
"A=mat([[1 ,0 ,2],[2 ,-1, 3],[4, 1, 8]])\n",
"B=mat([[-11, 2 ,2],[-4, 0 ,1],[6, -1, -1]])\n",
"print \"A*b = \\n\",dot(A,B)\n",
"print 'since A*B is identity matrix,A and B are invertible and inverse of each other'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex5.10 Pg 111"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"determinant of A 7.0\n",
"determinant of B 16.0\n",
"determinant of C -81.0\n"
]
}
],
"source": [
"from __future__ import division\n",
"from numpy.linalg import det,norm\n",
"from numpy import mat, add, dot, multiply, inner\n",
"A=mat([[5 ,4],[2, 3]])\n",
"print 'determinant of A',det(A)\n",
"B=mat([[2, 1],[-4, 6]])\n",
"print 'determinant of B',det(B)\n",
"C=mat([[2, 1, 3],[4, 6, -1],[5 ,1 ,0]])\n",
"print 'determinant of C',det(C)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex5.13 Pg 115"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"x = [[ 2.]]\n",
"y = [[-1.]]\n",
"z = [[ 3.]]\n"
]
}
],
"source": [
"from __future__ import division\n",
"from numpy.linalg import det,norm,solve\n",
"from numpy import mat, add, dot, multiply, inner,divide\n",
"\n",
"\n",
"A=mat([[1, 2, 1],[2, 5, -1],[3, -2, -1]]) #left hand side of the system of equations\n",
"B=mat([[3] ,[-4] ,[5]]) #right hand side or the constants in the equations\n",
"X=divide(A,B) # #unique solution for the system of equations\n",
"X = solve(A, B)\n",
"print \"x = \",X[0]\n",
"print \"y = \",X[1]\n",
"print \"z = \",X[2]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex5.14 Pg 116"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Inverse of A = \n",
"[[-11. 2. 2.]\n",
" [ -4. 0. 1.]\n",
" [ 6. -1. -1.]]\n"
]
}
],
"source": [
"from __future__ import division\n",
"from numpy import mat\n",
"\n",
"A=mat([[1 ,0 ,2],[2, -1, 3],[4, 1, 8]])\n",
"A_inv = A**-1\n",
"print \"Inverse of A = \\n\", A_inv"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
PKxIk^8^8 Discrete Mathematics/Ch6_1.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter6 - Counting"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex 6.1 Pg 133"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"number of ways a student can choose a calculus professor\n",
"13\n",
"event of getting an even or a prime number\n",
"7\n",
"number of ways of choosing a number which is prime or even\n",
"8\n"
]
}
],
"source": [
"from numpy import intersect1d, union1d\n",
"M=8# #number of male professors teaching calculus\n",
"F=5# #number of female professors teaching calculus\n",
"T=M+F #\n",
"print 'number of ways a student can choose a calculus professor\\n',T\n",
"\n",
"E=[2,3,5,7]# #event of choosing a prime number less than 10\n",
"F=[2,4,6,8]# #event of choosing an even number less than 10\n",
"G=intersect1d(E,F)# #event of getting an even and prime number \n",
"H=len(E)+len(F)-len(G)# \n",
"print 'event of getting an even or a prime number\\n',H\n",
"\n",
"E=[11,13,17,19]# #event of choosing a prime number between 10 and 20\n",
"F=[12,14,16,18]# #event of choosing an even number between 10 and 20\n",
"G=union1d(E,F)# #event of choosing a number which is prime or even\n",
"k=len(G)# \n",
"print 'number of ways of choosing a number which is prime or even\\n',k"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex6.2 Pg 133"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"a license plate contains two letters followed by three digits where first digit can not be zero\n",
"total number of license plates that can be printed\n",
"608400\n",
"\n",
"\n",
"a president ,a secretary and a treasurer has to be elected in an orga-nisation of 26 members.No person is elected to more than one postion\n",
"number of ways to elect the three officers (president,secretary,treasurer\n",
"15600\n"
]
}
],
"source": [
"print 'a license plate contains two letters followed by three digits where first digit can not be zero' \n",
"n=26# #number of english letters\n",
"n*n# #number of ways of choosing two letters in the license plate\n",
"p=10# #number of digits (0-9)\n",
"(p-1)*p*p# #number of ways to select the three digits with the first digit not being zero\n",
"k=n*n*(p-1)*p*p#\n",
"print 'total number of license plates that can be printed\\n',k\n",
"\n",
"print '\\n\\na president ,a secretary and a treasurer has to be elected in an orga-nisation of 26 members.No person is elected to more than one postion'\n",
"t=26# #total number of members in the organisation\n",
"j=t*(t-1)*(t-2)# \n",
"print 'number of ways to elect the three officers (president,secretary,treasurer\\n',j\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex6.3 Pg 134"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"factorial of 6 : \n",
"720\n",
"value of 8!/6! is: 56.0\n",
"value of 12!/9! is: 1320.0\n"
]
}
],
"source": [
"from scipy.misc import factorial\n",
"print 'factorial of 6 : '\n",
"facto2=2*1#\n",
"facto3=3*facto2\n",
"facto4=3*facto3\n",
"facto4=4*facto3\n",
"facto5=5*facto4\n",
"facto6=6*facto5\n",
"print facto6\n",
"k=8*7*factorial(6)/factorial(6)#\n",
"print 'value of 8!/6! is:',k\n",
"j=12*11*10*factorial(9)/factorial(9)#\n",
"print 'value of 12!/9! is:',j\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex6.4 Pg 135"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"8C2 = 28.0\n",
"9C4 = 126.0\n",
"12C5 = 792.0\n",
"10C3 = 120.0\n",
"13C1 = 13.0\n",
"value of 10C7 is 120.0\n"
]
}
],
"source": [
"from scipy.misc import factorial\n",
"def func1(n,r): #calculating binomial coefficient\n",
" k=factorial(n)/(factorial(r)*factorial(n-r))#\n",
" return k\n",
"print \"8C2 = \",func1(8,2)\n",
"print \"9C4 = \",func1(9,4)\n",
"print \"12C5 = \",func1(12,5)\n",
"print \"10C3 = \",func1(10,3)\n",
"print \"13C1 = \",func1(13,1)\n",
" \n",
"p = factorial(10)/(factorial(10-7)*factorial(7)) #calculating 10C7\n",
"q= factorial(10)/(factorial(10-3)*factorial(3)) #calculating 10C3\n",
"print 'value of 10C7 is',p\n",
"#10-7=3 so 10C7 can also be computed as 10C3\n",
"#both p and q have same values but second method saves time and space\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex6.5 Pg 136"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"finding the number of three-letter words using only the given six letters(A,B,C,D,E,F) without repetition\n",
"number of three-letter words possible 120\n"
]
}
],
"source": [
"print 'finding the number of three-letter words using only the given six letters(A,B,C,D,E,F) without repetition'\n",
"n=6# #total number of letters\n",
"l1=n# #number of ways in which first letter of the word can be chosen\n",
"l2=n-1# #number of ways in which second letter of the word can be chosen\n",
"l3= n-2# #number of ways in which third letter can be chosen\n",
"k=l1*l2*l3#\n",
"print 'number of three-letter words possible',k"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex6.6 Pg 137"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The number of seven-letter words that can be formed using letters of the word BENZENE = 420.0\n",
"\n",
"a set of 4 indistinguishable red coloured flags, 3 indistinguishable white flags and a blue flag is given\n",
"\n",
"number of different signals ,each consisting of eight flags = 280.0\n"
]
}
],
"source": [
"from scipy.misc import factorial\n",
"def funct1(n,p,q):\n",
" k= factorial(n)/(factorial(p)*factorial(q))#\n",
" return k\n",
"k=funct1(7,3,2) #in \"BENZENE\" three letters are alike(the three Es) and two are alike (the two Ns)\n",
"print 'The number of seven-letter words that can be formed using letters of the word BENZENE = ',k\n",
"\n",
"print '\\na set of 4 indistinguishable red coloured flags, 3 indistinguishable white flags and a blue flag is given'\n",
"j=funct1(8,4,3)\n",
"print '\\nnumber of different signals ,each consisting of eight flags = ',j\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex6.7 Pg 138"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"four objects are given (a,b,c,d) and three are taken at a time\n",
"number of combinations of the four objects given = 4.0\n",
"total number of permuatations for the problem = 24.0\n"
]
}
],
"source": [
"from scipy.misc import factorial\n",
"print 'four objects are given (a,b,c,d) and three are taken at a time' \n",
"combinations = factorial(4)/(factorial(4-3)*factorial(3))#\n",
"print 'number of combinations of the four objects given = ',combinations\n",
"k=factorial(3)# #number of permutations of objects in a combination\n",
"permutations = combinations*k#\n",
"print 'total number of permuatations for the problem = ',permutations\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex6.8 Pg 138"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"the number of committees of three that can be formed out of eight people = 56.0\n",
"total number of ways that a farmer can choose all these animals = 14000.0\n"
]
}
],
"source": [
"from scipy.misc import factorial\n",
"def myfunc(n,r):\n",
" k=factorial(n)/(factorial(n-r)*factorial(r))#\n",
" return k\n",
"k=myfunc(8,3)\n",
"print'the number of committees of three that can be formed out of eight people = ', k\n",
" \n",
"cows=myfunc(6,3) #number of ways that a farmer can choose 3 cows out of 6 cows\n",
"pigs=myfunc(5,2) #number of ways that a farmer can choose 2 pigs out of 5 pigs\n",
"hens=myfunc(8,4) #number of ways that a farmer can choose 4 hens out of 8 hens\n",
"p=cows*pigs*hens# \n",
"print 'total number of ways that a farmer can choose all these animals = ',p\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex6.9 Pg 139"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"number of non negative integer solutions of the given equation x+y+z=18 = 190.0\n"
]
}
],
"source": [
"from scipy.misc import factorial\n",
"#each solution to the equation can be viewed as a combination of objects\n",
"r=18# #number of objects \n",
"M=3# #kinds of object\n",
"m=factorial(r+(M-1))/(factorial(r+(M-1)-(M-1))*factorial(M-1))#\n",
"print 'number of non negative integer solutions of the given equation x+y+z=18 = ',m"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex6.14 Pg 145"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"number of ways nine toys can be divided between four children with the youngest son getting 3 toys and others getting 2 each 7560.0\n"
]
}
],
"source": [
"from scipy.misc import factorial\n",
"c1=3# #number of toys that the youngest child should get\n",
"c2=2# #number of toys that the third child should get\n",
"c3=2# #number of toys that the second child should get\n",
"c4=2# #number of toys that the eldest son should get\n",
"m=factorial(9)/(factorial(3)*factorial(2)*factorial(2)*factorial(2))#\n",
"print 'number of ways nine toys can be divided between four children with the youngest son getting 3 toys and others getting 2 each',m"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex6.15 Pg 146"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"each partition of the students can be arranged in 3! ways as an ordered partition\n",
"number of ways that 12 students can be partitioned into three teams so that each team consists of 4 students 5775.0\n"
]
}
],
"source": [
"from scipy.misc import factorial\n",
"p=12# #total number of students\n",
"t=3# #number of teams or partition\n",
"print 'each partition of the students can be arranged in 3! ways as an ordered partition'\n",
"r=factorial(12)/(factorial(4)*factorial(4)*factorial(4)) #number of ordered partitions\n",
"m=r/factorial(t)# #number of unordered partitions\n",
"print 'number of ways that 12 students can be partitioned into three teams so that each team consists of 4 students',m"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex6.16 Pg 147"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The number of integers in the set U, which are not divisible by 3,5 and 7 is 457.0\n"
]
}
],
"source": [
"from numpy import floor\n",
"U=1000# #number of elements in the set of positive integers not exceeding 1000\n",
"A=U/3# #number of elements in the subset of integers divisible by 3\n",
"B=U/5# #number of elements in the subset of integers divisible by 5\n",
"C=U/7# #number of elements in the subset of integers divisible by 7\n",
"AandB=floor(U/(3*5)) #number of elements in the subset containing numbers divisible by both 3 and 5\n",
"AandC=floor(U/(3*7)) #number of elements in the subset containing numbers divisible by both 3 and 7\n",
"BandC=floor(U/(5*7)) #number of elements in the subset containing numbers divisible by both 5 and 7\n",
"AandBandC=floor(U/(3*5*7)) #number of elements in the subset containing numbers divisible by 3,5 and 7\n",
"s=U-(A+B+C)+(AandB+AandC+BandC)-(AandBandC)# # By inclusion-exclusion principle\n",
"S=round(s)#\n",
"print 'The number of integers in the set U, which are not divisible by 3,5 and 7 is',S"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
PKxI=PmPm Discrete Mathematics/Ch7_1.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter7 - Probability Theory"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.1 Pg 152"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"sample space for the event that an even or a prime number occurs = [2 3 4 5 6]\n",
"sample space for the event that an odd prime number occurs = [3 5]\n",
"sample space for the event that a prime number does not occur = [1 4 6]\n",
"sample space for the event in which only heads appear = ['000']\n",
"Experiment:tossing a coin until a head appears and then counting the number of times the coin is tossed\n",
"Since every positive integer is an element of S,the sample space is infinite\n"
]
}
],
"source": [
"from numpy import intersect1d, setdiff1d, union1d,inf\n",
"from __future__ import division\n",
"S=[1,2,3,4,5,6] #sample space for the rolling of a die\n",
"A=[2,4,6] #event that an even number occurs\n",
"B=[1,3,5] #event that an odd number occurs\n",
"C=[2,3,5] #event that a prime number occurs\n",
"print 'sample space for the event that an even or a prime number occurs = ',union1d(A,C)\n",
"print 'sample space for the event that an odd prime number occurs = ',intersect1d(B,C)\n",
"print 'sample space for the event that a prime number does not occur = ',setdiff1d(S,C) #It is the complement of the set C.\n",
"intersect1d(A,B) #It is a null set or null vector since there can't occur an even and an odd number simultaneously\n",
" \n",
"H=0# #\"head\" face of a coin\n",
"T=1# #\"tail\" face of a coin\n",
"S=[\"000\",\"001\",\"010\",\"011\",\"100\",\"101\",\"110\",\"111\"] # #sample space for the toss of a coin three times\n",
"A=[\"000\",\"001\",\"100\"]# #event that two more or more heads appear consecutively\n",
"B=[\"000\",\"111\"]# #event that all tosses are the same\n",
"print 'sample space for the event in which only heads appear = ',intersect1d(A,B)\n",
" \n",
"print 'Experiment:tossing a coin until a head appears and then counting the number of times the coin is tossed'\n",
"S=[1,2,3,4,5,inf] #The sample space has infinite elements in it\n",
"print \"Since every positive integer is an element of S,the sample space is infinite\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.2 Pg 153"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Experiment:three coins are tossed and the number of heads are observed\n",
"the probability space is as follows \n",
"A is the event that atleast one head appears and B is the event that all heads or all tails appear \n",
"probability of occurrence of event A = 0.875\n",
"probability of occurrence of event B = 0.25\n"
]
}
],
"source": [
"print 'Experiment:three coins are tossed and the number of heads are observed'\n",
"S=[0,1,2,3]# #the sample space for the experiment where 0 implies no heads,1 implies only one head out of the three coins and so on\n",
"print \"the probability space is as follows \"\n",
"P0=1/8# #probability of getting no head on any of the coins i.e TTT\n",
"P1=3/8# #probability of getting only one head on any of the coins, out of the three coins i.e HTT,THT,TTH\n",
"P2=3/8# #probability of getting two heads, out of the three coins i.e THH,HTH,HHT\n",
"P3=1/8# #probability of getting all the three heads i.e HHH\n",
"print \"A is the event that atleast one head appears and B is the event that all heads or all tails appear \"\n",
"A=[1,2,3]# # HHH,HHT,HTH,HTT,THH,THT,TTH\n",
"B=[0,3]# #HHH,TTT\n",
"PA=P1+P2+P3# \n",
"print 'probability of occurrence of event A = ',PA\n",
"PB=P0+P3# \n",
"print 'probability of occurrence of event B = ',PB "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.3 Pg 154"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Experiment: a card is selected from a deck of 52 cards \n",
"A is the event of the selected card being a spade \n",
"B is the event of the selected card being a face card \n",
"probability of selecting a spade = 1/4\n",
"probability of selecting a face card = 3/13\n",
"probability of selecting a spade face card is: 3/52\n"
]
}
],
"source": [
"from fractions import Fraction\n",
"print \"Experiment: a card is selected from a deck of 52 cards \"\n",
"print \"A is the event of the selected card being a spade \"\n",
"print \"B is the event of the selected card being a face card \"\n",
"t=52 # #the total number of cards\n",
"s=13# #number of spades\n",
"PA= s/t# \n",
"print 'probability of selecting a spade = ',Fraction(PA).limit_denominator(100)\n",
"f=12# #number of face cards(jack,queen,king)\n",
"PB=f/t#\n",
"print 'probability of selecting a face card = ',Fraction(PB).limit_denominator(100)\n",
"sf=3# #number of spade face cards\n",
"Psf=sf/t#\n",
"print \"probability of selecting a spade face card is:\",Fraction(Psf).limit_denominator(100)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.4 Pg 155"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Experiment: selection of a student out of 100 students \n",
"probability of the selected student taking mathematics or chemistry = 2/5\n"
]
}
],
"source": [
"print \"Experiment: selection of a student out of 100 students \"\n",
"M=30# #no of students taking mathematics\n",
"C=20# #no of students taking chemistry\n",
"T=100# #total no. of students\n",
"PM = M/T #probability of the selected student taking mathematics\n",
"PC = C/T #probability of the selected student taking chemistry\n",
"MnC=10# #no of students taking mathematics and chemistry\n",
"PMnC = MnC/T #probability of the selected student taking mathematics and chemistry both\n",
"PMorC = PM+PC-PMnC# \n",
"print 'probability of the selected student taking mathematics or chemistry = ',Fraction(PMorC).limit_denominator(100)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.6 Pg 156"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"A bag contains 12 items of which four are defective.Three items are drawn at random,one after the other\n",
"probability that all three items are non defective = 14/55\n"
]
}
],
"source": [
"print \"A bag contains 12 items of which four are defective.Three items are drawn at random,one after the other\"\n",
"s=12# #total itmes in the bag\n",
"d=4# #defective items in the bag\n",
"Pf=(s-d)/s # #probability that the first item drawn is non defective\n",
"Pe=Pf*((s-d-1)/(s-1))*((s-d-2)/(s-2))\n",
"print 'probability that all three items are non defective = ',Fraction(Pe).limit_denominator(100)\n",
"#after the first item is chosen,the second item is to be chosen from 1 less than the original number of items in the box and similarly the number of non defective items gets decreased by 1.Similarly ,for the third draw of item from the box"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.7 Pg 157"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"probability of A is = 0.5\n",
"probability of B is = 0.5\n",
"probability of C is = 0.25\n",
"probability of the event AnB = 0.25\n",
"probability of the event AnC = 0.125\n",
"probability of the event BnC = 0.25\n",
"A and B are independent\n",
"A and C are independent\n",
"B and C are dependent\n"
]
}
],
"source": [
"from numpy import intersect1d\n",
"H=1# #heads of a coin\n",
"T=2# #tails of the coin\n",
"S=[111,112,121,122,211,212,221,222] #sample space for the toss of a coin three times. 111 implies heads all three times,112 implies heads on first two tosses and tails on the third toss\n",
"A=[111,112,121,122]# #event that first toss is heads\n",
"B=[111,112,211,212]# #event that second toss is heads\n",
"C=[112,211]# #event that exactly two heads appear in a row\n",
"PA=len(A)/len(S)\n",
"print 'probability of A is = ',PA\n",
"PB=len(B)/len(S)\n",
"print 'probability of B is = ',PB\n",
"PC=len(C)/len(S)\n",
"print 'probability of C is = ',PC\n",
"AnB=intersect1d(A,B)\n",
"AnC=intersect1d(A,C)\n",
"BnC=intersect1d(B,C)\n",
"PAnB= len(AnB)/len(S)\n",
"print 'probability of the event AnB = ',PAnB\n",
"PAnC= len(AnC)/len(S)#\n",
"print 'probability of the event AnC = ',PAnC \n",
"PBnC= len(BnC)/len(S)\n",
"print 'probability of the event BnC = ',PBnC\n",
"if((PA*PB)==PAnB):\n",
" print \"A and B are independent\"\n",
"else:\n",
" print \"A and B are dependent\"\n",
"\n",
"if((PA*PC)==PAnC):\n",
" print \"A and C are independent\"\n",
"else:\n",
" print \"A and C are dependent\"\n",
"if((PB*PC)==PBnC):\n",
" print \"B and C are independent\"\n",
"else:\n",
" print \"B and C are dependent\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.8 Pg 157"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Experiment: A and B both shoot at a target\n",
"A and B are independent events so PA*PB will be equal to probability of the event of A and B both hitting the target i.e PAnB\n",
"probability of atleast one of them hitting the target = 0.55\n"
]
}
],
"source": [
"print \"Experiment: A and B both shoot at a target\"\n",
"PA=1/4# #given probability of A hitting the target\n",
"PB=2/5# #given probability of B hitting the target\n",
"print \"A and B are independent events so PA*PB will be equal to probability of the event of A and B both hitting the target i.e PAnB\"\n",
"PAnB=PA*PB#\n",
"PAorB=PA+PB-PAnB#\n",
"print'probability of atleast one of them hitting the target = ', PAorB"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.9 Pg 158"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Experiment: Three horses race together twice\n",
"probability of third horse winning the first race and first horse winning the second race is = 1/12\n"
]
}
],
"source": [
"print \"Experiment: Three horses race together twice\"\n",
"Ph1=1/2# #probability of first horse winning the race\n",
"Ph2=1/3# #probability of second horse winning the race\n",
"Ph3=1/6# #probability of third horse winning the race\n",
"S=[11,12,13,21,22,23,31,32,33] #sample space where 11 implies first horse winning the first and second race both,12 implies first horse winning the first race and second horse winning the second race and so on\n",
"P11=Ph1*Ph1 #probability of first horse winning both races\n",
"P12=Ph1*Ph2 #probability of first horse winning the first race and second horse winning the second race\n",
"P13=Ph1*Ph3 #probability of first horse winning the first race and third horse winning the second race\n",
"P21=Ph2*Ph1 #probability of second horse winning the first race and first horse winning the second race\n",
"P22=Ph2*Ph2 #probability of second horse winning both the races\n",
"P23=Ph2*Ph3 #probability of second horse winning the first race and third horse winning the second race\n",
"P31=Ph3*Ph1 #probability of third horse winning the first race and first horse winning the second race\n",
"P32=Ph3*Ph2 #probability of third horse winning the first race and second horse winning the second race\n",
"P33=Ph3*Ph3 #probability of third horse winning both the races \n",
"print 'probability of third horse winning the first race and first horse winning the second race is = ',Fraction(P31).limit_denominator(100)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.10 Pg 158"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"probability of getting exactly two heads (i.e k=2) = 15/64\n",
"probability of getting atleast four heads(i.e k=4,5 or 6) = 11/32\n",
"probability of getting one or more heads = 63/64\n"
]
}
],
"source": [
"from scipy.misc import factorial\n",
"n=6# #number of times a fair coin is tossed and getting a heads is a success\n",
"p=1/2# #probability of getting a heads\n",
"q=1/2 # #probability of not getting a heads\n",
"P2=(factorial(6)/(factorial(6-2)*factorial(2)))*p**2*q**(6-2)# \n",
"print 'probability of getting exactly two heads (i.e k=2) = ',Fraction(P2).limit_denominator(100)\n",
"\n",
"P4=(factorial(6)/(factorial(6-4)*factorial(4)))*p**4*q**(6-4)# #probabilty of getting four heads\n",
"P5=(factorial(6)/(factorial(6-5)*factorial(5)))*p**5*q**(6-5)# #probabilty of getting five heads\n",
"P6=(factorial(6)/(factorial(6-6)*factorial(6)))*p**6*q**(6-6)# #probabilty of getting five heads\n",
"PA=P4+P5+P6 # \n",
"print 'probability of getting atleast four heads(i.e k=4,5 or 6) = ',Fraction(PA).limit_denominator(100)\n",
" \n",
"Pn=q**6 #probability of getting no heads\n",
"Pm=1-Pn#\n",
"print 'probability of getting one or more heads = ',Fraction(Pm).limit_denominator(100)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.12 Pg 159"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"A box contains 12 items of which three are defective\n",
"A sample of three items is selected from the box\n",
"number of elements in the sample space where samples are of size 3 220.0\n"
]
}
],
"source": [
"from scipy.misc import factorial\n",
"print \"A box contains 12 items of which three are defective\"\n",
"print \"A sample of three items is selected from the box\"\n",
"s=factorial(12)/(factorial(12-3)*factorial(3))# \n",
"print 'number of elements in the sample space where samples are of size 3',s\n",
"#X denotes the number of defective items in the sample\n",
"x=[0,1,2,3]# #range space of the random variable X"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.13 Pg 160"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"\n",
"distribution table of X where first row gives the range space and second row gives the respective probabilities is as follows : \n",
"x(i)\t\t\tp(i)\n",
"2.0 \t\t\t1/36\n",
"3.0 \t\t\t1/18\n",
"4.0 \t\t\t1/12\n",
"5.0 \t\t\t1/9\n",
"6.0 \t\t\t5/36\n",
"7.0 \t\t\t1/6\n",
"8.0 \t\t\t5/36\n",
"9.0 \t\t\t1/9\n",
"10.0 \t\t\t1/12\n",
"11.0 \t\t\t1/18\n",
"12.0 \t\t\t1/36\n"
]
}
],
"source": [
"from numpy import mat,nditer\n",
"r=[1,2,3,4,5,6,5,4,3,2,1]\n",
"#number of outcomes whose sum is 2,3,4,5,6,7,8,9,10,11,12 respectively such that there is only 1 outcome i.e (1,1) whose sum is 2,two outcomes (1,2) and (2,1) whose sum is 3 and so on\n",
"t=36# #total number of elements in the sample space of the experiment of tossing a pair of dice\n",
"\n",
"\n",
"x=mat([[2,3,4,5,6,7,8,9,10,11,12]]) #range space of random variable X which assigns to each point in sample space the sum of the numbers \n",
"\n",
"D=mat([[2,3,4,5,6,7,8,9,10,11,12],[0.0277778, 0.0555556 , 0.0833333, 0.1111111, 0.1388889 ,0.1666667, 0.1388889 ,0.1111111, 0.0833333, 0.0555556, 0.0277778]])\n",
"print '\\n\\ndistribution table of X where first row gives the range space and second row gives the respective probabilities is as follows : '\n",
"\n",
"print \"x(i)\\t\\t\\tp(i)\"\n",
"for x,y in nditer([D[0,:],D[1,:]]):\n",
" y=float(y)\n",
" print x,\"\\t\\t\\t\",Fraction(y).limit_denominator(100)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.14 Pg 160"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"a box contains 12 items of which three are defective\n",
"A sample of three items is selected from the box\n",
"\n",
"distribution table for random variable X the upper row being values of X\n",
":\n",
"x(i)\t\t\tp(i)\n",
"0.0 \t\t\t21/55\n",
"1.0 \t\t\t27/55\n",
"2.0 \t\t\t7/57\n",
"3.0 \t\t\t0\n"
]
}
],
"source": [
"from fractions import Fraction\n",
"from numpy import nditer,mat\n",
"from scipy.misc import factorial\n",
"print \"a box contains 12 items of which three are defective\"\n",
"print \"A sample of three items is selected from the box\"\n",
"r=factorial(9)/(factorial(9-3)*factorial(3)) #number of samples of size 3 with no defective items\n",
"t=220# #number of different samples of size 3 i.e the number of elements in the sample space\n",
"P0=r/t #probability of getting no defective item\n",
"r1=3*(factorial(9)/(factorial(9-2)*factorial(2))) #number of samples of size 3 getting 1 defective item\n",
"P1=r1/t #probability of getting 1 defective item\n",
"r2=9*(factorial(3)/(factorial(3-2)*factorial(2))) #number of samples of size 3 getting 2 defective item\n",
"P2=r2/t #probability of getting 2 defective item\n",
"r3=1# #number of samples of size 3 getting 3 defective item\n",
"P3=r3/t #probability of getting 3 defective item\n",
"x=[0,1,2,3]#\n",
"p=mat([[P0,P1,P2,P3]])\n",
"D=mat([[0,1,2,3],[P0,P1,P2,P3]])\n",
"print '\\ndistribution table for random variable X the upper row being values of X\\n:'\n",
"\n",
"print \"x(i)\\t\\t\\tp(i)\"\n",
"for x,y in nditer([D[0,:],D[1,:]]):\n",
" y=float(y)\n",
" print x,\"\\t\\t\\t\",Fraction(y).limit_denominator(100)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.15 Pg 161"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"A fair coin is tossed six times\n",
"mean or expected number of heads are = 3.0\n",
"X is a random variable which gives possible number of defective items in a sample of size 3\n",
"expected number of defective items in a sample of size 3 are = 0.75\n",
"expected pay off for the race is = 4.5\n"
]
}
],
"source": [
"print \"A fair coin is tossed six times\"\n",
"x=[0,1,2,3,4,5,6] #number of heads which can occur\n",
"p=[1/64,6/64,15/64,20/64,15/64,6/64,1/64]# #probability of occurring of heads where 1/64 is probability for occurrence of a single head,6/64 that of occurrence of two heads and so on.\n",
"r=0#\n",
"for i in range(0,7):\n",
" r = r + (x[i]*p[i])#\n",
"\n",
"print 'mean or expected number of heads are = ',r\n",
" \n",
"print \"X is a random variable which gives possible number of defective items in a sample of size 3\"\n",
"#Box contains 12 items of which three are defective\n",
"x=[0,1,2,3]# #possible number of defective items in a smaple of size 3\n",
"p=[84/220,108/220,27/220,1/220]# #probability of occurrence of each number in x respectively where 84/220 is the probability for getting no defective item,108/220 is that of getting 1 defective item and so on.\n",
"r=0#\n",
"for i in range(0,4):\n",
" r = r + (x[i]*p[i])#\n",
"\n",
"print 'expected number of defective items in a sample of size 3 are = ',r\n",
" \n",
"Ph1=1/2# #probability of winning the race by first horse\n",
"Ph2=1/3# #probability of winning the race by second horse\n",
"Ph3=1/6# #probability of winning the race by third horse\n",
"#X is the payoff function for the winning horse\n",
"X1=2# #X pays $2 as first horse wins the rac\n",
"X2=6# #X pays $6 as second horse wins the race\n",
"X3=9# #X pays $9 as third horse wins the race\n",
"E=X1*Ph1+X2*Ph2+X3*Ph3\n",
"print 'expected pay off for the race is = ',E"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.16 Pg 162"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Variance of X is = 1.5\n",
"Standard deviation of X is = 1.2247\n",
"variance of X is = 0.4602\n",
"Standard deviation for X = 0.6784\n"
]
}
],
"source": [
"from numpy import sqrt\n",
"u=3 #mean of distribution of random variable X\n",
"x=[0,1,2,3,4,5,6] #values of X in the distribution as x where it is the number of times heads occurs when a coin is tossed six times\n",
"p=[1/64,6/64,15/64,20/64,15/64,6/64,1/64] #probabilities of occurrence of each value of X (x) in the distribution such that 1/64 gives the probability of occurrence of no heads at all,6/64 gives that of occurrence of heads for only one time and so on\n",
"k=0\n",
"for i in range(0,7):\n",
" k=k+((x[i]-u)**2)*p[i]\n",
"\n",
"print 'Variance of X is = ',k\n",
"s=sqrt(k)#\n",
"print'Standard deviation of X is = ',round(s,4)\n",
"\n",
"u=0.75# #mean \n",
"x=[0,1,2,3]# #values of random variable X as x in the probability distribution of X\n",
"p=[84/220,108/220,27/220,1/220]# #probability of values in x which appear in distribution table of X\n",
"g=0#\n",
"for i in range(0,4):\n",
" g=g+((x[i])**2)*p[i]\n",
"\n",
"h=g-(u*u) \n",
"print 'variance of X is = ',round(h,4)\n",
"sd=sqrt(h)#\n",
"print 'Standard deviation for X = ',round(sd,4)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.17 Pg 162"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"expected number of times the man will hit the target = 20.0\n",
"Standard deviation = 4.0\n",
"expected number of correct answers in the exam = 2.5\n"
]
}
],
"source": [
"from __future__ import division\n",
"from numpy import sqrt\n",
"p=1/5# #probability of the man hitting a target\n",
"q=1-1/5# #probability of the man not hitting the target\n",
"n=100# #number of times the man fires\n",
"e=n*p# \n",
"print 'expected number of times the man will hit the target = ',e\n",
"r=sqrt(n*p*q)# \n",
"print 'Standard deviation = ',r\n",
"\n",
"p=1/2# #probability of guessing the correct answer in a five question true-false exam\n",
"n=5# #number of questions in the exam\n",
"g=n*p#\n",
"print 'expected number of correct answers in the exam = ',g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.18 Pg 164"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"thus the probability that a value of X lies between 65 and 85 is atleast 0.75 according to Chebyshev inequality\n",
"thus the probability that a value of X lies between 60 and 90 is atleast 0.8888889 according to Chebyshev Inequality\n"
]
}
],
"source": [
"from __future__ import division\n",
"u=75# #mean of a random variable X\n",
"n=5# #standard deviation of X\n",
"k=2# #for k=2\n",
"l1=u-k*n\n",
"l2=u+k*n\n",
"P1=1-(1/k)**2\n",
"print \"thus the probability that a value of X lies between 65 and 85 is atleast 0.75 according to Chebyshev inequality\"\n",
"k=3# #for k=3\n",
"l1=u-k*n\n",
"l2=u+k*n\n",
"P2=1-(1/k)**2\n",
"print \"thus the probability that a value of X lies between 60 and 90 is atleast 0.8888889 according to Chebyshev Inequality\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex7.19 Pg 166"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"a die is tossed 5 times with the following outcomes\n",
"for a fair die the mean is 3.5.So law of large numbers tells us that as number of outcomes increase for this experiment,there is a greater likelihood that themean will get closer to 3.5\n"
]
}
],
"source": [
"from __future__ import division\n",
"print \"a die is tossed 5 times with the following outcomes\"\n",
"x1=3#\n",
"x2=4#\n",
"x3=6#\n",
"x4=1#\n",
"x5=4#\n",
"xmean=(x1+x2+x3+x4+x5)/5 #mean of the outcomes\n",
"print \"for a fair die the mean is 3.5.So law of large numbers tells us that as number of outcomes increase for this experiment,there is a greater likelihood that themean will get closer to 3.5\""
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
PKxIϗ< Discrete Mathematics/Ch8_1.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter8 - Graph Theory"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex8.1 Pg 193"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"given a graph with 6 nodes viz. node1,node2....node6\n",
"The adjacency matrix for A is : \n",
"[[0 1 0 1 1 0]\n",
" [1 0 1 0 1 0]\n",
" [0 1 0 0 0 1]\n",
" [1 0 0 0 0 0]\n",
" [1 1 0 0 0 0]\n",
" [0 0 1 0 0 0]]\n",
"sequence A is a path from node4 to node6# but it is not a trail since the edge from node1 to node2 is used twice\n",
"The adjacency matrix for B is : \n",
"[[0 0 0 1 1 0]\n",
" [0 0 0 0 1 1]\n",
" [0 0 0 0 0 0]\n",
" [1 0 0 0 0 0]\n",
" [1 1 0 0 0 0]\n",
" [0 1 0 0 0 0]]\n",
"sequence B is not a path since there is no edge from node2 to node6 is used twice\n",
"sequence C is a trail since is no edge is used twice\n",
"The adjacency matrix for D is : \n",
"[[0 0 0 1 1 0]\n",
" [0 0 0 0 0 0]\n",
" [0 0 0 0 1 1]\n",
" [1 0 0 0 0 0]\n",
" [1 0 1 0 0 0]\n",
" [0 0 1 0 0 0]]\n",
"sequence D is a simple path from node4 to node6\n"
]
}
],
"source": [
"from numpy import mat\n",
"# refer to page 8.6\n",
"print 'given a graph with 6 nodes viz. node1,node2....node6'\n",
"A=mat([[0, 1, 0, 1 ,1 ,0],[1, 0, 1, 0, 1, 0],[0, 1, 0, 0, 0, 1],[1, 0, 0 ,0 ,0 ,0],[1 ,1, 0, 0, 0, 0],[0, 0, 1, 0 ,0 ,0]])\n",
"print 'The adjacency matrix for A is : \\n',A\n",
"print 'sequence A is a path from node4 to node6# but it is not a trail since the edge from node1 to node2 is used twice'\n",
"B=mat([[0 ,0, 0, 1, 1, 0],[0, 0 ,0 ,0 ,1, 1],[0, 0, 0, 0 ,0, 0],[1, 0, 0 ,0 ,0,0],[1, 1, 0, 0, 0, 0],[0,1, 0 ,0, 0, 0]])\n",
"print 'The adjacency matrix for B is : \\n',B\n",
"print 'sequence B is not a path since there is no edge from node2 to node6 is used twice'\n",
"C=mat([[0, 0, 0 ,1 ,1 ,0],[0, 0, 1, 0, 1, 0],[0, 1, 0, 0, 1, 0],[1, 0, 0, 0, 0, 0],[1, 1, 1, 0, 0, 1],[0, 0, 0, 0, 1, 0]])\n",
"print 'sequence C is a trail since is no edge is used twice'\n",
"D=mat([[0, 0 ,0 ,1, 1, 0],[0, 0, 0, 0, 0, 0],[0, 0 ,0 ,0, 1, 1],[1, 0, 0,0, 0, 0],[1, 0, 1, 0, 0, 0],[0, 0, 1 ,0 ,0 ,0]])\n",
"print 'The adjacency matrix for D is : \\n',D\n",
"print 'sequence D is a simple path from node4 to node6'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex8.2 Pg 200"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"to find:minimal spanning tree\n",
"the adjacency matrix for the weighted graph(nodeA,nodeB...nodeF) of 6 nodes is :\n",
"edges of the graph\n",
"deleting edges without disconnecting the graph until 5 edges remain\n",
"weight of the minimal spanning tree is : 24\n",
"another method of finding a minimal spanning tree is :\n",
"weight of the minimal spanning tree is : 24\n"
]
}
],
"source": [
"from numpy import int32,mat\n",
"print 'to find:minimal spanning tree'\n",
"print 'the adjacency matrix for the weighted graph(nodeA,nodeB...nodeF) of 6 nodes is :'\n",
"K=mat([[0,0,7,0, 4, 7],[0, 0, 8, 3, 7 ,5],[7, 8, 0, 0, 6, 0],[0, 3 ,0 ,0, 0, 4],[4, 7 ,6 ,0 ,0 ,0],[7, 5, 0, 4, 0, 0]])\n",
"print 'edges of the graph'\n",
"AC=7# \n",
"AE=4#\n",
"AF=7#\n",
"BC=8#\n",
"BD=3#\n",
"BE=7#\n",
"BF=5#\n",
"CE=6#\n",
"DF=4#\n",
"M=[AC,AE,AF,BC,BD,BE,BF,CE,DF]# #set of all edges\n",
"V=int32(M)#\n",
"L=sorted(V, reverse = True) #edges sorted in decreasing order of their weights\n",
"print 'deleting edges without disconnecting the graph until 5 edges remain'\n",
"N=[BE,CE,AE,DF,BD]# #edges in minimum spanning tree\n",
"Sum=sum(N)#\n",
"print 'weight of the minimal spanning tree is : ',Sum\n",
"\n",
"\n",
"print 'another method of finding a minimal spanning tree is :'\n",
"K=sorted(V)#edges sorted in increasing order\n",
"N2=[BD,AE,DF,CE,AF]# #edges in minimum spanning tree\n",
"Sum2=sum(N2)#\n",
"print 'weight of the minimal spanning tree is : ',Sum2"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
PKxIO4_
_
Discrete Mathematics/Ch9_1.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter9 - Directed Graphs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex9.1 Pg 233"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"adjacency matrix of graph G is: \n",
"[[0 0 0 1]\n",
" [1 0 1 1]\n",
" [1 0 0 1]\n",
" [1 0 1 0]]\n",
"the number of ones in A is equal to the number of edges in the graph i.e 8\n"
]
}
],
"source": [
"from numpy import mat\n",
"A=mat([[0,0, 0, 1],[1, 0, 1, 1],[1, 0, 0, 1],[1, 0, 1, 0]])\n",
"print 'adjacency matrix of graph G is: \\n',A\n",
"A2=A**2\n",
"A3=A**3\n",
"print 'the number of ones in A is equal to the number of edges in the graph i.e 8'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex9.2 Pg 234"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"adjacency matrix of graph G is : \n",
"[[0 0 0 1]\n",
" [1 0 1 1]\n",
" [1 0 0 1]\n",
" [1 0 1 0]]\n",
"Replacing non zero entries of B4 with 1 ,we get path (reachability) matrix P is:\n",
"[1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"there are zero entries in P,therefore the graph is not strongly connected\n"
]
}
],
"source": [
"from numpy import mat\n",
"A=mat([[0, 0, 0, 1],[1, 0, 1, 1],[1 ,0 ,0 ,1],[1, 0, 1, 0]])\n",
"print 'adjacency matrix of graph G is : \\n',A\n",
"A4=A**4#\n",
"A3=A**3#\n",
"A2=A**2#\n",
"B4=A+A2+A3+A4#\n",
"B4=[4, 11, 7 ,7 ,0, 0, 0 ,0 ,3 ,7 ,4 ,4 ,4, 11, 7, 7]\n",
"for i in range(0,16):\n",
" if(B4[i]!=0):\n",
" B4[i]=1\n",
"print 'Replacing non zero entries of B4 with 1 ,we get path (reachability) matrix P is:\\n',B4\n",
"print 'there are zero entries in P,therefore the graph is not strongly connected'"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
PKxI~J!Discrete Mathematics/Ch11_1.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter11 - Properties of integers"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex11.2 Pg 319"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Division Algorithm\n",
"a and j have equal values.Hence division algorithm is proved\n"
]
}
],
"source": [
"from numpy import divide\n",
"print 'Division Algorithm'\n",
"a=4461# #dividend\n",
"b=16# #divisor\n",
"r=(a%b) #remainder\n",
"k=divide(a,b) #quotient\n",
"j=b*k+r #dividend=divisor*quotient+remainder\n",
"\n",
"a=-262# #dividend\n",
"b=3# #divisor\n",
"k=divide(a,b) #remainder\n",
"r=(a%b) #quotient\n",
"j=b*k+r #dividend=divisor*quotient+remainder\n",
"print 'a and j have equal values.Hence division algorithm is proved'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex11.4 Pg 320"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Divisibility and Primes\n",
"prime numbers less than 50 are\n",
"the prime factorisation of 21,24 and 1729 respectively are:\n",
"[3, 7] [2, 2, 2, 3] [7, 13, 19]\n"
]
}
],
"source": [
"from math import floor\n",
"print 'Divisibility and Primes'\n",
"x=50#\n",
"print 'prime numbers less than 50 are'\n",
"def get_primes(n):\n",
" numbers = set(range(n, 1, -1))\n",
" primes = []\n",
" while numbers:\n",
" p = numbers.pop()\n",
" primes.append(p)\n",
" numbers.difference_update(set(range(p*2, n+1, p)))\n",
" return primes\n",
"\n",
"y=get_primes(x)\n",
"\n",
"print 'the prime factorisation of 21,24 and 1729 respectively are:'\n",
"\n",
"def factors(n):\n",
" primfac = []\n",
" d = 2\n",
" while d*d <= n:\n",
" while (n % d) == 0:\n",
" primfac.append(d) # supposing you want multiple factors repeated\n",
" n //= d\n",
" d += 1\n",
" if n > 1:\n",
" primfac.append(n)\n",
" return primfac\n",
"\n",
"k=factors(21)\n",
"l=factors(24)\n",
"n=factors(1729)\n",
"print k,l,n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex11.5 Pg 321"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"the GCD of the following numbers is:\n",
"gcd(12,18) = [6]\n",
"gcd(12,-18) = [6]\n",
"gcd(12,-16) = [4]\n",
"gcd(29,15) = [1]\n",
"gcd(14,49) = [7]\n"
]
}
],
"source": [
"from numpy import int32\n",
"import numpy as np\n",
"print 'the GCD of the following numbers is:'\n",
"def gcd(a, b):\n",
" a, b = np.broadcast_arrays(a, b)\n",
" a = a.copy()\n",
" b = b.copy()\n",
" pos = np.nonzero(b)[0]\n",
" while len(pos) > 0:\n",
" b2 = b[pos]\n",
" a[pos], b[pos] = b2, a[pos] % b2\n",
" pos = pos[b[pos]!=0]\n",
" return abs(a)\n",
"print \"gcd(12,18) = \",gcd([12],[18])\n",
"print \"gcd(12,-18) = \",gcd([12],[-18])\n",
"print \"gcd(12,-16) = \",gcd([12],[-16])\n",
"print \"gcd(29,15) = \",gcd([29],[15])\n",
"print \"gcd(14,49) = \",gcd([14],[49])\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex11.6 Pg 322"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Euclidean Algorithm\n",
"540.0\n",
"168.0\n",
"36.0\n",
"24.0\n",
"for the equation 540*x+168*y=12,we are given\n",
"x=5 and y=16\n"
]
}
],
"source": [
"from numpy import floor\n",
"print 'Euclidean Algorithm'\n",
"a=[540,168,36,24]#\n",
"b=[168,36,24,12]#\n",
"thegcd=[]\n",
"for i in range(0,4):\n",
" thegcd.append(gcd(a,b))\n",
" \n",
"\n",
"\n",
"def myf(dividend,divisor):\n",
" quotient=floor(dividend/divisor)#\n",
" rem=(dividend%divisor)#\n",
" k=quotient*divisor+rem#\n",
" print k\n",
" if(rem!=0):\n",
" myf(divisor,rem) \n",
"\n",
"\n",
"\n",
"myf(540,168)\n",
"\n",
"print 'for the equation 540*x+168*y=12,we are given'\n",
"a=540#\n",
"b=168#\n",
"c=24#\n",
"d=36#\n",
"d=a-3*b# #Eqn (1)\n",
"c=b-4*d# #Eqn (2)\n",
"k=d-1*c# #Eqn (3)\n",
"5*d-1*b# #Eqn (4)\n",
"k=d-b+4*d# #substituting value of c in Eqn (3) from Eqn (2) \n",
"r=5*a-16*b# \n",
"if(r==k):\n",
" print 'x=5 and y=16'# \n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex11.9 Pg 324"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"gcd(a,b) = [792]\n",
"lcm(a,b) = 183783600\n"
]
}
],
"source": [
"a=2**4*3**3*7*11*13\n",
"b=2**3*3**2*5**2*11*17\n",
"d=gcd([a],[b])\n",
"print \"gcd(a,b) =\",d\n",
"lcm1=2**4*3**3*5**2*7*11*13*17 #lcm is the product of those primes which appear in either a or b\n",
"print \"lcm(a,b) =\",lcm1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex11.19 Pg 332"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"solving for the congruence equation 8x @ 12(mod 28) ,where @ is the sign for congruence\n",
"k is the unique solution of the equation \n",
"solutions of the original equation at d=4\n",
"[5]\n",
"[12]\n",
"[19]\n",
"[26]\n"
]
}
],
"source": [
"print 'solving for the congruence equation 8x @ 12(mod 28) ,where @ is the sign for congruence'\n",
"a=8#\n",
"b=12#\n",
"m=28#\n",
"d= gcd([a],[m])#\n",
"a1= a/d#\n",
"b1= b/d#\n",
"m1= m/d#\n",
" \n",
"def f(x):\n",
" yd= (a1*x)-b1\n",
" return yd\n",
" \n",
"print 'k is the unique solution of the equation '\n",
"for i in range(0,m1):\n",
" x=i#\n",
" p=f(x)#\n",
" if((p%m1) == 0):\n",
" k=x\n",
" break#\n",
"\n",
"s1=[k]#\n",
"s2=k+m1#\n",
"s3=k+(m1*2)#\n",
"s4=k+(m1*3)#\n",
"print 'solutions of the original equation at d=4'\n",
"print s1\n",
"print s2\n",
"print s3\n",
"print s4"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
PKxIN2,
,
!Discrete Mathematics/Ch12_1.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter12- Algebric systems"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex12.4 Pg 365"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"since a and b are not equal so subtraction is non-commutative on Z(set of integers)\n",
"since g and k are not equal matrix multiplication is non-commutative\n",
"since h and j are not equal so exponential operation is non associative on the set of positive integers N\n"
]
}
],
"source": [
"from numpy import mat\n",
"a=(8-4)-3\n",
"b=8-(4-3)\n",
"print 'since a and b are not equal so subtraction is non-commutative on Z(set of integers)'\n",
"\n",
"a=mat([[1, 2],[3, 4]])\n",
"b=mat([[5 ,6],[0, -2]])\n",
"g= a*b\n",
"k= b*a\n",
"print 'since g and k are not equal matrix multiplication is non-commutative'\n",
"\n",
"h=(2**2)**3\n",
"j=2**(2**3)\n",
"print 'since h and j are not equal so exponential operation is non associative on the set of positive integers N'\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex12.17 Pg 380"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"roots of f(t) are as follows:\n",
"2\n",
"-3/2 + sqrt(17)/2\n",
"-sqrt(17)/2 - 3/2\n"
]
}
],
"source": [
"from sympy import symbols, solve\n",
"t=symbols('t')\n",
"f=t**3+t**2-8*t+4\n",
"r=solve(f,t)\n",
"print 'roots of f(t) are as follows:'\n",
"for r in r:\n",
" print r"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex12.18 Pg 382"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"the real roots of h(t) are 1 and -2\n",
"-2\n",
"1\n",
"3/2 - sqrt(11)*I/2\n",
"3/2 + sqrt(11)*I/2\n",
"\n",
"roots of f(t) are as follows:\n",
"-1/2 + sqrt(13)/2\n",
"2 - 3*I\n",
"2 + 3*I\n",
"-sqrt(13)/2 - 1/2\n"
]
}
],
"source": [
"from sympy import symbols, solve\n",
"t=symbols('t')\n",
"h=t**4-2*t**3+11*t-10\n",
"r=solve(h,t)\n",
"print 'the real roots of h(t) are 1 and -2'\n",
"for r in r:\n",
" print r\n",
"\n",
"t=symbols('t')\n",
"f=t**4-3*t**3+6*t**2+25*t-39\n",
"r=solve(f,t)\n",
"print '\\nroots of f(t) are as follows:'\n",
"for r in r:\n",
" print r\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
PKxIԹ!Discrete Mathematics/Ch15_1.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter15 - Boolean Algebra"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex15.2 Pg 479"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"lcm(2,14) : 14\n"
]
}
],
"source": [
"from fractions import gcd\n",
"D=[1,2,5,7,10,14,35,70]#\n",
"a = 2# #a and b belong to D\n",
"b = 14#\n",
"def lcm(*numbers):\n",
" \"\"\"Return lowest common multiple.\"\"\" \n",
" def lcm(a, b):\n",
" return (a * b) // gcd(a, b)\n",
" return reduce(lcm, numbers, 1)\n",
"print \"lcm(2,14) : \",lcm(2,14)\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
PKxIw4((!Discrete Mathematics/Ch16_1.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter16 - Recurrance relations"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex16.14 Pg 536"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"for recurrence relation a(n)=5*a(n-1)-4*a(n-2)+n**2\n",
"Value of a(2) is: 10 \n",
"\n",
"Value of a(3) is: 51 \n",
"\n",
"for recurrence relation a(n)=2*a(n-1)*a(n-2)+n**2\n",
"Value of a(2) is: 8 \n",
"\n",
"Value of a(3) is: 41 \n",
"\n",
"for recurrence relation a(n)=n*a(n-1)+3*a(n-2)\n",
"Value of a(2) is: 7 \n",
"\n",
"Value of a(3) is: 27 \n",
"\n",
"for recurrence relation a(n)=2*a(n-1)+5*a(n-2)-6*a(n-3)\n",
"Value of a(2) is: 1 \n",
"\n",
"Value of a(3) is: 3 \n",
"\n"
]
}
],
"source": [
"a=[]#\n",
"a.append(1)# #initial condition\n",
"a.append(2)# #initial condition\n",
"print 'for recurrence relation a(n)=5*a(n-1)-4*a(n-2)+n**2' #this is a second order recurrence relation with constant coefficients.It is non homogenous because of the n**2\n",
"for n in range(2,4):\n",
" a.append(5*a[n-1]-4*a[n-2]+n**2)\n",
" print 'Value of a(%d) is: %d \\n'%(n,a[n])\n",
"\n",
" \n",
"a=[]#\n",
"a.append(1)# #initial condition\n",
"a.append(2)# #initial condition\n",
"print 'for recurrence relation a(n)=2*a(n-1)*a(n-2)+n**2' #this recurrence relation is not linear\n",
"for n in range(2,4):\n",
" a.append(2*a[(n-1)]*a[(n-2)]+n**2)\n",
" print 'Value of a(%d) is: %d \\n'%(n,a[n])\n",
"\n",
" \n",
"a=[]#\n",
"a.append(1)# #initial condition\n",
"a.append(2)# #initial condition\n",
"print 'for recurrence relation a(n)=n*a(n-1)+3*a(n-2)' #this is a homogenous linear second order recurrence relation without constant coefficients because the coefficient of a[n-1] is n,not a constant\n",
"for n in range(2,4):\n",
" a.append(n*a[(n-1)]+3*a[(n-2)])\n",
" print 'Value of a(%d) is: %d \\n'%(n,a[n])\n",
"\n",
"\n",
" \n",
"a=[]#\n",
"a.append(1)# #initial condition\n",
"a.append(2)# #initial condition\n",
"a.append(1)# #initial condition\n",
"print 'for recurrence relation a(n)=2*a(n-1)+5*a(n-2)-6*a(n-3)' #this is a homogenous linear third order recurrence relation with constant coefficients.Thus we need three,not two,initial conditions to yield a unique solution of the recurrence relation\n",
"for n in range(2,4):\n",
" a.append(2*a[(n-1)]+5*a[(n-2)]-6*a[(n-3)])\n",
" print 'Value of a(%d) is: %d \\n'%(n,a[n])\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex16.15 Pg 539"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"recurrence relation of Fibonacci numbers f[n]=f[n-1]+f[n-2]\n",
"characterstic equation of the recurrence relation is: x**2 - x - 1\n",
"roots of the characterstic equation j1,j2 are :\n",
"1/2 + sqrt(5)/2 \t-sqrt(5)/2 + 1/2 \t\n",
"\n",
"for general equation fn=Ar**n+Br**n,values of Aand B respectively are calculated as:\n",
"initial condition at n=0 and n=1 respectively are:\n",
"[[ 1.618034 -0.618034]] [[ 2.61803403 0.38196603]]\n",
"thus the solution is f[n]=0.4472136*((1.618034)**n-(- 0.4472136)**n)]\n"
]
}
],
"source": [
"from numpy import mat\n",
"from sympy import symbols, solve\n",
"print 'recurrence relation of Fibonacci numbers f[n]=f[n-1]+f[n-2]' \n",
"x=symbols('x')\n",
"g=x**2-x-1\n",
"print 'characterstic equation of the recurrence relation is:',g\n",
"j=solve(g,x)#\n",
"print 'roots of the characterstic equation j1,j2 are :'\n",
"for x in j:\n",
" print x,'\\t',\n",
"\n",
"print '\\n'\n",
"print 'for general equation fn=Ar**n+Br**n,values of Aand B respectively are calculated as:'\n",
"print 'initial condition at n=0 and n=1 respectively are:'\n",
"f1=1# \n",
"f2=1# \n",
"#putting the values of f1 and f2 we get the equations to solve \n",
"\n",
"D=mat([[1.6180340, -0.618034],[(1.6180340)**2, (-0.618034)**2]])#\n",
"K=mat([[1, 1]])\n",
"c=[]#\n",
"c=D/K#\n",
"A=c[0]\n",
"B=c[1]\n",
"print A, B\n",
"print 'thus the solution is f[n]=0.4472136*((1.618034)**n-(- 0.4472136)**n)]'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex16.17 Pg 543"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The recurrence relation t[n]=4(t[n-1]-t[n-2])\n",
"characterstic polynomial equation for the above recurrence relation : x**2 - 4*x + 4\n",
"roots of the characterstic equation j1,j2 : \n",
"2 \t\n",
"\n",
"the general solution is t[n]=n*2**n\n",
"initial condition at n=0 and n=1 respectively are:\n",
"[[ 1. 1. ]\n",
" [-0.5 -0.5]] \t[[ 1. 1. ]\n",
" [-0.5 -0.5]] \t\n",
"thus the solution is t{n}=2*n-n*2**(n-1)\n"
]
}
],
"source": [
"from numpy import mat\n",
"from sympy import symbols, solve\n",
"print 'The recurrence relation t[n]=4(t[n-1]-t[n-2])'\n",
"x=symbols('x')\n",
"g=x**2-4*x+4\n",
"print 'characterstic polynomial equation for the above recurrence relation : ',g \n",
"j=solve(g, x)\n",
"print 'roots of the characterstic equation j1,j2 : '\n",
"for x in j:\n",
" print x,'\\t'\n",
"print ''\n",
"print 'the general solution is t[n]=n*2**n' \n",
"print 'initial condition at n=0 and n=1 respectively are:'\n",
"t0=1#\n",
"t1=1#\n",
"#putting the values of t0 and t1 we get the equations to solve\n",
"D=mat([[1, 0],[2, 2]])\n",
"K=mat([[1, 1]])\n",
"from numpy.linalg import solve\n",
"c=solve(D,K)\n",
"for cc in c:\n",
" print c,'\\t',\n",
"print ''\n",
"D=mat([[1, 0],[2, 2]])\n",
"K=mat([[1, 1]])\n",
"c=D/K#\n",
"c1=c[0]\n",
"c2=c[1]\n",
"print 'thus the solution is t{n}=2*n-n*2**(n-1)'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex16.18 Pg 544"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The recurrence relation a[n]=2*a[n-1]-3a[n-2]\n",
"characterstic polynomial equation for the above recurrence relation : x**2 - 2*x - 3\n",
"roots of the characterstic equation j1,j2 : \n",
"-1 \t3 \t\n",
"the general solution is a[n]=c1*3**n+c2*(-1)**n\n",
"initial condition at n=0 and n=1 respectively are:\n",
"[[1 0]] [[ 3 -1]]\n",
"thus the solution is a[n]=0.75*(3**n)+0.25*(1**n)\n"
]
}
],
"source": [
"from numpy import mat\n",
"from sympy import symbols, solve\n",
"print 'The recurrence relation a[n]=2*a[n-1]-3a[n-2]'\n",
"x=symbols('x')\n",
"g=x**2-2*x-3\n",
"print 'characterstic polynomial equation for the above recurrence relation : ',g \n",
"from sympy import solve\n",
"j=solve(g, x)#\n",
"print 'roots of the characterstic equation j1,j2 : '\n",
"for x in j:\n",
" print x,'\\t',\n",
"print \"\"\n",
"print 'the general solution is a[n]=c1*3**n+c2*(-1)**n' \n",
"print 'initial condition at n=0 and n=1 respectively are:'\n",
"#putting the values of t0 and t1 we get the equations to solve\n",
"a0=1#\n",
"a1=2#\n",
"D=mat([[1, 1],[3, -1]])\n",
"K=mat([[1, 2]])\n",
"c=D/K#\n",
"c1=c[0]\n",
"c2=c[1]\n",
"print c1, c2\n",
"print 'thus the solution is a[n]=0.75*(3**n)+0.25*(1**n)'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex16.19 Pg 556"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The recurrence relation a[n]=11*a[n-1]-39*a[n-2]+45*a[n-3]\n",
"characterstic polynomial equation for the above recurrence relation : x**3 - 11*x**2 + 39*x - 45\n",
"roots of the characterstic equation j1,j2 : \n",
"3 \t5 \t\n",
"hence the general solution is:a[n]=c1*(3**n)+c2*n*(3**n)+c3*(5**n)\n",
"initial condition at n=0 and n=1 respectively are:\n",
"[[0 0 0]] [[0 0 0]] [[1 1 1]]\n",
"thus the solution is a[n]=(4-2*n)*(3**n)+5**n\n"
]
}
],
"source": [
"from numpy import mat\n",
"from sympy import symbols, solve\n",
"print 'The recurrence relation a[n]=11*a[n-1]-39*a[n-2]+45*a[n-3]'\n",
"x=symbols('x')\n",
"g=x**3-11*x**2+39*x-45\n",
"print 'characterstic polynomial equation for the above recurrence relation : ',g \n",
"j=solve(g, x)\n",
"print 'roots of the characterstic equation j1,j2 : '\n",
"for x in j:\n",
" print x,'\\t',\n",
"print ''\n",
"print 'hence the general solution is:a[n]=c1*(3**n)+c2*n*(3**n)+c3*(5**n)'\n",
"print 'initial condition at n=0 and n=1 respectively are:'\n",
"#putting the values of t0 and t1 we get the equations to solve\n",
"a0=5#\n",
"a1=11#\n",
"a2=25#\n",
"D=mat([[1, 0 ,1],[3, 3, 5],[9, 18, 25]])\n",
"K=mat([[5, 11, 25]])\n",
"c=D/K#\n",
"c1=c[0]\n",
"c2=c[1]\n",
"c3=c[2]\n",
"print c1, c2, c3\n",
"print 'thus the solution is a[n]=(4-2*n)*(3**n)+5**n'"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
PKxIoO= Discrete Mathematics/Ch1_1.ipynbPKxIT4E;; Discrete Mathematics/Ch3_1.ipynbPKxI͝&& >!Discrete Mathematics/Ch5_1.ipynbPKxIk^8^8 mHDiscrete Mathematics/Ch6_1.ipynbPKxI=PmPm Discrete Mathematics/Ch7_1.ipynbPKxIϗ< Discrete Mathematics/Ch8_1.ipynbPKxIO4_
_
WDiscrete Mathematics/Ch9_1.ipynbPKxI~J!Discrete Mathematics/Ch11_1.ipynbPKxIN2,
,
!I+Discrete Mathematics/Ch12_1.ipynbPKxIԹ!8Discrete Mathematics/Ch15_1.ipynbPKxIw4((!=Discrete Mathematics/Ch16_1.ipynbPK^g