Exam 2 Flashcards
How many different three letter initials with none of the leters repeated can people have
26x25x24
How many bit strings of length n where n is a positive integer start and end with 1s
2^(n-2) + 1
How many strings are there of four lowercase letters that have the letter x in them
26^4 -25^4
(all strings possible - all strings without the letter x
How many positive integers between 1000 and 9999 are divisible by 9
9999/9 - 999/9
all divisible by 9 - lower than 1000 divisible by 9
How many positive integers between 1000 and 9999 are even
9999/2 - 999/2
all even - even below 1000
How many positive integers between 1000 and 9999 have distinct digits
9x9x8x7
(1-9)x(0-8)x8x7
How many positive integers between 1000 and 9999 are not divisible by 3
(9999-999) - (9999/3 - 999/3)
all integers - integers divisible by 3
How many positive integers between 1000 and 9999 are divisible by 5 or 7
(9999/5-999/5) + (9999/7+999/7) -(9999/35 - 999/35)
all divisible by 5 + all divisible by 7 - all divisible by both
How many positive integers between 1000 and 9999 are divisible by 5 but not by 7
(9999/5-999/5) -(9999/35 - 999/35)
all divisible by 5 - all divisible by 5 and 7
How many positive integers between 1000 and 9999 are divisible by 5 and 7
(9999/35 - 999/35)
How many subsets of a set with 100 elements have more than one element
2^100 - 101
all possible - 100 1 elements sets and 1 empty set
A palindrome is a string whos reversal is identical to the string, how many bit strings of length n are palindromes
(2^n/2)
In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, where the bride an d groom are among these 10 people if the bride must be in the picture
6(9x8x7x6x5)
1x9x8x7x6x5) + (9x1x8x7x6x5) + (9x8x1x7x6x5) + (9x8x7x1x6x5) + 9x8x7x6x1x5) + (9x8x7x6x5x1
In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, where the bride an d groom are among these 10 people if the bride is not next to the groom
(5x6)(8x7x6x5)
first place 4 that are not bride and groom, then place bride in 1 of 5 places then the groom in 1 of 6 places
In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, where the bride an d groom are among these 10 people if exactly one of the bride and the groom is in the picture
(8x7x6x5x4)x(2x6)
Pick the other 5 people out of 8 then pick bride or groom then put it in one of the 6 possible places
How many bit strings of length 10 contain either 5 consecutive 0s or 5 consecutive 1s
6(2^6)
6 possible locations for the string of 5, then possible choices for 5 other bits and if the string is 1 or 0
Show that among any group of five integers there are two with the same remainder when divided by 4
Since there are only 4 outcomes when divided by 4 {0,1,2,3} and there are 5 numbers, it must be the case via the pigeonhole principle that two have the same remainder
Show that any group of d+1 integers there are two with exactly the same remainder when they are divided by d
The possible remainders when divided by d are {0,1,2,…,d-1} which are d in total. since we check d+1 options it must be the case that two have the same remainder via the pigeonhole principle
Given a set of 5 distinct integer coordinates on the xy plane, show that the midpoint of the line joining at least one pair of these points has an integer coordinate
There are only 4 types of points that can occur {(even, odd),(even,even),(odd,odd),(odd,even)}. As we can see that the mid pint on any two of the same would be integers. Via the pigeonhole principle it must be the case that we have a midpoint that lies on integers
if there are 101 people of different heights standing in line it is possible to find 11 people that are in order of increasing or decreasing
theorem: every sequence of n^2+1 distinct real numbers contains a sub sequence of n+1 that is either strictly increasing or decreasing
How many bit strings of length 12 contain exactly three 1s
C(12,3)
How many bit strings of length 12 contain at most three 1s
C(12,0) + C(12,1) + C(12,2) + C(12,3)
How many bit strings of length 12 contain at least 3 1s
2^12 - (C(12,1) + C(12,2) + C(12,0))
How many bit strings of length 12 contain an equal number of 0s and 1s
C(12,6)
Coin flipped eight times, how many possible outcomes in total
2^8
Coin flipped eight times, how many possible outcomes contain three heads
C(8,3)
Coin flipped eight times, how many possible outcomes contain at least three heads
2^8 - (C(8,0) + C(8,1) + C(8,2))
total - - 0 head -1 head - 2 head
Coin flipped eight times, how many possible outcomes contain the same number of heads and tails
C(8,4)
How many bit strings of length 10 have exactly three 0s
C(10,3)
How many bit strings of length 10 have more 0s than 1s
C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10)
How many bit strings of length 10 have at least seven 1s
C(10,7) + C(10,8) + C(10,9) + C(10,10)
How many bit strings of length 10 have at least three 1s
C(10,3) + C(10,4) + C(10,5) + C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10)
How many permutations of the letters ABCDEFGH contain the string ED?
7!
How many permutations of the letters ABCDEFGH contain the string CDE?
6!
How many permutations of the letters ABCDEFGH contain the string BA and FGH?
5!
How many permutations of the letters ABCDEFGH contain the string AB, DE and GH?
5!
How many permutations of the letters ABCDEFGH contain the string CAB and BED?
4!
How many permutations of the letters ABCDEFGH contain the string BCA and ABF?
none since the b would never line up
How many ways to order 10 women and six men
10! x C(11,6) x 6!
Ways to form a committee of 6 with 15 women and 10 men with more women then men
C(15,6) + C(15,5)C(10,1) + C(15,4)C(10,2)
{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}
reflexive, symmetric, antisymmetric, transitive?
transitive
{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}
reflexive, symmetric, antisymmetric, transitive?
reflexive, transitive, symmetric
{(1,1),(2,2),(3,3),(4,4)
reflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, antisymmetric, transitive
a is taller than b
reflexive, symmetric, antisymmetric, transitive?
transitive, antisymmetric
a and b were born on the same day
reflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, transitive
a has the same first name as b
reflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, transitive
a and b have a common grandparent
reflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric
x + y = 0
reflexive, symmetric, antisymmetric, transitive?
symmetric
x = +-y
reflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, transitive
x=1
reflexive, symmetric, antisymmetric, transitive?
antisymmetric, Transitive
xy >=0
reflexive, symmetric
Show that r=empty set on a nonempty set is symmetric and transitive, but not reflexive
answer?
R1 a>b R2 a>=b R3 a<b><=b R5 a=b R6 a!=b
R1 o R1</b>
R1
R1 a>b R2 a>=b R3 a<b><=b R5 a=b R6 a!=b
R1 o R2</b>
R1
R1 a>b R2 a>=b R3 a<b><=b R5 a=b R6 a!=b
R1 o R3</b>
?
R1 a>b R2 a>=b R3 a<b><=b R5 a=b R6 a!=b
R1 o R4</b>
R^2
R1 = a divides b R2 = a is a multiple of b
R1 u R2
a divides b or b divides a
R1 = a divides b R2 = a is a multiple of b
R1 n R2
a = b or a=-b
if R and S are reflexive prove that R u S is reflexive
R and S are reflexive on A
so for all x in A, (x,x) is in R and S.
if R and S are reflexive prove that R n S is reflexive
R and S are reflexive on A
so for all x in A, (x,x) is in R and S.
Equivalence, if not what properties do they lack?
a and b are the same age
yes
Equivalence, if not what properties do they lack?
a and b have the same parents
yes
Equivalence, if not what properties do they lack?
a and b share a common parent
no
missing transitive
Equivalence, if not what properties do they lack?
a and b have met
no
missing transitive
Equivalence, if not what properties do they lack?
a and b speak a common language
no
missing transitive
Equivalence, if not what properties do they lack?
f(1)=g(1)
equivalence????
Equivalence, if not what properties do they lack?
f(x)-g(x)=1
not reflexive, symmetric or transitive
Equivalence, if not what properties do they lack?
f(x)-g(x) = C
equivalence????
Equivalence, if not what properties do they lack?
f(0)=g(1) and f(1)=g(0)
not transitive or reflexive
f A->B
Domain?
A
f A->B
codomain
B
f A->B
image
f(a)=b
b is image
f A->B
preimage
f(a)=b
a is preimage
f maps A to B
f is a function that connects A to B
when are two functions equal
when they both have the same domain, codomain, and map each element in their domain to the same element in their codomain
(f1+f2)(x)
f1(x) + f2(x)
(f1f2)(x)
f1(x)*f2(x)
one-to-one function
f(a)=f(b) ->a=b
onto
for all b E B there is an element a E A f(a)=b
surjective
a function that is onto
one-to-one correspondence or bijection
if f is one-to-one and onto
(f o g)(x)
f(g(x))
floor function
assigns to a real number the largest integer that is less to or equal to it
roof function
assigns to a real number the largest smallest integer that is greater than or equal to it
Show that C(n,n/2) >= (2^n)/n
C(n,n/2) is the middlemost element in the binomial equation. 2^n is the sum of an entire level of the binomial equation, and when divided by n it is the average of all elements. Since the middlemost element is always larger than the average
Combinatorial proof:
k(n choose k) = n((n-1) choose (k-1))
LHS: choose k elements then choose 1 out of the k
RHS: choose 1 element then choose the k-1 others
(n choose r)(r choose k) = (n choose k)((n-k) choose (r-k))
LHS:choose set r then from r choose subset k
RHS:Choose subset then choose the remaining for larger set
variety of ways to choose a dozen donuts from 20 varieties if there are no two donuts of the same variety
C(20,12)
variety of ways to choose a dozen donuts from 20 varieties if all donuts are of the same variety
C(20,1)
variety of ways to choose a dozen donuts from 20 varieties if there are no restrictions
c(12+20-1,12)
choices plus varieties -1 choose choices
r-combinations of a set with n elements when repetition is aloud
C(n+r-1,r)
variety of ways to choose a dozen donuts from 20 varieties if there are at least two varieties among the dozen donuts chosen
C(12+20-1,r) -20
all permutations minus 20 where they are all the same type
variety of ways to choose a dozen donuts from 20 varieties if theree must be at least six blueberry filled donuts
C(6+20-1,6)
variety of ways to choose a dozen donuts from 20 varieties if theree can be no more than six blueberry filled donuts
C(12+20-1,12) - C(5+20-1,5)
C(x,y)
x!/((y!)(x-y)!)
Def Tree:
A connected, undirected graph with no simple circuits
an undirected graph is a tree iff
there is a unique simple path between any two of its vertices
Def Rooted Tree:
a tree in which one vertex has been designated as the root and every edge is directed away from the root
Def m-ary tree
if every internal vertex has no more than m children
def Full m-ary Tree
if every internal vertex has exactly m children
internal vertex
a vertex that has children
A tree with n vertices has how many edges
n-1
A full m-ary tree with i internal vertices contains how many vertices
mi+1 vertices
A full m-ary tree with n vertices has how many internal vertices, how many leaves
(n -1)/m internal vertices and n-internal vertices leaves
A full m-ary tree with i internal vertices has how many vertices
mi+1
How many ways are there to arrange the letters in THANKSGIVING
12!/((2!)(2!)(2!))
divided by 2! for doubles of letters
How many different ways to spell THANKSGIVING start with T
11!/(2!)(2!)
