Exam 2 Flashcards by j s

How many different three letter initials with none of the leters repeated can people have

26x25x24

How well did you know this?

Not at all

Perfectly

How many bit strings of length n where n is a positive integer start and end with 1s

2^(n-2) + 1

How well did you know this?

Not at all

Perfectly

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 well did you know this?

Not at all

Perfectly

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 well did you know this?

Not at all

Perfectly

How many positive integers between 1000 and 9999 are even

9999/2 - 999/2

all even - even below 1000

How well did you know this?

Not at all

Perfectly

How many positive integers between 1000 and 9999 have distinct digits

9x9x8x7

(1-9)x(0-8)x8x7

How well did you know this?

Not at all

Perfectly

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 well did you know this?

Not at all

Perfectly

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 well did you know this?

Not at all

Perfectly

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 well did you know this?

Not at all

Perfectly

How many positive integers between 1000 and 9999 are divisible by 5 and 7

(9999/35 - 999/35)

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

A palindrome is a string whos reversal is identical to the string, how many bit strings of length n are palindromes

(2^n/2)

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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 well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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 well did you know this?

Not at all

Perfectly

How many bit strings of length 12 contain exactly three 1s

C(12,3)

How well did you know this?

Not at all

Perfectly

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 well did you know this?

Not at all

Perfectly

How many bit strings of length 12 contain at least 3 1s

2^12 - (C(12,1) + C(12,2) + C(12,0))

How well did you know this?

Not at all

Perfectly

How many bit strings of length 12 contain an equal number of 0s and 1s

C(12,6)

How well did you know this?

Not at all

Perfectly

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?

How many permutations of the letters ABCDEFGH contain the string CDE?

How many permutations of the letters ABCDEFGH contain the string BA and FGH?

How many permutations of the letters ABCDEFGH contain the string AB, DE and GH?

How many permutations of the letters ABCDEFGH contain the string CAB and BED?

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 R5 a=b R6 a!=b ``` R1 o R1

54

``` R1 a>b R2 a>=b R3 a<=b R5 a=b R6 a!=b ``` R1 o R2

R1

55

``` R1 a>b R2 a>=b R3 a<=b R5 a=b R6 a!=b ``` R1 o R3

?

56

``` R1 a>b R2 a>=b R3 a<=b R5 a=b R6 a!=b ``` R1 o R4

R^2

57

``` R1 = a divides b R2 = a is a multiple of b ``` R1 u R2

a divides b or b divides a

58

``` R1 = a divides b R2 = a is a multiple of b ``` R1 n R2

a = b or a=-b

59

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.

60

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.

61

Equivalence, if not what properties do they lack? | a and b are the same age

yes

62

Equivalence, if not what properties do they lack? | a and b have the same parents

yes

63

Equivalence, if not what properties do they lack? | a and b share a common parent

no | missing transitive

64

Equivalence, if not what properties do they lack? | a and b have met

no | missing transitive

65

Equivalence, if not what properties do they lack? | a and b speak a common language

no | missing transitive

66

Equivalence, if not what properties do they lack? | f(1)=g(1)

equivalence????

67

Equivalence, if not what properties do they lack? | f(x)-g(x)=1

not reflexive, symmetric or transitive

68

Equivalence, if not what properties do they lack? | f(x)-g(x) = C

equivalence????

69

Equivalence, if not what properties do they lack? | f(0)=g(1) and f(1)=g(0)

not transitive or reflexive

70

f A->B | Domain?

A

71

f A->B | codomain

B

72

f A->B | image

f(a)=b | b is image

73

f A->B | preimage

f(a)=b | a is preimage

74

f maps A to B

f is a function that connects A to B

75

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

76

(f1+f2)(x)

f1(x) + f2(x)

77

(f1f2)(x)

f1(x)*f2(x)

78

one-to-one function

f(a)=f(b) ->a=b

79

onto

for all b E B there is an element a E A f(a)=b

80

surjective

a function that is onto

81

one-to-one correspondence or bijection

if f is one-to-one and onto

82

(f o g)(x)

f(g(x))

83

floor function

assigns to a real number the largest integer that is less to or equal to it

84

roof function

assigns to a real number the largest smallest integer that is greater than or equal to it

85

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

86

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

87

(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

88

variety of ways to choose a dozen donuts from 20 varieties if there are no two donuts of the same variety

C(20,12)

89

variety of ways to choose a dozen donuts from 20 varieties if all donuts are of the same variety

C(20,1)

90

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

91

r-combinations of a set with n elements when repetition is aloud

C(n+r-1,r)

92

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

93

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)

94

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)

95

C(x,y)

x!/((y!)(x-y)!)

96

Def Tree:

A connected, undirected graph with no simple circuits

97

an undirected graph is a tree iff

there is a unique simple path between any two of its vertices

98

Def Rooted Tree:

a tree in which one vertex has been designated as the root and every edge is directed away from the root

99

Def m-ary tree

if every internal vertex has no more than m children

100

def Full m-ary Tree

if every internal vertex has exactly m children

101

internal vertex

a vertex that has children

102

A tree with n vertices has how many edges

n-1

103

A full m-ary tree with i internal vertices contains how many vertices

mi+1 vertices

104

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

105

A full m-ary tree with i internal vertices has how many vertices

mi+1

106

How many ways are there to arrange the letters in THANKSGIVING

12!/((2!)(2!)(2!)) | divided by 2! for doubles of letters

107

How many different ways to spell THANKSGIVING start with T

11!/(2!)(2!)

Exam 2 Flashcards

(107 cards)