Pure Mathematics B cards
0.0 / 5
- Created by: CJ#13
- Created on: 30-10-22 17:56
Define the Stirling numbers
The Stirling numbers (of the second kind), S(n,k), are defined as the numbers of ways to partition a set of size n into k pairwise disjoint, non-empty subsets
1 of 46
Define the Bell numbers
The Bell numbers, B(n), counts the number of partitions of a set of size n
2 of 46
What is a countable set?
A countable set is either a finite set or a set of the same cardinality as N (ℵ0)
3 of 46
Define the Euler ϕ function
If the greatest common divisor (a, b) of two natural
numbers a, b ∈ N+ is 1, then they are called coprime. The Euler function ϕ(n) is defined
as the number of positive integers m ≤ n which are coprime to n.
numbers a, b ∈ N+ is 1, then they are called coprime. The Euler function ϕ(n) is defined
as the number of positive integers m ≤ n which are coprime to n.
4 of 46
Define the equality between sets
Two sets A, and B are called equal if any element
a of A is also an element of B and any element of B is an element of A. We then write
A = B
a of A is also an element of B and any element of B is an element of A. We then write
A = B
5 of 46
Define a subset
A set A is a subset of a set B if every element of A is contained in B. We write A ⊆ B or simply A ⊂ B.
We call A a proper subset of B if there is a subset A of B, but A is not equal to B. We then write A ⊆B
We call A a proper subset of B if there is a subset A of B, but A is not equal to B. We then write A ⊆B
6 of 46
Define the union of two sets
The union A ∪ B of two sets A and B is the set of all elements of A and B. That is, an object x is contained in A ∪ B if it is contained in A or B.
7 of 46
Define the intersection of two sets
The intersection A ∩ B of two sets A and B is the set of all elements that are contained in both A and B.
8 of 46
When are two sets disjoint?
We call two sets A and B disjoint, if A ∩ B = ∅
9 of 46
Define the difference and the complements of sets
The difference of two sets A and B is defined as A\B:= {x ∈ A|x ∉ B}.
If A ⊂ B, we call B\A the (relative) complement of A in B.
If A ⊂ B, we call B\A the (relative) complement of A in B.
10 of 46
Define the Cartesian product
The Cartesian product A × B of two sets A and
B is the set of all ordered pairs (a, b) with a ∈ A and b ∈ B
B is the set of all ordered pairs (a, b) with a ∈ A and b ∈ B
11 of 46
Define the Power set
The set of subsets of a set A is called the power set of A and denoted by P(A)
12 of 46
Define a binary relation
A (binary) relation R between two sets A and B is a subset R ⊂ A × B. That is, a relation is a set of pairs (a, b) with a ∈ A and b ∈ B.
A binary relation on a set A is a subset R ⊂ A × A
A binary relation on a set A is a subset R ⊂ A × A
13 of 46
What are the types of functions and what are their properties?
A function in which each element of B is associated at least once to an element of A, i.e. f (A) = B, is called surjective.
A function in which each element of B is associated at most once to an element of A is called injective. In other words, a function
A function in which each element of B is associated at most once to an element of A is called injective. In other words, a function
14 of 46
Define the inverse of a function
A function f : A->B is invertible, if there is a
function f^(-1) : B->A such that f (a) = b is equivalent to a = f^(−1) (b) for all a ∈ A and
b ∈ B.
function f^(-1) : B->A such that f (a) = b is equivalent to a = f^(−1) (b) for all a ∈ A and
b ∈ B.
15 of 46
What is the composition of two functions, f: A->B, g: B->C & h: C->D?
The composition g ◦ f is the function from A to C that associates to each element a ∈ A the element g(f (a)) ∈ C.
The composition of functions is associative: h ◦ (g ◦ f ) = (h ◦ g) ◦ f .
The composition of functions is associative: h ◦ (g ◦ f ) = (h ◦ g) ◦ f .
16 of 46
What are the types of compositions between two functions of a certain type?
The composition of surjective functions g ◦ f is surjective;
The composition of injective functions g ◦ f is injective;
The composition of bijective functions g ◦ f is bijective;
The composition of a injective function & a surjective function g ◦ f is bij
The composition of injective functions g ◦ f is injective;
The composition of bijective functions g ◦ f is bijective;
The composition of a injective function & a surjective function g ◦ f is bij
17 of 46
Define the Equivalence relation and name the axioms
An equivalence relation on a set A is a binary
relation R ⊂ A × A on A satisfying three axioms. Writing a ∼ b as a shorthand for (a, b) ∈ R, they read as:
(i) a ∼ a (Reflexivity);
(ii) a ∼ b ⇔ b ∼ a (Symmetry);
(iii) a ∼ b ∼ c ⇒ a ∼ c (Transitivity).
relation R ⊂ A × A on A satisfying three axioms. Writing a ∼ b as a shorthand for (a, b) ∈ R, they read as:
(i) a ∼ a (Reflexivity);
(ii) a ∼ b ⇔ b ∼ a (Symmetry);
(iii) a ∼ b ∼ c ⇒ a ∼ c (Transitivity).
18 of 46
What is the cardinality of a finite set?
A set A is called finite if either A is empty or A ≈ Nk for some natural number k, where Nk = {1, . . . , k}.
A has cardinality k if A ≈ Nk, and the empty set has cardinality 0
A has cardinality k if A ≈ Nk, and the empty set has cardinality 0
19 of 46
What is the cardinality of a power set P(A)?
The cardinality |P(A)| of the power set P(A) of a finite set A is 2^(|A|)
Proof: If |A| = n, then an element of A either is an element of the subset or not. That is, we have 2 possibilities for each element and thus obtain 2·2·. . . = 2^(n) distinct subse
Proof: If |A| = n, then an element of A either is an element of the subset or not. That is, we have 2 possibilities for each element and thus obtain 2·2·. . . = 2^(n) distinct subse
20 of 46
Finish the sentence: "Let m, n ∈ N. If there is an injection f: ..."
Let m, n ∈ N. If there is an injection f : {0, . . . m->{0, . . . , n}, then m ≤ n.
21 of 46
State the Uniqueness of cardinality for finite sets corollary
If we have |A| = m and |A| = n for a finite set |A| and m, n ∈ N, then m = n.
Proof: The statements |A| = m and |A| = n imply bijections between A and {0, . . . , m−1}
and between A and {0, . . . , n − 1}, respectively, and inversion and composition yield
Proof: The statements |A| = m and |A| = n imply bijections between A and {0, . . . , m−1}
and between A and {0, . . . , n − 1}, respectively, and inversion and composition yield
22 of 46
Define the cardinality for infinite sets
A set S which is not finite, is called
infinite. That is, S does not have a cardinality in N and there is no bijection between S and any finite cardinal.
Two infinite sets have the same cardinality
infinite. That is, S does not have a cardinality in N and there is no bijection between S and any finite cardinal.
Two infinite sets have the same cardinality
23 of 46
State the theorem that states the identities for cardinalities
(i) |N ∪ {∗}| = |N|;
(ii) {(i, n)| i ∈ {0, 1}, n ∈ N}| = |N|;
(iii) |N × N| = |N|.
(ii) {(i, n)| i ∈ {0, 1}, n ∈ N}| = |N|;
(iii) |N × N| = |N|.
24 of 46
Are rational numbers countable?
Yes, The cardinality of the rational numbers is ℵ0
25 of 46
What is the cardinality of real numbers?
The real numbers have a strictly larger cardinality than the natural numbers, called the cardinality of the continuum. Moreover, R has the same number of elements as the power set of N (2^(ℵ0))
26 of 46
State the continuum hypothesis
The continuum hypothesis states that there is no set that has a cardinality between that of the natural and that of the real numbers. That
is, there is no “infinity” between ℵ0 and cardinality of the continuum .
is, there is no “infinity” between ℵ0 and cardinality of the continuum .
27 of 46
State the Pigeonhole principle
If n objects are distributed into m boxes with
n > m, then at least one box contains more than one object.
Proof: The pigeonhole principle can be rephrased as follows: if n > m, then there is
no injective function from {1, . . . , n} to {1, . . . , m}.
n > m, then at least one box contains more than one object.
Proof: The pigeonhole principle can be rephrased as follows: if n > m, then there is
no injective function from {1, . . . , n} to {1, . . . , m}.
28 of 46
State the rule of sum and the rule of product
The rule of sum states that if there are x possible outcomes for event a and y possible outcomes for event b and either a or b happens, then the total
number of possible outcomes is x + y.
The rule of product states that if there are x possible outcomes f
number of possible outcomes is x + y.
The rule of product states that if there are x possible outcomes f
29 of 46
Proof the following statement: "If a and b have the same remainder when divided by n, i.e. a ≡ b mod n, then the greatest common divisors of a with n and b with n are equal, (a, n) = (b, n). In particular (a, n) = 1 ⇔ (b, n) = 1."
If a ≡ b mod n, then a = pn + r and b = qn + r for some p, q ∈ N+ . Thus, a − b is a multiple of n: a − b = kn for some k ∈ N. Then any common divisor of a and n divides b and inversely any common divisor of b and n divides a
30 of 46
Define a permutation
A permutation of a set of n objects is an ordered arrangement onto n places. That is, the original set is turned into a finite sequence.
Eg: (1, 2, 3) , (2, 1, 3) , (2, 3, 1) , (3, 2, 1) , (3, 1, 2) ,
(1, 3, 2) are all the permutations of {1, 2, 3}.
Eg: (1, 2, 3) , (2, 1, 3) , (2, 3, 1) , (3, 2, 1) , (3, 1, 2) ,
(1, 3, 2) are all the permutations of {1, 2, 3}.
31 of 46
How do you calculate the number of possible permutations of a set of n objects?
n!
32 of 46
State the theorem of the permutations Sn
The permutations Sn (considered as rearrangements of {1, . . . , n}) form a group, the symmetric group of order n!.
33 of 46
What is the difference between combinations and permutations?
For combinations the order in
which the elements are chosen is irrelevant, while for permutations the order matters. Both combinations and permutations can be considered with or without repetitions.
which the elements are chosen is irrelevant, while for permutations the order matters. Both combinations and permutations can be considered with or without repetitions.
34 of 46
Define the Ballot problem
This problem corresponds to counting monotonic paths on an b × a grid which do not cross the diagonal x = y. The outcome N (a, b) is therefore a generalisation of the Catalan numbers C(n).
35 of 46
Define the partitions of a natural number
Let n ∈ N with n ≥ 1. A partition of
a positive integer is a way of writing it as a sum of positive integers. We identify partitions that are related by permutations of parts
a positive integer is a way of writing it as a sum of positive integers. We identify partitions that are related by permutations of parts
36 of 46
Define the partitions of a set
A partition of a set is a way of writing the set as
a union of pairwise disjoint, non-empty subsets. These subsets are called the parts of the
partition. We identify partitions that are related by permutations of parts
a union of pairwise disjoint, non-empty subsets. These subsets are called the parts of the
partition. We identify partitions that are related by permutations of parts
37 of 46
What is a Ferrers diagram?
A Ferrers diagram displays an integer partition as a monotonic decreasing sequence of dots, where each row of dots corresponds to a part of the integer partition. The total number of dots equals the integer being partitioned.
38 of 46
What is the transpose (conjugate) of a Ferrers diagram?
The transpose or conjugate of a Ferrers diagram is one in which rows and columns are interchanged
39 of 46
What does the number of partitions of an integer n into at most r parts is equal to?
It equals the number of partitions of n + r into exactly r parts
Proof: Proof: Consider a partition of n + r into r parts. The corresponding Ferrers diagram has
a first column with r dots. If we remove this column, we end up with a Ferrers diagram
with a
Proof: Proof: Consider a partition of n + r into r parts. The corresponding Ferrers diagram has
a first column with r dots. If we remove this column, we end up with a Ferrers diagram
with a
40 of 46
What does the number of self-conjugate partitions of an integer n is equal to?
It equals to the number of partitions of n whose parts are distinct and odd.
41 of 46
Finish the sentence: "Given an integer n, the difference between the number of partitions of n into an even number of pairwise distinct parts and odd number of pairwise distinct parts is ..."
(−1)^m if n = (1/2)m(3m ± 1) and 0 otherwise
42 of 46
Why does S(n,n-1) = nC2?
A partition of a set A with |A| = n into n − 1 pdn-subsets contains n − 2 subsets with one element and one subset with two elements. It is determined by choosing the latter, which can be done in nC2 ways.
43 of 46
Why does S(n,2) = 2^(n-1)-1 for n≥2?
A partition of a set A with |A| = n into two pdn-subsets is of the form A = B ∪(A\B), where B ⊂ A. The total number of subsets of A is 2^(n) , and there are 2^(n)/2 = 2^(n)−1 distinct pairs (B, A\B). However, one of the pairs is (A, ∅), and therefore S(n,
44 of 46
What do the following equal to?
S(n,0)
S(0,0)
S(n,n)
S(n,1)
S(n,0)
S(0,0)
S(n,n)
S(n,1)
S(n,0) = 0
S(0,0) = 1
S(n,n) = 1
S(n,1) = 1
S(0,0) = 1
S(n,n) = 1
S(n,1) = 1
45 of 46
What is Aitken's array and how do you use it to find Bell numbers?
The Bell numbers can be readily computed using Aiken's Array. Starting from a 1, we obtain a new row by copying the last entry of the last row and then adding the left and the upper left numbers.
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
The Bell numbers, sta
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
The Bell numbers, sta
46 of 46
Other cards in this set
Card 2
Front
Define the Bell numbers
Back
The Bell numbers, B(n), counts the number of partitions of a set of size n
Card 3
Front
What is a countable set?
Back
Card 4
Front
Define the Euler ϕ function
Back
Card 5
Front
Define the equality between sets
Back
Related discussions on The Student Room
- Mathematics BSC refresher content ahead of looking at a masters »
- A Level Maths Exams and Predictions »
- Cognitive Science Bsc »
- A level Maths or Sociology for non fluent English student? »
- retook units »
- Is a degree in 'Mathematics with Finance and Accounting' good? »
- Chances for Economics at Cambridge? »
- Economics or Economics and Politics? »
- Optometry at Bradford/Huddersfield university »
- Converting CIE A-Level grades to 4.0 Scale GPA »
Similar Mathematics resources:
0.0 / 5
1.0 / 5 based on 1 rating
0.0 / 5
1.5 / 5 based on 8 ratings
1.0 / 5 based on 1 rating
3.0 / 5 based on 2 ratings
Comments
No comments have yet been made