PK„IâFk‘Z‘Z/Elements of discrete mathematics/Chapter1.ipynb{
"metadata": {
"name": "",
"signature": "sha256:de0a0f66aff079301941637787a8030ad1f216bb6fd8c51b1e13503001244ca2"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"1 Sets and Propositions"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 11:Page 21"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"To find the number of computers that support one or more of the three kinds of hardware considered, namely;Floating point arithmetic unit, magnetic disk storage and graphical display terminal.\"\n",
"A1=2#Set of computers with floating point arithmetic unit\n",
"A2=5#Set of computers with magetic disk storage\n",
"A3=3#Set of computers with graphical display terminal\n",
"A1_intersection_A2=2#Set of computers with floating point arithmetic unit and magentic disk storage\n",
"A1_intersection_A3=1#Set of computers with floating point arithmetic unit and graphical display terminal\n",
"A2_intersection_A3=3#Set of computers with magnetic disk storage and graphical display terminal \n",
"A1_intersection_A2_intersection_A3=1#Set of computers with floating point arithmetic, magnetic disk storage and graphical display terminal\n",
"#By the principle of inclusion and exclusion\n",
"A1_union_A2_union_A3=A1+A2+A3-A1_intersection_A2-A1_intersection_A3-A2_intersection_A3+A1_intersection_A2_intersection_A3\n",
"print A1_union_A2_union_A3,\"of the six computers have one or more of the three kinds of hardware considered\"\n",
"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"To find the number of computers that support one or more of the three kinds of hardware considered, namely;Floating point arithmetic unit, magnetic disk storage and graphical display terminal.\n",
"5 of the six computers have one or more of the three kinds of hardware considered\n"
]
}
],
"prompt_number": 1
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 12:Page 21"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"We consider 200 students of courses Discrete Mathematics and Economics. A party is being organized which can be attended only by students who are not in either of the courses as these two courses have exams scheduled the next day.\"\n",
"students=200# Total number of students \n",
"DM=50 # Number of students who have taken Discrete Mathematics\n",
"ECO=140 # Number of students who have taken Economics\n",
"DM_and_ECO=24 # Number of students who have taken both Discrete Mathematics and Economics\n",
"one_or_both=(DM+ECO-DM_and_ECO) # Number of students who have taken either one or both the courses\n",
"print \"Number of students who take either one or both the courses is equal to\",one_or_both\n",
"print \"Consequently, the number of students who will be at the party is\", (students-one_or_both)\n",
"print \"Suppose that 60 of the 200 are underclass students \"\n",
"UC_students=60 # Number of underclass students\n",
"dm=20 # Number of underclass students who have taken Discrete Mathematics\n",
"eco=45 # Number of underclass students who have taken Economics\n",
"dm_and_eco=16 # Number of underclass students who have taken both Discrete Mathematics and Economics\n",
"# A1 is the set of students in the course Discrete Mathematics\n",
"# A2 is the set of students in the course Economics\n",
"# A3 is the set of underclass students\n",
"A1_union_A2_union_A3=DM+ECO+UC_students-DM_and_ECO-dm-eco+dm_and_eco\n",
"print \"Thus, the number of upperclass students who will go to the party is\",(students-A1_union_A2_union_A3)\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"We consider 200 students of courses Discrete Mathematics and Economics. A party is being organized which can be attended only by students who are not in either of the courses as these two courses have exams scheduled the next day.\n",
"Number of students who take either one or both the courses is equal to 166\n",
"Consequently, the number of students who will be at the party is 34\n",
"Suppose that 60 of the 200 are underclass students \n",
"Thus, the number of upperclass students who will go to the party is 23\n"
]
}
],
"prompt_number": 2
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 13:Page 22"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"To find the number of cars which have neither a radio nor an air conditioner nor white-wall tires out of the thirty cars assembled in a factory\"\n",
"cars=30 # Total number of cars assembled in a factory\n",
"A1=15 # Set of cars with radio\n",
"A2=8 # Set of cars with air-conditioner\n",
"A3=6 # Set of cars with white-wall tires\n",
"A1_intersection_A2_intersection_A3=3\n",
"A1_intersection_A2=3 # Since |A1_intersection_A2| >=|A1_intersection_A2_intersection_A3|\n",
"A1_intersection_A3=3 # Since |A1_intersection_A3| >=|A1_intersection_A2_intersection_A3|\n",
"A2_intersection_A3=3 # Since |A2_intersection_A3| >=|A1_intersection_A2_intersection_A3|\n",
"A1_union_A2_union_A3=A1+A2+A3-A1_intersection_A2-A1_intersection_A3-A2_intersection_A3+A1_intersection_A2_intersection_A3 # By the principle of inclusion and exclusion\n",
"print \"There are at most\",A1_union_A2_union_A3,\"cars that have one or more options.\"\n",
"print \"Consequently,there are at least\",(cars-A1_union_A2_union_A3),\"cars that do not have any options\"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"To find the number of cars which have neither a radio nor an air conditioner nor white-wall tires out of the thirty cars assembled in a factory\n",
"There are at most 23 cars that have one or more options.\n",
"Consequently,there are at least 7 cars that do not have any options\n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 14:Page 24"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"To determine the number of integers between 1 and 250 that are divisible by 2,3,5,7\"\n",
"A1=250/2 # Number of integers between 1 and 250 that are divisible by 2\n",
"A2=250/3 # Number of integers between 1 and 250 that are divisible by 3\n",
"A3=250/5 # Number of integers between 1 and 250 that are divisible by 5\n",
"A4=250/7 # Number of integers between 1 and 250 that are divisible by 7\n",
"A1_intersection_A2=250/(2*3) # Number of integers between 1 and 250 that are divisible by 2 and 3\n",
"A1_intersection_A3=250/(2*5) # Number of integers between 1 and 250 that are divisible by 2 and 5\n",
"A1_intersection_A4=250/(2*7) # Number of integers between 1 and 250 that are divisible by 2 and 7\n",
"A2_intersection_A3=250/(3*5)# Number of integers between 1 and 250 that are divisible by 3 and 5\n",
"A2_intersection_A4=250/(3*7)# Number of integers between 1 and 250 that are divisible by 3 and 7\n",
"A3_intersection_A4=250/(5*7)# Number of integers between 1 and 250 that are divisible by 5 and 7\n",
"A1_intersection_A2_intersection_A3=250/(2*3*5) # Number of integers between 1 and 250 that are divisible by 2,3 and 5\n",
"A1_intersection_A2_intersection_A4=250/(2*3*7) # Number of integers between 1 and 250 that are divisible by 2,3 and 7\n",
"A1_intersection_A3_intersection_A4=250/(2*5*7) # Number of integers between 1 and 250 that are divisible by 2,5 and 7\n",
"A2_intersection_A3_intersection_A4=250/(3*5*7) # Number of integers between 1 and 250 that are divisible by 3,5 and 7\n",
"A1_intersection_A2_intersection_A3_intersection_A4=250/(2*3*5*7) # Number of integers between 1 and 250 that are divisible by 2,3,5 and 7\n",
"A1_union_A2_union_A3_union_A4=A1+A2+A3+A4-A1_intersection_A2-A1_intersection_A3-A1_intersection_A4-A2_intersection_A3-A2_intersection_A4-A3_intersection_A4+A1_intersection_A2_intersection_A3+A1_intersection_A2_intersection_A4+A1_intersection_A3_intersection_A4+A2_intersection_A3_intersection_A4-A1_intersection_A2_intersection_A3_intersection_A4\n",
"print \"A1 is the set of integers between 1 and 250 that are divisible by 2\"\n",
"print \"A2 is the set of integers between 1 and 250 that are divisible by 3\"\n",
"print \"A3 is the set of integers between 1 and 250 that are divisible by 5\"\n",
"print \"A4 is the set of integers between 1 and 250 that are divisible by 7\"\n",
"print \"|A1_union_A2_union_A3_union_A4|=\",A1_union_A2_union_A3_union_A4\n",
"\n",
"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"To determine the number of integers between 1 and 250 that are divisible by 2,3,5,7\n",
"A1 is the set of integers between 1 and 250 that are divisible by 2\n",
"A2 is the set of integers between 1 and 250 that are divisible by 3\n",
"A3 is the set of integers between 1 and 250 that are divisible by 5\n",
"A4 is the set of integers between 1 and 250 that are divisible by 7\n",
"|A1_union_A2_union_A3_union_A4|= 193\n"
]
}
],
"prompt_number": 4
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 15:Page 29"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"Truth table for (p and q)and (not p)\"\n",
"def truth_table(p,q):\n",
" return (p and q) and (not p)#Logical representation of the given boolean exoression\n",
"print \"p\\tq\\t(p and q)\\t(not p)\\t(p and q) and (not p)\"\n",
"for a in (True,False):\n",
" for b in (True,False):#Loops that generate the possible input values\n",
" print a,\"\\t\",b,\"\\t\",a and b,\"\\t\\t\",not a,\"\\t\",truth_table(a,b)\n",
" \n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Truth table for (p and q)and (not p)\n",
"p\tq\t(p and q)\t(not p)\t(p and q) and (not p)\n",
"True \tTrue \tTrue \t\tFalse \tFalse\n",
"True \tFalse \tFalse \t\tFalse \tFalse\n",
"False \tTrue \tFalse \t\tTrue \tFalse\n",
"False \tFalse \tFalse \t\tTrue \tFalse\n"
]
}
],
"prompt_number": 5
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 21:Page 33"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"Consider the truth tables of (P and negation_P)\"\n",
"print \"Here all the entries in the last column are false\"\n",
"def truth_table_and(p):\n",
" return p and (not p)#Representation of logical AND\n",
" \n",
"print \"p\\tnegation_p\\tp_and_negation_p\"\n",
"print \"---------------------------------------------\"\n",
"for q in (True,False):#generates the combination of inputs\n",
" res=truth_table_and(q)\n",
" print q,\"\\t\\t\",not q,\"\\t\\t\",res\n",
" \n",
" \n",
"print \"Consider the truth tables of (P or negation_P)\"\n",
"print \"Here all the entries in the last column are true \"\n",
"def truth_table_or(p):\n",
" return p or (not p)#Representation of logical OR\n",
" \n",
"print \"p\\tnegation_p\\tp_or_negation_p\"\n",
"print \"----------------------------------------------\"\n",
"for q in (True,False):#generates the combination of inputs\n",
" res=truth_table_or(q)\n",
" print q,\"\\t\\t\",not q,\"\\t\\t\",res\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Consider the truth tables of (P and negation_P)\n",
"Here all the entries in the last column are false\n",
"p\tnegation_p\tp_and_negation_p\n",
"---------------------------------------------\n",
"True \t\tFalse \t\tFalse\n",
"False \t\tTrue \t\tFalse\n",
"Consider the truth tables of (P or negation_P)\n",
"Here all the entries in the last column are true \n",
"p\tnegation_p\tp_or_negation_p\n",
"----------------------------------------------\n",
"True \t\tFalse \t\tTrue\n",
"False \t\tTrue \t\tTrue\n"
]
}
],
"prompt_number": 6
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 23:Page 35"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"Restaurent 1 says 'Good food is not cheap'\"\n",
"print \"Restaurent 2 says 'Cheap food is not good'\"\n",
"#Generating prepositions from the given sentences\n",
"g='Food is good'\n",
"c='Food is cheap'\n",
"print \"g->negation c means 'Good food is not cheap'\"\n",
"print \"c->negation g means 'Cheap food is not good'\"\n",
"def g_implies_negation_c(g,c):\n",
" if g==True and not(c)==False:# Implementation of logical implication\n",
" return 'False'\n",
" else:\n",
" return 'True'\n",
"\n",
"def c_implies_negation_g(g,c):\n",
" if c==True and not g==False:# Implementation of logical implication\n",
" return 'False'\n",
" else:\n",
" return 'True'\n",
"print \"g\\t\\tc\\t|\\t\\tnegation_g\\t\\t\\tnegation_c\\t\\t\\tg_implies_negation_c\\t\\t\\tc_implies_negation_g\"\n",
"print \"---------------------------------------------------------------------------------------------------------------------------------------------------------------\"\n",
"for a in (False,True):#Generate the possible inputs\n",
" for b in (False,True):\n",
" print (\"%5s%10s\\t\\t|%20s%30s%35s%40s\"%(a,b,not a,not b,g_implies_negation_c(a,b),c_implies_negation_g(a,b)))\n",
" \n",
" \n",
"print \"Since both g_implies_negation_c and c_implies_negation_g values in the truth table are similar, it is proved that 'Good food is not cheap' and 'Cheap food is not good are the same'\"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Restaurent 1 says 'Good food is not cheap'\n",
"Restaurent 2 says 'Cheap food is not good'\n",
"g->negation c means 'Good food is not cheap'\n",
"c->negation g means 'Cheap food is not good'\n",
"g\t\tc\t|\t\tnegation_g\t\t\tnegation_c\t\t\tg_implies_negation_c\t\t\tc_implies_negation_g\n",
"---------------------------------------------------------------------------------------------------------------------------------------------------------------\n",
"False False\t\t| True True True True\n",
"False True\t\t| True False True True\n",
" True False\t\t| False True True True\n",
" True True\t\t| False False False False\n",
"Since both g_implies_negation_c and c_implies_negation_g values in the truth table are similar, it is proved that 'Good food is not cheap' and 'Cheap food is not good are the same'\n"
]
}
],
"prompt_number": 7
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 24:Page 35"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def implication(p,q,r,s):#Implementation of logical implicaion\n",
" part1=((p and q) or (p and r) )\n",
" if part1==True and s==False:\n",
" return 'False'\n",
" else:\n",
" return 'True'\n",
"def equivalent(p,q,r,s):#Implementation of logical expression\n",
" return (((not p) or((not q) and (not r)))or s)\n",
"print \"\\tp\\tq\\tr\\t\\ts\\t\\t|((p and q)or(p and q))->s\\t((negation_p or(negation_q and negation_r))or s)\"\n",
"print \"--------------------------------------------------------------------------------------------------------------------------------------\"\n",
"for a in (False,True):\n",
" for b in (False,True):\n",
" for c in (False,True):\n",
" for d in (False,True):#Genetates all possible combinations of inputs\n",
" print (\"%8s%8s%10s%15s|%35s%35s\" %(a,b,c,d,implication(a,b,c,d),equivalent(a,b,c,d)))\n",
" \n",
"print \"Therefore, they are proved to be equivalent\"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\tp\tq\tr\t\ts\t\t|((p and q)or(p and q))->s\t((negation_p or(negation_q and negation_r))or s)\n",
"--------------------------------------------------------------------------------------------------------------------------------------\n",
" False False False False| True True\n",
" False False False True| True True\n",
" False False True False| True True\n",
" False False True True| True True\n",
" False True False False| True True\n",
" False True False True| True True\n",
" False True True False| True True\n",
" False True True True| True True\n",
" True False False False| True True\n",
" True False False True| True True\n",
" True False True False| False False\n",
" True False True True| True True\n",
" True True False False| False False\n",
" True True False True| True True\n",
" True True True False| False False\n",
" True True True True| True True\n",
"Therefore, they are proved to be equivalent\n"
]
}
],
"prompt_number": 10
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 55:Page 55"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"EUCLIDEAN ALGORITHM\"\n",
"def GCD(n,m):#Euclidean algorithm to compute GCD\n",
" if n>=m and (n%m==0):\n",
" return m\n",
" else:\n",
" return GCD(m,n%m)\n",
"print \"GCD(25,6) by Euclidean algorithm =\",GCD(25,6),\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"EUCLIDEAN ALGORITHM\n",
"GCD(25,6) by Euclidean algorithm = 1\n"
]
}
],
"prompt_number": 11
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 56:Page 55"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"EUCLIDEAN ALGORITHM\"\n",
"def GCD(n,m):#Euclidean algorithm to compute GCD\n",
" if n>=m and (n%m==0):\n",
" return m\n",
" else:\n",
" return GCD(m,n%m)\n",
"print \"GCD(18,4) by Euclidean algorithm =\",GCD(18,4),#Final comma in all print statements is to eliminate new line character in the end of it\n",
"print \"\\nGCD(26,2) by Euclidean algorithm =\",GCD(26,2),\n",
"print \"\\nGCD(28,8) by Euclidean algorithm =\",GCD(28,8),\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"EUCLIDEAN ALGORITHM\n",
"GCD(18,4) by Euclidean algorithm = 2 \n",
"GCD(26,2) by Euclidean algorithm = 2 \n",
"GCD(28,8) by Euclidean algorithm = 4\n"
]
}
],
"prompt_number": 12
}
],
"metadata": {}
}
]
}PK„I?¡®Ÿôô/Elements of discrete mathematics/Chapter2.ipynb{
"metadata": {
"name": "",
"signature": "sha256:2cbc1da90c4c7b54c1033f2cfac603ed9480419c909b33f66bc0d4ea974287c3"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"2 Permutations, combinations, and discrete probability "
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 01:page 69"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"This is to find the number of ways to schedule three exams in five days such that no two exams fall on the same day\"\n",
"first_exam=5#number of available days for the first exam\n",
"second_exam=4#number of available days for the second exam\n",
"third_exam=3#number of available days for the third exam\n",
"total=first_exam*second_exam*third_exam#number of combinations\n",
"print \"Total number of ways is :\",total\n",
"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"This is to find the number of ways to schedule three exams in five days such that no two exams fall on the same day\n",
"Total number of ways is : 60\n"
]
}
],
"prompt_number": 1
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 02:Page 69"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"To find the number of ways in which seven rooms can be allocated to four programmers\"\n",
"a=7 # The number of possible rooms for first programmer\n",
"b=6 # The number of possible rooms for second programmer\n",
"c=5 # The number of possible rooms for third programmer\n",
"d=4 # The number of possible rooms for fourth programmer\n",
"res=a*b*c*d\n",
"print \"The assignment can be made in \",res,\"different ways\"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"To find the number of ways in which seven rooms can be allocated to four programmers\n",
"The assignment can be made in 840 different ways\n"
]
}
],
"prompt_number": 2
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 03:Page 69"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"Number of four digit decimal numbers which have no repeated digits\"\n",
"thousands_place=9 # Only nine digits can be placed there. zero cannot be placed there as it will become a three digit number\n",
"hundreds_place=9 #As one slot is already filled with a number, the remaining nine digits can only be placed here\n",
"tens_place=8 # As two digits have already been used, there are only eight more digits for this place\n",
"ones_place=7 # Three digits have occupied three places and only seven digits remain more\n",
"total=thousands_place*hundreds_place*tens_place*ones_place\n",
"print total,\" possible four digit decimal numbers can be formed without any repetition of digits\"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Number of four digit decimal numbers which have no repeated digits\n",
"4536 possible four digit decimal numbers can be formed without any repetition of digits\n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 04:Page 70"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"print \"To find the number of ways in which we can make up strings of four distinct letters followed by three distinct digits\"\n",
"def permutations(n,r):\n",
" res=math.factorial(n)/math.factorial(n-r)#Mathematical formula for permutations\n",
" return res\n",
"print \"Total number of possible ways are\",permutations(26,4)*permutations(10,3)\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"To find the number of ways in which we can make up strings of four distinct letters followed by three distinct digits\n",
"Total number of possible ways are 258336000\n"
]
}
],
"prompt_number": 4
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 05:Page 70"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"To schedule three examinations within a five day period with no restrictions on the number of examinations scheduled each day\"\n",
"print \"The total number of ways are\", pow(5,3)\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"To schedule three examinations within a five day period with no restrictions on the number of examinations scheduled each day\n",
"The total number of ways are 125\n"
]
}
],
"prompt_number": 5
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 08:Page 71"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"We print all five-digit numbers on slips of paper with one number on each slip.\"\n",
"print \"We have\",pow(10,5),\"distinct five-digit numbers\" \n",
"print \"Among these numbers\",pow(5,5),\"of them can be read either right side up or upside down\"#Since the digits 0,1,6,8,9 become 0,1,9,8,6 when they are read upside down, there are pairs of numbers that can share the same slip if the slips are read right side up or upside down\n",
"print \"There are\",pow(5,5)-(3*pow(5,2)),\"numbers that can be read either right side up or upside down but will read differently.So,hey can be divided into pairs so that every pair of numbers can share one slip.\"\n",
"print \"The total number of distinct slips we need is\",pow(10,5)-((pow(5,5)-3*pow(5,2))/2)\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"We print all five-digit numbers on slips of paper with one number on each slip.\n",
"We have 100000 distinct five-digit numbers\n",
"Among these numbers 3125 of them can be read either right side up or upside down\n",
"There are 3050 numbers that can be read either right side up or upside down but will read differently.So,hey can be divided into pairs so that every pair of numbers can share one slip.\n",
"The total number of distinct slips we need is 98475\n"
]
}
],
"prompt_number": 6
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 09:Page 72"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"There are\",pow(4,7),\"different schedules for a seven day period with four subjects\"\n",
"print \"To find the number of schedules which devote at least one day to each subject namely mathematics, physics, chemistry,and economics.\"\n",
"print \"A1 denote the set of schedules in which mathematics is never included\"\n",
"print \"A2 denote the set of schedules in which physics is never included\"\n",
"print \"A3 denote the set of schedules in which chemistry is never included\"\n",
"print \"A4 denote the set of schedules in which economics is never included\"\n",
"print \"A1_union_A2_union_A3_union_A4 is the set of schedules in which one or more of the subjects is not included. We obtain |A1 U A2 U A3 U A4|=\",\n",
"A1=A2=A3=A4=pow(3,7)\n",
"A1_intersection_A2=A1_intersection_A3=A1_intersection_A4=A2_intersection_A3=A2_intersection_A4=A3_intersection_A4=pow(2,7)\n",
"A1_intersection_A2_intersection_A3=A1_intersection_A2_intersection_A4=A1_intersection_A3_intersection_A4=A2_intersection_A3_intersection_A4=1\n",
"A1_intersection_A2_intersection_A3_intersection_A4=0\n",
"A1_union_A2_union_A3_union_A4=A1+A2+A3+A4-A1_intersection_A2-A1_intersection_A3-A1_intersection_A4-A2_intersection_A3-A2_intersection_A4-A3_intersection_A4+A1_intersection_A2_intersection_A3+A1_intersection_A2_intersection_A4+A1_intersection_A3_intersection_A4+A2_intersection_A3_intersection_A4\n",
"print A1_union_A2_union_A3_union_A4\n",
"print \"The number of schedules in which all subjects will be included\",pow(4,7)-A1_union_A2_union_A3_union_A4\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"There are 16384 different schedules for a seven day period with four subjects\n",
"To find the number of schedules which devote at least one day to each subject namely mathematics, physics, chemistry,and economics.\n",
"A1 denote the set of schedules in which mathematics is never included\n",
"A2 denote the set of schedules in which physics is never included\n",
"A3 denote the set of schedules in which chemistry is never included\n",
"A4 denote the set of schedules in which economics is never included\n",
"A1_union_A2_union_A3_union_A4 is the set of schedules in which one or more of the subjects is not included. We obtain |A1 U A2 U A3 U A4|= 7984\n",
"The number of schedules in which all subjects will be included 8400\n"
]
}
],
"prompt_number": 7
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 10:Page 73"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"num_office=12 # Total number of offices to be painted\n",
"num_of_green=3 # Number of offices to be painted green\n",
"num_of_pink=2 # Number of offices to be painted pink\n",
"num_of_yellow=2 # Number of offices to be painted yellow\n",
"num_of_white=5 # Number of offices to be painted white\n",
"res=math.factorial(num_office)/(math.factorial(num_of_green)*math.factorial(num_of_pink)*math.factorial(num_of_yellow)*math.factorial(num_of_white))#Mathematical implementation of permutation with similarities\n",
"print \"Total number of ways to paint 12 offices so that 3 of them are green,2 of them are pink,2 of them are yellow and the remaining with white are \", res\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Total number of ways to paint 12 offices so that 3 of them are green,2 of them are pink,2 of them are yellow and the remaining with white are 166320\n"
]
}
],
"prompt_number": 8
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 11:Page 73"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"length=5#Total length of the message\n",
"num_of_dashes=3#Number of dashes in message \n",
"num_of_dots=2#Number of dots in the message\n",
"res=math.factorial(length)/(math.factorial(num_of_dashes)*math.factorial(num_of_dots))\n",
"print \"The number of different messages that can be represented by a sequence of three dashes and two dots :\",res\n",
" \n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"The number of different messages that can be represented by a sequence of three dashes and two dots : 10\n"
]
}
],
"prompt_number": 9
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 12:Page 74"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"days=7 # Number of days in a week\n",
"spaghetti=3 # Number of days a housekeeper wants to serve speghetti in a week\n",
"res=math.factorial(days)/(math.factorial(spaghetti)*math.factorial(days-spaghetti))#Mathematical implementation of permutation swith similarities\n",
"print \"Number of possible ways in which a house keeper can serve spagetti dinner three times each week is\",res\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Number of possible ways in which a house keeper can serve spagetti dinner three times each week is 35\n"
]
}
],
"prompt_number": 10
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 13:Page 74"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"length=32 # Total length of binary sequence\n",
"num_of_one=7 # Total number of places to be filled with one\n",
"def c(n,r):\n",
" res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))\n",
" return res\n",
"print \"Total number of combinations of binary sequences of length 32 in each of which there are exactly seven 1s is \",c(length,num_of_one)\n",
"# Because we can view the problem as placing 7 ones in 32 numbered boxes(and then fill the empty boxes with 0s)\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Total number of combinations of binary sequences of length 32 in each of which there are exactly seven 1s is 3365856\n"
]
}
],
"prompt_number": 12
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 14:Page 74"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"\n",
"import math\n",
"\n",
"total_senators=11 # Total number of senators\n",
"committee_mem=5 # Number of members in the committee\n",
"\n",
"def c(n,r):\n",
" res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))\n",
" return res\n",
"\n",
"#Finding number of combinations for selecting a committee of 5 members from 11 senators\n",
"print \"The number of ways to select a committee of 5 members among 11 senators are\",c(total_senators,committee_mem);\n",
"\n",
"# Finding number of combinations to select a committee of five members so that a particular senator , senator A is always included\n",
"print \"The number of ways to select a committee of five members so that a particular senator , senator A is always included are\", c(total_senators-1,committee_mem-1);\n",
"# Since senator A is always included in the committee, we need to find combinations for the remaining 4 using remaining 10 senators\n",
"\n",
"# Finding number of combinations to select a committee of five members so that a particular senator , senator A is always excluded\n",
"print \"The number of ways to select a committee of five members so that a particular senator , senator A is always excluded are\", c(total_senators-1,committee_mem);\n",
"# Since senator A is alway excluded from the committee, the committee members are selected from the remaining 10 senators\n",
"\n",
"\n",
"print \"To find number of combinations to select a committee of five members so that at least one of senator A and senator B will be included\"\n",
"\n",
"both_A_and_B=c(total_senators-2,committee_mem-2)\n",
"print \"Number of selections including both senator A and senator B \",both_A_and_B\n",
"# Since both senator A and senator B are already included, we need to find combinations for the remaining 3 committee members using remaining 9 senators\n",
"\n",
"#Number of ways to select a committee of five members including senator A and excluding senator B\n",
"A_but_not_B=c(total_senators-2,committee_mem-1)\n",
"print \"Number of selections including senator A and excluding senator B \",A_but_not_B\n",
"# Since senator A is included and senator B is always excluded, find combinations for remaining 4 committee members using remaining 9 senators\n",
"\n",
"#Finding number of combinations to select a committee of five members including senator B and excluding senator A\n",
"B_but_not_A=c(total_senators-2,committee_mem-1)\n",
"print \"Number of selections including senator B and excluding senator A \",B_but_not_A\n",
"# Since senator B is included and senator A is always excluded, find combinations for remaining 4 committee members using remaining 9 senators\n",
"\n",
"res=both_A_and_B+A_but_not_B+B_but_not_A\n",
"print \"Number of ways to select a committee of five members so that at least one of senator A and senator B will be included\",res\n",
"\n",
"print \"Alternative method\"\n",
"\n",
"print \"Number of ways to select a committee of five members so that at least one of senator A and senator B will be included\",c(total_senators,committee_mem)-c(total_senators-2,committee_mem)\n",
"\n",
"\n",
"print \"By applying principle of inclusion and exclusion\"\n",
"#A1 denotes the set of ways of selection that include senator A\n",
"#A2 denotes the set of ways of selection that include senator B\n",
"A1=c(total_senators-1,committee_mem-1)\n",
"A2=c(total_senators-1,committee_mem-1)\n",
"A1_intersection_A2=c(total_senators-2,committee_mem-2)\n",
"print \"|A1 U A2|\",A1+A2-A1_intersection_A2\n",
"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"The number of ways to select a committee of 5 members among 11 senators are 462\n",
"The number of ways to select a committee of five members so that a particular senator , senator A is always included are 210\n",
"The number of ways to select a committee of five members so that a particular senator , senator A is always excluded are 252\n",
"To find number of combinations to select a committee of five members so that at least one of senator A and senator B will be included\n",
"Number of selections including both senator A and senator B 84\n",
"Number of selections including senator A and excluding senator B 126\n",
"Number of selections including senator B and excluding senator A 126\n",
"Number of ways to select a committee of five members so that at least one of senator A and senator B will be included 336\n",
"Alternative method\n",
"Number of ways to select a committee of five members so that at least one of senator A and senator B will be included 336\n",
"By applying principle of inclusion and exclusion\n",
"|A1 U A2| 336\n"
]
}
],
"prompt_number": 13
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 15:Page 75"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"print \"To find the total number of line segments the diagonals are divided into by their intersections\"\n",
"def c(n,r):\n",
" res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))\n",
" return res\n",
"nodes=10#Decagon has 10 vertex points\n",
"pair=2#Denotes pair of edges to form a disgonal\n",
"num_of_diagonals=(c(nodes,pair)-nodes)\n",
"print \"Number of diagonals :\",num_of_diagonals\n",
"#There are c(10,2) straight lines joining c(10,2) pairs of vertices. But since 10 of them are sides of the decagon, we subtract 10\n",
"num_of_intersections=c(nodes,4)\n",
"print \"Total number of intersections\",num_of_intersections\n",
"# Since for every 4 vertices we can count exactly one intersection between the diagonals\n",
"print \"Total number of line segments\",(num_of_diagonals+(2*num_of_intersections))\n",
"#Since a diagonal is divided into k+1 line segments when there are k intersecting points lying on it, and since each intersecting point lies on two diagonals\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"To find the total number of line segments the diagonals are divided into by their intersections\n",
"Number of diagonals : 35\n",
"Total number of intersections 210\n",
"Total number of line segments 455\n"
]
}
],
"prompt_number": 14
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 16:Page 76"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"def c(n,r):\n",
" res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))#Mathematical implementation of combinations\n",
" return res\n",
"days=7#Total days in a week\n",
"choice=3#Number of days to be selected\n",
"print \"The number of ways to choose three out of seven days(with repititions allowed) is c(7+3-1,3)=c(9,3)=\", c(days+choice-1,choice)\n",
"print \"The number of ways to choose seven out of three days(with repititions necessarily allowed) is c(3+7-1,7)=c(9,7)=\", c(choice+days-1,days)\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"The number of ways to choose three out of seven days(with repititions allowed) is c(7+3-1,3)=c(9,3)= 84\n",
"The number of ways to choose seven out of three days(with repititions necessarily allowed) is c(3+7-1,7)=c(9,7)= 36\n"
]
}
],
"prompt_number": 15
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 17:Page 76"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"total=7#Total number of diferent markings in a domino\n",
"squares=2#Number of squares in a domino\n",
"def c(n,r):\n",
" res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))\n",
" return res\n",
"print \"The number of distinct dominoes in a set is C(7+2-1,2)=C(8,2)=\",c(total+squares-1,squares)\n",
"#Equivalent to selecting two subjects from seven objects \"one\",\"two\",\"three\",\"four\",\"five\",\"six\",\"blank\"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"The number of distinct dominoes in a set is C(7+2-1,2)=C(8,2)= 28\n"
]
}
],
"prompt_number": 16
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 18:page 76"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"dice=3#Number of dice being rolled\n",
"num=6#Total number of outcomes in one dice\n",
"def C(n,r):\n",
" return math.factorial(n)/(math.factorial(r)*math.factorial(n-r))#Formula to calculate combinations\n",
"print \"When three dice are rolled, the number of different outcomes are C(6+3-1,3)=C(8,3)=\",C(num+dice-1,dice),\"because rolling three dice is equivalent to selecting three numbers from six numbers 1,2,3,4,5,6, with repetitions allowed\"\n",
"#Since it is equivalent to selecting 3 numbers from 6 numbers namely 1,2,3,4,5,6 with repetitions allowed\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"When three dice are rolled, the number of different outcomes are C(6+3-1,3)=C(8,3)= 56 because rolling three dice is equivalent to selecting three numbers from six numbers 1,2,3,4,5,6, with repetitions allowed\n"
]
}
],
"prompt_number": 17
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 19:Page 77"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"def C(n,r):\n",
" res= math.factorial(n)/(math.factorial(r)*math.factorial(n-r))#Formula to calculate combinations\n",
" return res\n",
"moves=14#total possible moves in both directions\n",
"eastward=7#Possible number of eastward moves in total\n",
"northward=7#Possible number of northward moves in total\n",
"print \"The number of different paths for a rook to move from the southwest corner of a chessboard to the northwest corner by moving eastward and northward only.\"\n",
"print \"0 denote an eastward step and 1 denote a northward step, the number of paths is equal to the number of ways of arranging seven 0s and seven 1s, which is\",math.factorial(14)/(math.factorial(7)*math.factorial(7))\n",
"#Formula of permutations involving indistinguishable objects ie.,7 similar eastward moves and 7 similar northward moves\n",
"#This is the same as that of placing seven indistinguishable balls in four distinct boxes with no box left empty.\n",
"east_move=4#Number of northward moves\n",
"north_move=3#Number of eastward moves\n",
"num=C(east_move+north_move-1,north_move)#Number of ways of making up a path with four eastward moves\n",
"num1=C(north_move+east_move-1,east_move)#Number of ways of making up a path with three northward moves\n",
"print \"Number of ways of making up a path with four eastward moves is \",num#Same as that of placing seven indistinguishable balls in four boxes with no box left empty\n",
"print \"Number of ways of making up a path with three northward moves is \",num1\n",
"print \"Therefore, the answer to our question is \",num,\"*\",num1,\"=\",num*num1\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"The number of different paths for a rook to move from the southwest corner of a chessboard to the northwest corner by moving eastward and northward only.\n",
"0 denote an eastward step and 1 denote a northward step, the number of paths is equal to the number of ways of arranging seven 0s and seven 1s, which is 3432\n",
"Number of ways of making up a path with four eastward moves is 20\n",
"Number of ways of making up a path with three northward moves is 15\n",
"Therefore, the answer to our question is 20 * 15 = 300\n"
]
}
],
"prompt_number": 18
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 20:Page 77"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"chairs=12#Total number of chairs\n",
"boys=5#Number of boys to be seated\n",
"objects=6#Number of differenr objects\n",
"def C(n,r):\n",
" return math.factorial(n)/(math.factorial(r)*math.factorial(n-r))#Mathematical implementation of combinations\n",
"print \"To determine the number of ways to seat five boys in a row of 12 chairs.The number of arrangements would be\",math.factorial(chairs)/math.factorial(chairs-boys)#Because it is similar to arranging 12 objects which are of 6 different types ie.five boys are of different kind each and the remaining unoccupied chairs are of a kind\n",
"print \"Alternative way:\"\n",
"print \"Suppose, we arrange the first five boys in a row and then distribute the seven unoccupied chairs arbitrarily either between any two boys or at the two ends. The distribution problem then becomes that of placing seven balls of the same color in six boxes. Thus, the number of ways to do is 5!*C(6+7-1,7)=5!*(12!/7!*5!)=12!/7!=\",math.factorial(boys)*C(objects+(chairs-boys)-1,(chairs-boys))\n",
"print \"Suppose, we want to seat the boys so that no two boys are next to each other.\"\n",
"print \"5!*C(6+3-1,3)=5!*(8!/3!*5!)=\",math.factorial(5)*C(6+3-1,3)\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"To determine the number of ways to seat five boys in a row of 12 chairs.The number of arrangements would be 95040\n",
"Alternative way:\n",
"Suppose, we arrange the first five boys in a row and then distribute the seven unoccupied chairs arbitrarily either between any two boys or at the two ends. The distribution problem then becomes that of placing seven balls of the same color in six boxes. Thus, the number of ways to do is 5!*C(6+7-1,7)=5!*(12!/7!*5!)=12!/7!= 95040\n",
"Suppose, we want to seat the boys so that no two boys are next to each other.\n",
"5!*C(6+3-1,3)=5!*(8!/3!*5!)= 6720\n"
]
}
],
"prompt_number": 33
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 22:page 83"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from fractions import Fraction\n",
"print \"For the experiment of rolling a dice, the sample space consists of six samples. We suppose the probability of occurence of each of these samples is 1/6.\"\n",
"print \"probability of getting an odd number is\", (Fraction(1,6)+Fraction(1,6)+Fraction(1,6)) # Since out of the six samples, three of them are odd numbers and the probability of getting each of them is 1/6\n",
"print \"On the other hand, suppose that we have a 'crooked' die such that the probability of getting a 1 is 1/3 and the probability of getting each of the remaining numbers is 2/15.\"\n",
"print \"The probability of getting an odd number is\",(Fraction(1,3)+Fraction(2,15)+Fraction(2,15)) # Since out of the six samples, three of them are odd numbers and the probability of getting a 1 is 1/3 and each of the remaining is 2/15\n",
"print \"The probability of getting an even number is\",(Fraction(2,15)+Fraction(2,15)+Fraction(2,15)) # Since out of the six samples, three of them are even numbers and the probability of getting each of them is 2/15\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"For the experiment of rolling a dice, the sample space consists of six samples. We suppose the probability of occurence of each of these samples is 1/6.\n",
"probability of getting an odd number is 1/2\n",
"On the other hand, suppose that we have a 'crooked' die such that the probability of getting a 1 is 1/3 and the probability of getting each of the remaining numbers is 2/15.\n",
"The probability of getting an odd number is 3/5\n",
"The probability of getting an even number is 2/5\n"
]
}
],
"prompt_number": 20
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 23:Page 84"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from fractions import Fraction\n",
"print \"For the experiment of rolling two dice, the sample space consists of 36 samples. Suppose we want to find the probability of getting a sum of 9 in this experiment. We can get the sum 9 in four different ways such as {(3,6),(4,5),(5,4),(6,3)}\"\n",
"print \"probability of getting a sum 9 is\",(Fraction(1,36)+Fraction(1,36)+Fraction(1,36)+Fraction(1,36)) # Since the probability of occurence of each sample is 1/36 and we have four samples which give a sum of 9\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"For the experiment of rolling two dice, the sample space consists of 36 samples. Suppose we want to find the probability of getting a sum of 9 in this experiment. We can get the sum 9 in four different ways such as {(3,6),(4,5),(5,4),(6,3)}\n",
"probability of getting a sum 9 is 1/9\n"
]
}
],
"prompt_number": 21
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 24:Page 84"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from decimal import *\n",
"import math\n",
"def c(n,r):\n",
" res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))#Mathematical implementation of combinations\n",
" return res\n",
"\n",
"cards=52#Total number of cards in a deck\n",
"poker_cards=5#5 cards make up a poker hand\n",
"aces=48.0#Number of outcomes with 4 aces\n",
"print \"Consider the problem of dealing a poker hand out of a deck of 52 cards.\"\n",
"print \"The sample space consists of\",c(cards,poker_cards),\"sample points corresponding to the c(52,5) different hands that can be dealt\"\n",
"print \"Assume that the outcomes have equal probabilities;that is,the probability that a particular hand was dealt is equal to 1/c(52,5)=\",1.0/(c(cards,poker_cards))\n",
"getcontext().prec=3#Decides the number of decimal digits\n",
"print \"To determine the probability of geting four aces, we note that 48 of the c(52,5) possible outcomes contain four aces;thus,the probability is 48/c(52,5)=\",Decimal(aces)/Decimal(c(cards,poker_cards))\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Consider the problem of dealing a poker hand out of a deck of 52 cards.\n",
"The sample space consists of 2598960 sample points corresponding to the c(52,5) different hands that can be dealt\n",
"Assume that the outcomes have equal probabilities;that is,the probability that a particular hand was dealt is equal to 1/c(52,5)= 3.84769292332e-07\n",
"To determine the probability of geting four aces, we note that 48 of the c(52,5) possible outcomes contain four aces;thus,the probability is 48/c(52,5)= 0.0000185\n"
]
}
],
"prompt_number": 22
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 25:Page 84"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"from decimal import *\n",
"def P(n,r):\n",
" res=math.factorial(n)/math.factorial(n-r)#Mathematical implementation of permutations\n",
" return res\n",
"print \"Consider 23 people out of which the chance is less than 50-50 that no two of them will have the same birthday. Sample space consists of 366^23 samples corresponding to all possible distributions of birthdays of 23 people.\"\n",
"print \"Assume: The distributions are equiprobable.\"\n",
"getcontext().prec=3#Decides the number of decimal digits\n",
"print \"Since out of the 366^23 samples, P(366,23) of them correspond to distributions of birthdays such that no two of the 23 people have the same birthday, the probability that no two people have the same birthday is P(366,23)/366^23=\",(Decimal(P(366,23))/Decimal(pow(366,23)))\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Consider 23 people out of which the chance is less than 50-50 that no two of them will have the same birthday. Sample space consists of 366^23 samples corresponding to all possible distributions of birthdays of 23 people.\n",
"Assume: The distributions are equiprobable.\n",
"Since out of the 366^23 samples, P(366,23) of them correspond to distributions of birthdays such that no two of the 23 people have the same birthday, the probability that no two people have the same birthday is P(366,23)/366^23= 0.494\n"
]
}
],
"prompt_number": 23
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 26:Page 84"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from decimal import *\n",
"import math\n",
"students=8#Total number of students\n",
"freshmen=2#Total number of freshmen\n",
"sophomores=2#Total number of sophomores\n",
"juniors=2#Total number of juniors\n",
"seniors=2#Total number of seniors\n",
"sample_space=pow(4,8)#Total number of samples\n",
"print \"Eight students are standing in line for an interview. We want to determine the probability that there are exactly two fishermen, two sophomores, two juniors, and two seniors in the line. The sample space consists of 4^8 samples corresponding to all possibilities of classes the students are from. \"\n",
"print \"Assume: All the samples are equiprobable\"\n",
"getcontext().prec=3#Decides the number of decimal digits\n",
"print \"There are 8!/2!2!2!2! samples corresponding to the case in which there are two students from each class. Thus the probability is \",(Decimal(math.factorial(students))/(Decimal(math.factorial(freshmen)*math.factorial(sophomores)*math.factorial(juniors)*math.factorial(seniors)*sample_space)))\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Eight students are standing in line for an interview. We want to determine the probability that there are exactly two fishermen, two sophomores, two juniors, and two seniors in the line. The sample space consists of 4^8 samples corresponding to all possibilities of classes the students are from. \n",
"Assume: All the samples are equiprobable\n",
"There are 8!/2!2!2!2! samples corresponding to the case in which there are two students from each class. Thus the probability is 0.0385\n"
]
}
],
"prompt_number": 24
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 28:Page 85 "
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"To find the probability of various number of buffers being filled by digital data from a remote site\"\n",
"A=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]# A denotes that initial 16 buffers are full\n",
"B=[1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31]#B denotes that odd buffers are full\n",
"A_inter_B=[1,3,5,7,9,11,13,15]#set representing A intersection B\n",
"P_A=0.0#initial probability corresponding to set A is zero\n",
"P_A_and_B=0.0#initial probability of set A intersection B is zero\n",
"P_B=0.0#initial probability of set B is zero\n",
"for q in A:\n",
" P_A+=(1.0/561.0)*(33.0-q)\n",
"print \"Probability of buffers in set A being filled is\",round(P_A,3)\n",
"for q in B:\n",
" P_B+=(1.0/561.0)*(33.0-q)\n",
"print \"Probability of buffers in set B being filled is\",round(P_B,3)\n",
"for q in A_inter_B:\n",
" P_A_and_B+=(1.0/561.0)*(33.0-q)\n",
"print \"Probability of buffers in set A intersection B being filled is\",round(P_A_and_B,3)\n",
"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"To find the probability of various number of buffers being filled by digital data from a remote site\n",
"Probability of buffers in set A being filled is 0.758\n",
"Probability of buffers in set B being filled is 0.485\n",
"Probability of buffers in set A intersection B being filled is 0.357\n"
]
}
],
"prompt_number": 25
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 29:Page 86"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"Out of 100,000 people, 51,500 are female and 48,500 are male. Among the females 9,000 are bald, and among the males 30,200 are bald. Suppose we are to choose a person at random. We shall have S={fb,fh,mb,mh} as the sample space with fb denoting bald female, fh a femele with hair, mb a bald male, and mh a male with hair.\"\n",
"P_fb=0.090 # Probability of selecting a bald female \n",
"P_fh=0.425 # Probabbility of selecting a female with hair\n",
"P_mb=0.302 # Probability of selecting a bald male\n",
"p_mh=0.183 # Probability of selecting a male with hair\n",
"print \"Given:\"\n",
"print \"P(fb)=0.090\"\n",
"print \"P(fh)=0.425\"\n",
"print \"P(mb)=0.302\"\n",
"print \"P(mh)=0.183\"\n",
"\n",
"print \"Let A denote the event that a bald person was chosen\"\n",
"print \"Let B denote the event that a female was chosen\"\n",
"print \"Then A intersection B is the event that a bald female was chosen, A union B the event that a bald person or a female was chosen,A EXOR B the event that a female with hair or a bald male was chosen and B-A the event that a female with hair was chosen.\"\n",
"P_A=P_fb+P_mb # Includes both male bald and female bald\n",
"P_B=P_fb+P_fh # Includes all females\n",
"P_A_intersection_B=P_fb # iIncludes all females who are bald\n",
"P_A_union_B=P_fb+P_fh+P_mb # Includes all females and bald male\n",
"P_A_EXOR_B=P_fh+P_mb # Includes female with hair and bald male\n",
"P_B_minus_A=P_fh # Includes only female with hair\n",
"print \"P(A)=\",P_A\n",
"print \"P(B)\",P_B\n",
"print \"P(A intersection B)=\",P_A_intersection_B\n",
"print \"P(A union B)=\",P_A_union_B\n",
"print \"P(A EXOR B)=\",P_A_EXOR_B\n",
"print \"P(B-A)=\",P_B_minus_A\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Out of 100,000 people, 51,500 are female and 48,500 are male. Among the females 9,000 are bald, and among the males 30,200 are bald. Suppose we are to choose a person at random. We shall have S={fb,fh,mb,mh} as the sample space with fb denoting bald female, fh a femele with hair, mb a bald male, and mh a male with hair.\n",
"Given:\n",
"P(fb)=0.090\n",
"P(fh)=0.425\n",
"P(mb)=0.302\n",
"P(mh)=0.183\n",
"Let A denote the event that a bald person was chosen\n",
"Let B denote the event that a female was chosen\n",
"Then A intersection B is the event that a bald female was chosen, A union B the event that a bald person or a female was chosen,A EXOR B the event that a female with hair or a bald male was chosen and B-A the event that a female with hair was chosen.\n",
"P(A)= 0.392\n",
"P(B) 0.515\n",
"P(A intersection B)= 0.09\n",
"P(A union B)= 0.817\n",
"P(A EXOR B)= 0.727\n",
"P(B-A)= 0.425\n"
]
}
],
"prompt_number": 26
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 31:Page 88"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"Out of 100,000 people, 51,500 are female and 48,500 are male. Among the females 9,000 are bald, and among the males 30,200 are bald. Suppose we are to choose a person at random.We shall have S={fb,fh,mb,mh} as the sample space with fb denoting bald female, fh a femele with hair, mb a bald male, and mh a male with hair.\"\n",
"print \"Let A denote the event that a bald person was chosen, B the event that a female was chosen, and C the event that a male was chosen.\"\n",
"P_fb=0.090 # Probability of selecting a bald female \n",
"P_fh=0.425 # Probabbility of selecting a female with hair\n",
"P_mb=0.302 # Probability of selecting a bald male\n",
"P_mh=0.183 # Probability of selecting a male with hair\n",
"print \"Given:\"\n",
"print \"P(fb)=0.090\"\n",
"print \"P(fh)=0.425\"\n",
"print \"P(mb)=0.302\"\n",
"print \"P(mh)=0.183\"\n",
"P_A=P_fb+P_mb # Includes both male bald and female bald\n",
"P_B=P_fb+P_fh # Includes all female\n",
"P_C=P_mb+P_mh # Includes all male\n",
"P_A_intersection_C=P_mb # Includes all males who are bald\n",
"P_C_intersection_A=P_mb # Since A intersection C and C intersection A are the same, this also includes all males who are bald\n",
"P_A_intersection_B=P_fb # Includes all females who are bald\n",
"P_B_intersection_A=P_fb # Since A intersection B and B intersection A are the same,this also includes all females who are bald\n",
"\n",
"P_A_given_B=P_A_intersection_B/P_B # By conditional probability\n",
"print \"P(A|B)=\",round(P_A_given_B,3);\n",
"print \"This is less than P(A) which is 0.392\"\n",
"P_A_given_C=P_A_intersection_C/P_C # By conditional probability\n",
"\n",
"print \"P(A|C)=\",round(P_A_given_C,3)\n",
"print \"This is quite a bit greater than P(A)\"\n",
"P_B_given_A=P_B_intersection_A/P_A# By conditional probability\n",
"print \"P(B|A)=\",round(P_B_given_A,2)\n",
"P_C_given_A=P_C_intersection_A/P_A# By conditional probability\n",
"print \"P(C|A)=\",round(P_C_given_A,2)\n",
"print \"Indeed, although P(B) is slightly larger than P(C),P(B|A) is much smaller than P(C|A)\"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Out of 100,000 people, 51,500 are female and 48,500 are male. Among the females 9,000 are bald, and among the males 30,200 are bald. Suppose we are to choose a person at random.We shall have S={fb,fh,mb,mh} as the sample space with fb denoting bald female, fh a femele with hair, mb a bald male, and mh a male with hair.\n",
"Let A denote the event that a bald person was chosen, B the event that a female was chosen, and C the event that a male was chosen.\n",
"Given:\n",
"P(fb)=0.090\n",
"P(fh)=0.425\n",
"P(mb)=0.302\n",
"P(mh)=0.183\n",
"P(A|B)= 0.175\n",
"This is less than P(A) which is 0.392\n",
"P(A|C)= 0.623\n",
"This is quite a bit greater than P(A)\n",
"P(B|A)= 0.23\n",
"P(C|A)= 0.77\n",
"Indeed, although P(B) is slightly larger than P(C),P(B|A) is much smaller than P(C|A)\n"
]
}
],
"prompt_number": 27
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 32:Page 89"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from fractions import Fraction\n",
"from decimal import *\n",
"print \"A coin was chosen at random and tossed.\"\n",
"p_fc_hd=Fraction('1/3') # Probability that a fair coin was chosen and head shows\n",
"p_fc_tl=Fraction('1/3') # Probability that a fair coin was chosen and tail shows\n",
"p_ufc_hd=Fraction('1/12') # Probability that a unfair coin was chosen and head shows\n",
"p_ufc_tl=Fraction('1/4') # Probability that a unfair coin was chosen and head shows\n",
"\n",
"print \"The probability that head shows is\",(Fraction(p_fc_hd)+Fraction(p_ufc_hd)) # Probability of head in both fair and unfair coins\n",
"print \"The probability that an unfair coin was chosen is\",(Fraction(p_ufc_hd)+Fraction(p_ufc_tl)) # Probability of head and tail in unfair coin\n",
"p_head=(Fraction(p_fc_hd)+Fraction(p_ufc_hd))\n",
"print \"The conditional probability that an unfair coin was chosen given that head shows is\",(Fraction(p_ufc_hd)/Fraction(p_head))# By conditional probability, probability of head in unfair coin to the probabilty of head in both fair and unfair coins\n",
"print \"The conditional probability that head shows given that an unfair coin was chosen is\",(Fraction(p_ufc_hd)/(Fraction(p_ufc_hd)+Fraction(p_ufc_tl))) # By conditional probability,probability of head in unfair coin to the probability of head and tail in unfair coin\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"A coin was chosen at random and tossed.\n",
"The probability that head shows is 5/12\n",
"The probability that an unfair coin was chosen is 1/3\n",
"The conditional probability that an unfair coin was chosen given that head shows is 1/5\n",
"The conditional probability that head shows given that an unfair coin was chosen is 1/4\n"
]
}
],
"prompt_number": 28
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 33:Page 89"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"from fractions import Fraction\n",
"def P(n,r):\n",
" res=math.factorial(n)/math.factorial(n-r)\n",
" return res\n",
"faces=6#Number of faces in a dice\n",
"dice=3#Number of dice that were rolled\n",
"print \"Three dice were rolled.\"\n",
"print \"Given: No two faces were the same.\"\n",
"print \"Let A denote the event that there was an ace.\"\n",
"print \"Let B denote the event that no two faces were the same.\"\n",
"P_B=Fraction(P(faces,dice))/Fraction(pow(faces,dice)) # Sample space is pow(6,3) sice three dice are rolled.\n",
"P_A_intersection_B=Fraction(dice*P(faces-1,dice-1))/Fraction(pow(faces,dice))#Since A has occured, it cannot repeat again. So faces and dice are reduced by 1\n",
"P_A_given_B=Fraction(P_A_intersection_B)/Fraction(P_B) #By conditional probability\n",
"print \"P(A|B)=\",P_A_given_B\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Three dice were rolled.\n",
"Given: No two faces were the same.\n",
"Let A denote the event that there was an ace.\n",
"Let B denote the event that no two faces were the same.\n",
"P(A|B)= 1/2\n"
]
}
],
"prompt_number": 29
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 34:Page 90"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from fractions import Fraction\n",
"print \"We define events and probabilities as follows.\"\n",
"print \"E:Introduction of computer education\"\n",
"print \"A1:Mr.X is selected as chairman\"\n",
"print \"A2:Mr.Y is selected as chairman\"\n",
"print \"A3:Mr.Z is selected as chairman\"\n",
"P_A1=Fraction('4/9') # Probability of Mr.X being selected\n",
"P_A2=Fraction('2/9') # Probability of Mr.Y being selected\n",
"P_A3=Fraction('3/9') # Probability of Mr.Z being selected\n",
"P_E_given_A1=Fraction('3/10') # probability that there was computer education in the college when Mr.X is selected as a chairman\n",
"P_E_given_A2=Fraction('5/10') # probability that there was computer education in the college when Mr.Y is selected as a chairman\n",
"P_E_given_A3=Fraction('8/10') # probability that there was computer education in the college when Mr.Z is selected as a chairman\n",
"print \"P(E)=P[(E INTERSECTION A1) UNION (E INTERSECTION A2) UNION (E INTERSECTION A3)]\"\n",
"print \"=P(E INTERSECTION A1) + P(E INTERSECTION A2) + P(E INTERSECTION A3)\"\n",
"print \"=P(A1)P(E|A1)+P(A2)P(E|A2)+P(A3)P(E|A3)\" # Since by conditional probability, P(E|A1)=P(E intersection A1)/P(A1)\n",
"print \"=\",P_A1,\"*\",P_E_given_A1,\"+\",P_A2,\"*\",P_E_given_A2,\"+\",P_A3,\"*\",P_E_given_A3,\"=\",\n",
"P_E=(P_A1*P_E_given_A1)+(P_A2*P_E_given_A2)+(P_A3*P_E_given_A3) # P_E denotes the probability of computer education in the college\n",
"print P_E\n",
"print \"So, the probability that there was computer education in the college is\",P_E\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"We define events and probabilities as follows.\n",
"E:Introduction of computer education\n",
"A1:Mr.X is selected as chairman\n",
"A2:Mr.Y is selected as chairman\n",
"A3:Mr.Z is selected as chairman\n",
"P(E)=P[(E INTERSECTION A1) UNION (E INTERSECTION A2) UNION (E INTERSECTION A3)]\n",
"=P(E INTERSECTION A1) + P(E INTERSECTION A2) + P(E INTERSECTION A3)\n",
"=P(A1)P(E|A1)+P(A2)P(E|A2)+P(A3)P(E|A3)\n",
"= 4/9 * 3/10 + 2/9 * 1/2 + 1/3 * 4/5 = 23/45\n",
"So, the probability that there was computer education in the college is 23/45\n"
]
}
],
"prompt_number": 30
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 35:Page 91"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"A1: Event that the selected item was produced by machine M1\"\n",
"print \"A2: Event that the selected item was produced by machine M2\"\n",
"print \"A3: Event that the selected item was produced by machine M3\"\n",
"print \"E: Event that the selected item is defective\"\n",
"P_A1=0.2 # The probability that an item selected at random from the entire batch was produced by machine M1\n",
"P_A2=0.3 # The probability that an item selected at random from the entire batch was produced by machine M2\n",
"P_A3=0.5 # The probability that an item selected at random from the entire batch was produced by machine M3\n",
"P_E_given_A1=0.01 # Probability that an item produced by machine M1 will be defective\n",
"P_E_given_A2=0.02 # Probability that an item produced by machine M2 will be defective\n",
"P_E_given_A3=0.03 # Probability that an item produced by machine M3 will be defective\n",
"print \"We require to calculate the conditional probability P(A3|E)\"\n",
"print \"Using bayes' theorem\"\n",
"P_A3_given_E=(P_A3*P_E_given_A3)/((P_A1*P_E_given_A1)+(P_A2*P_E_given_A2)+(P_A3*P_E_given_A3))\n",
"print \"The probability that this item was produced by machine M3 is\",round(P_A3_given_E,3)\n",
" \n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"A1: Event that the selected item was produced by machine M1\n",
"A2: Event that the selected item was produced by machine M2\n",
"A3: Event that the selected item was produced by machine M3\n",
"E: Event that the selected item is defective\n",
"We require to calculate the conditional probability P(A3|E)\n",
"Using bayes' theorem\n",
"The probability that this item was produced by machine M3 is 0.652\n"
]
}
],
"prompt_number": 31
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 36:Page 95"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from fractions import Fraction\n",
"import math\n",
"from decimal import *\n",
"print \"Estimating the likelihood that there will be a 1 hour examination when the professor is scheduled to get out of town\"\n",
"print \"Sample space={x1,x2,x3,x4}\"\n",
"P_X1=Fraction('1/2')#X1 denotes professor out of town and exam given\n",
"P_X2=Fraction('1/16')#X2 denotes professor out of town and exam not given\n",
"P_X3=Fraction('3/16')#X3 denotes professor in town and exam given\n",
"P_X4=Fraction('1/4')#X4 denotes professor in town and exam not given\n",
"print \"A denotes the event that exam is given and B denote the event that professor is out of town\"\n",
"P_A=P_X1+P_X3#Probability of A\n",
"P_A_numerator=P_A.numerator#Separating numerator and denominators in all P(A)\n",
"P_A_denominator=P_A.denominator\n",
"P_A_given_B=P_X1/(P_X1+P_X2)#Probability of P(A|B)\n",
"P_A_given_B_numerator=P_A_given_B.numerator#Separating numerators and denominators in P(A|B)\n",
"P_A_given_B_denominator=P_A_given_B.denominator\n",
"print \"Probability that the exam is given is \",P_A\n",
"print \"Probability of exam given that the profession is out of town is \",P_A_given_B\n",
"log_P_A_numerator=round(math.log(P_A_numerator,2),2)#Logrithm of 11\n",
"log_P_A_denominator=math.log(P_A_denominator,2)#Logrithm of 16\n",
"neg_log_P_A=-log_P_A_numerator+log_P_A_denominator#Negative logrithm of P(A).SInce log(a/b)=lob(a)-log(b)\n",
"getcontext().prec=2#Decides the number of digits after decimal point\n",
"print \"The needed information to determine that an examination will be given is \",neg_log_P_A,\"bits\"\n",
"log_P_A_given_B_numerator=math.log(P_A_given_B_numerator,2)#Logrithm of \n",
"log_P_A_given_B_denominator=round(math.log(P_A_given_B_denominator,2),2)#Logrithm of 9\n",
"print \"Information provided by the fact that the professor is out of town on the fact that examination is given is I(A,B)=\",(-log_P_A_numerator+log_P_A_denominator+log_P_A_given_B_numerator-log_P_A_given_B_denominator),\"bits\"\n",
"print \"C denotes the event that the professor is in town\"\n",
"P_A_given_C=P_X3/(P_X3+P_X4)\n",
"print \"Probability that the examination is given when the professor is in town is \",P_A_given_C\n",
"P_A_given_C_numerator=P_A_given_C.numerator#Separating numerators and denominators in P(A|C)\n",
"P_A_given_C_denominator=P_A_given_C.denominator\n",
"log_P_A_given_C_numerator=round(math.log(P_A_given_C_numerator,2),2)\n",
"log_P_A_given_C_denominator=math.log(P_A_given_C_denominator,2)\n",
"print \"I(A,C)=\",round((-log_P_A_numerator+log_P_A_denominator+log_P_A_given_C_numerator-log_P_A_given_C_denominator),2)\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Estimating the likelihood that there will be a 1 hour examination when the professor is scheduled to get out of town\n",
"Sample space={x1,x2,x3,x4}\n",
"A denotes the event that exam is given and B denote the event that professor is out of town\n",
"Probability that the exam is given is 11/16\n",
"Probability of exam given that the profession is out of town is 8/9\n",
"The needed information to determine that an examination will be given is 0.54 bits\n",
"Information provided by the fact that the professor is out of town on the fact that examination is given is I(A,B)= 0.37 bits\n",
"C denotes the event that the professor is in town\n",
"Probability that the examination is given when the professor is in town is 3/7\n",
"I(A,C)= -0.69\n"
]
}
],
"prompt_number": 32
}
],
"metadata": {}
}
]
}PK„I~¢`¹¹/Elements of discrete mathematics/Chapter3.ipynb{
"metadata": {
"name": "",
"signature": "sha256:d6505774a4cce1c5726d5bf482120157569ff894ee6f05281095d53b18882117"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"3 Relations and Functions"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 06:Page 118"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"Given a relation R on a set A={a,b,c,d} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\"\n",
"#Each element in A acts as a node\n",
"nodes=input(\"Enter the number of nodes\")#This is the total number of elements in the given set A\n",
"w0=[[0 for i in range (nodes)]for j in range(nodes)]#Matrix elements are initialised to zero\n",
"#Gets the initial value for the matrix elements\n",
"print \"Enter the elements of W0. (Enter only 0 or 1)\"# The value is 1 if there is a path between i and j in the given graph, else it is 0\n",
"for i in range(0,nodes):\n",
" for j in range(0,nodes):\n",
" print \"Enter value for w\",i,j\n",
" w0[i][j]=input()\n",
"#To print the given matrix\n",
"print \"The given matrix W0=MR(Matrix relation on R) is\"\n",
"for i in range(0,nodes):\n",
" for j in range(0,nodes):\n",
" print w0[i][j],\n",
" print \"\\n\"\n",
"for k in range(0,nodes):#To find the transitive relation matrix using Warshall's algorithm\n",
" for i in range(0,nodes):\n",
" for j in range(0,nodes):\n",
" w0[i][j]=w0[i][j] or (w0[i][k] and w0[k][j])\n",
"#To print the transitive relation matrix\n",
"print \"The required transitive relation matrix is\"\n",
"for i in range(0,nodes):\n",
" for j in range(0,nodes):\n",
" print w0[i][j],\n",
" print \"\\n\"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Given a relation R on a set A={a,b,c,d} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the number of nodes4\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the elements of W0. (Enter only 0 or 1)\n",
"Enter value for w 0 0\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 0 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 0 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 0 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 1 0\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 1 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 1 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 1 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 2 0\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 2 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 2 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 2 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 3 0\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 3 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 3 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 3 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"The given matrix W0=MR(Matrix relation on R) is\n",
"0 1 0 0 \n",
"\n",
"1 0 1 0 \n",
"\n",
"0 0 0 1 \n",
"\n",
"1 0 0 0 \n",
"\n",
"The required transitive relation matrix is\n",
"1 1 1 1 \n",
"\n",
"1 1 1 1 \n",
"\n",
"1 1 1 1 \n",
"\n",
"1 1 1 1 \n",
"\n"
]
}
],
"prompt_number": 2
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 07:Page 119"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"Given a relation R on a set A={a,b,c,d,e} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\"\n",
"print \"Given:R={(b,c),(b,e),(c,e),(d,a),(c,b),(e,c)}\"\n",
"#Each element in A acts as a node\n",
"nodes=input(\"Enter the number of nodes\")#This is the total number of elements in the given set A\n",
"w0=[[0 for i in range (nodes)]for j in range(nodes)]#Matrix elements are initialised to zero\n",
"#Gets the initial value for the matrix elements\n",
"print \"Enter the elements of W0. (Enter only 0 or 1)\"# The value is 1 if there is a path between i and j in the given graph, else it is 0\n",
"for i in range(0,nodes):\n",
" for j in range(0,nodes):\n",
" print \"Enter value for w\",i,j\n",
" w0[i][j]=input()\n",
"#To print the given matrix\n",
"print \"The given matrix W0=MR(Matrix relation on R) is\"\n",
"for i in range(0,nodes):\n",
" for j in range(0,nodes):\n",
" print w0[i][j],\n",
" print \"\\n\"\n",
"for k in range(0,nodes):#To find the transitive relation matrix using Warshall's algorithm\n",
" for i in range(0,nodes):\n",
" for j in range(0,nodes):\n",
" w0[i][j]=w0[i][j] or (w0[i][k] and w0[k][j])\n",
"#To print the transitive relation matrix\n",
"print \"The required transitive relation matrix is\"\n",
"for i in range(0,nodes):\n",
" for j in range(0,nodes):\n",
" print w0[i][j],\n",
" print \"\\n\"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Given a relation R on a set A={a,b,c,d,e} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\n",
"Given:R={(b,c),(b,e),(c,e),(d,a),(c,b),(e,c)}\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the number of nodes5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the elements of W0. (Enter only 0 or 1)\n",
"Enter value for w 0 0\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 0 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 0 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 0 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 0 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 1 0\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 1 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 1 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 1 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 1 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 2 0\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 2 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 2 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 2 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 2 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 3 0\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 3 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 3 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 3 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 3 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 4 0\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 4 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 4 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 4 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter value for w 4 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"The given matrix W0=MR(Matrix relation on R) is\n",
"0 0 0 0 0 \n",
"\n",
"0 0 1 0 1 \n",
"\n",
"0 0 0 0 1 \n",
"\n",
"1 0 0 0 0 \n",
"\n",
"0 1 1 0 0 \n",
"\n",
"The required transitive relation matrix is\n",
"0 0 0 0 0 \n",
"\n",
"0 1 1 0 1 \n",
"\n",
"0 1 1 0 1 \n",
"\n",
"1 0 0 0 0 \n",
"\n",
"0 1 1 0 1 \n",
"\n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 41:Page 154"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"#Given function definition is as follows\n",
"print \"RECURSIVE FUNCTIONS\"\n",
"def f(x):\n",
" if x==0:\n",
" return 1\n",
" else:\n",
" return 3*f(x-1)+1\n",
"print \"f(1)=\",f(1)\n",
"print \"f(2)=\",f(2)\n",
"print \"f(3)=\",f(3)\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"RECURSIVE FUNCTIONS\n",
"f(1)= 4\n",
"f(2)= 13\n",
"f(3)= 40\n"
]
}
],
"prompt_number": 5
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 43:Page 156"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"A recursive function to calculate the GCD of two numbers\"\n",
"def GCD(x,y):\n",
" if x>y:\n",
" x=x-y\n",
" return GCD(x,y)\n",
" elif x1:\n",
" \n",
" mid=len(alist)/2\n",
" left_half=alist[:mid]\n",
" right_half=alist[mid:]#Spltting into halves\n",
" mergesort(left_half)\n",
" mergesort(right_half)#Recirsive split to obtain values\n",
" i=0\n",
" j=0\n",
" k=0#Varaibles for indexing\n",
" while i