Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

2nd year maths > combinatorics cards > Flashcards

combinatorics cards Flashcards

1
Q

pigeonhole principle

A

let n∈ℕ. If at least n+1 pigeons are placed in n pigeonholes, then some pigeonhole contains at least two pigeons

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

pigeonhole principle general

A

let n,k∈ℕ. If at least n pigeons are placed in k pigeonholes, the some pigeonhole contains atleast ⌈n/k⌉ pigeons

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

ceiling of x, ⌈ x ⌉

A

the smallest integer greater than or equal to x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

floor of x, ⌊ x ⌋

A

the greatest integer less than or equal to x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

⌈ x ⌉ =

A

⌊ - x ⌋

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

other ways the define the set {1,2,3,4}

A

EXAMPLES
{x∈ℕ: x<5}
{x-1| x∈{2,3,4,5}}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Union

A

AUB is the set consisting of anything in A OR anything in B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Intersection

A

A∩B is the set consisting of anything in A AND anything in B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Difference

A

A\B is the set consisting of anything in A but not in B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Complement

A

In context of the universal set the complement of A is defined by Aᶜ = U/A

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

consequences of the axiom of extension

A
  • it doesnt matter the order of elements
  • elements cannot appear in a set more than once
  • There is exactly one set with no elements called the empty set {}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

property of ∈

A

not transitive i.e. if a∈b and b∈c that doesn’t mean a∈c

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

subset

A

A is a subset of B if the set A is contained in B. A⊆B.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

image of a under f

A

f(a)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

image

A

the set of elements in the codomain which are mapped to

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

functions a and b are equal if

A
  1. equal domains
  2. equal codomains
  3. same rule
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

injective

A

different elements of the domain map to different elements in the codomain

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

surjective

A

every element of the codomain is mapped to

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

bijective

A

both injective and surjective

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

if f is a bijection then there is precisely…

A

one element of the domain s.t. f(a)=b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

bijective functions are…

A

invertible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

the inverse of a bijection is…

A

a bijection

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

A set X has size n if there exists…

A

a bijection f:{1,2…n}->X

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

distributivity of ∩ and ∪

A

A∩(B∪C) = (A∩B)∪(A∩C)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

∩ ∪ are

A

associative and commutative

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

ordered r-tuple

A

a sequence of r objects which we refer to as elements or co-ordinates in a given order (a,b,c,…)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

in tuples..

A

order matters and elements can be repeated

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

cartesian product

A

cartesian product of A and B is given by AxB {(a,b): a∈A and b∈B}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

powers of sets

A

Aⁿ = AxAx…xA

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Power set

A

a set whose elements are the subsets of A

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

choosing a possibility of one type or another

A

m+n posiibilities (assuming no overlap)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

choosing a possiblity of each type

A

mn posibilities

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Uniformly random choice

A

a choice where all outcomes are equally as likely

34
Q

probability of an event where there are a finite number of possible outcomes each with a uniformly random chance of being picked

A

P(E) = number of outcomes for which E occurs/ total number of outcomes

35
Q

binomial coefficiant of n choose n

A

1

36
Q

binomial coefficiant of n choose n-1

A

n

37
Q

binomial coefficiant of n choose n-2

A

n(n-2)/2

38
Q

ways to choose r elements from a set of size n where order matters and repition is allowed

A

nʳ

39
Q

ways to choose r elements from a set of size n where order matters and repition is not allowed

A

n!/(n-r)!

40
Q

ways to choose r elements from a set of size n where order doesnt matter and repition is allowed

A

n+r-1 choose r

41
Q

ways to choose r elements from a set of size n where order doesn’t matter and repition is not allowed

A

n choose r

42
Q

permutation

A

A permutation of set S of size n is an ordered n-tuple in which each element of S appears once

43
Q

0! =

A

1

44
Q

If there is an overlap of sets then

A

use inclusion exclusion

45
Q

probability of an element being chosen from a total of n elements where order matters and repetition is not allowed

A

(n-r)!/n!

46
Q

probability of an element being chosen from a total of n elements where order matters and repetition is allowed

A

1/nʳ

47
Q

probability of an element being chosen from a total of n elements where order doesn’t matter and repetition is allowed

A

no probability

48
Q

probability of an element being chosen from a total of n elements where order doesnt matter and repetition is not allowed

A

r!(n-r)!/n!

49
Q

workout the probability of certain values being chosen

A
  1. workout the outcomes that fit the condition given
  2. workout the total number of possible outcomes
  3. divide the value from 1. by the value from 2.
50
Q

how many permutations are there of S? where |S|=n

A

n!

51
Q

finding the probability for an unordered set where repetition is allowed

A
  1. work out the possible set outcomes
  2. pick out the ordered sets which match the condition. workout all the permutations of these sets
  3. divide the no. permutations of all the possible sets by the the set of possible outcomes.
52
Q

binomial theorem

A

allows you to express a power of a sum as a sum of individual terms

53
Q

if |X|≤|Y| and |Y|≤|Z| then

A

|X|≤|Z|

54
Q

if |X|≤|Y| and |Y|≤|X| then

A

|X|=|Y|

55
Q

for to sets we must either have

A

|X|≤|Y| or |Y|≤|X|

56
Q

A proper subset may have the same…

A

cardinality as the original set

57
Q

The smallest cardinality of an infinite set is…

A

|ℕ|

58
Q

countable infite

A

if there exists a bijection f:ℕ->X

59
Q

A set is countable if

A

it is finite or countably infinite

60
Q

A set in uncountable if

A

its not finite or countably infinite

61
Q

small infinite set

A

countably infinite stes

62
Q

large infinite sets

A

uncountable sets

63
Q

Continuum hypothesis

A

Does there exist a set whose cardinality is larger than |ℕ| and smaller than |ℝ|

64
Q

Russels paradox

A

There is a contradiction by defining sets {n:n is an element in a set} and says sets must be defined like {x∈X: x satisfies this property}

65
Q

graph

A

a structure consisting of vertices and edges where each edge links two distinct vertices and any two distinct vertices are linked by at most one edge

66
Q

two graphs are equal if

A

they have the same set of edges and vertices

67
Q

Two graphs G and H are isomorphic if

A

we can transform G to H by relabelling vertices.

The are the same graph

68
Q

how to calculate how many labelled graphs there are with a given vertex set

A
  1. work out the edge set, E, and size of edge set |E|

2. the are 2|ᴱ| graphs with vertex set V

69
Q

how to calculate how many graphs there are with n vertices up to isomorphism

A
  1. work out how many graphs there are with 0,1,…|E| edges

2. sum these to get a total number of graphs

70
Q

Complement of a graph

A

the inverse of the graph

71
Q

regular graphs

A

all the vertices have equal order

72
Q

complete graph

A

has an edge between every pair of vertices

73
Q

total number of edges in a complete graph

A

n choose 2

74
Q

copy

A

An instance of another graph at a specific point

75
Q

Walk

A

any order of adjacent vertices where vertices and edges can be repeated as many times as you like.

76
Q

connected

A

a graph is connected if there is a walk through all the vertices or alternatively if there is a path from u to v in G

77
Q

connected components

A

the subgraphs that are connected (If the graph is connected there is one connected component: the graph)

78
Q

acyclic

A

doesn’t contain a cycle

79
Q

what does deleting an edge in a cycle do to graph connectedness

A

nothing

80
Q

What three properties imply each other for trees

A
  1. T is connected
  2. T is acyclic
  3. T has n-1 edges where n is the order of the tree
81
Q

size of a closed walk in a bipartite graph

A

2n (even)

2nd year maths (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions