Exam questions

Question 1

poset

Answer 1

Poset: A partially ordered set (poset) is a set 𝑋 equipped with a binary relation
⪯ that is reflexive, antisymmetric, and transitive.

Question 2

Hasse diagram

Answer 2

A graphical representation of a finite poset, where elements are represented by vertices, and the order relation is represented by edges, without transitive edges.

Question 3

Immediate predecessor/cover relation

Answer 3

In a poset (𝑋,⪯), x is an immediate predecessor of y if x≺y and there is no z such that
x≺z≺y.

Question 4

Linear order

Answer 4

A poset where every pair of elements is comparable.

Question 5

Lexicographic order

Answer 5

An order defined on the Cartesian product of ordered sets, extending the order of each set to the product.

Question 6

Erdős–Szekeres theorem

Answer 6

For any sequence of n^2+1 distinct real numbers, there is a subsequence of n+1 numbers that is either strictly increasing or strictly decreasing.

Question 7

Smallest/minimum element

Answer 7

An element a in a poset such that a⪯x for all x in the poset.

Question 8

Minimal element

Answer 8

An element
a in a poset such that there is no x ≠a with x⪯a

Question 9

Linear extension

Answer 9

A linear order that contains the original poset order.

Question 10

Show that every finite poset has a linear extension.

Answer 10

Proof: Using the topological sorting algorithm, we can extend any finite poset to a linear order by iteratively removing minimal elements and maintaining the order constraints.

Question 10

Show that every finite poset has a minimal element.

Answer 10

Proof: In a finite poset, consider any chain of elements. Since the set

Question 12

Show that every finite poset has an embedding into (2^𝑋,⊆)

Answer 12

Using the concept of down-sets, we can map each element of the poset to a subset of X, preserving the order.

Question 13

Chains

Answer 13

A subset of a poset where every two elements are comparable.

Question 15

Anti-chains

Answer 15

A subset of a poset where no two elements are comparable.

Question 16

α(P)

Answer 16

The size of the largest anti-chain in the poset.

Question 17

ω(P)

Answer 17

The size of the largest chain in the poset.

Question 18

Prove that 𝛼⋅𝜔≥∣𝑋∣

Answer 18

Using Dilworth’s theorem, which states that in any finite poset, the size of the largest anti-chain is equal to the minimum number of chains needed to cover the poset.

Question 19

Letn=∣X∣ and m=∣Y∣. How many functions are there from X to Y?

Answer 19

Number of functions from m^n.

Question 20

Letn=∣X∣ and m=∣Y∣. How many functions are there from X to Y? proof

Answer 20

Each of the n elements in X has m choices in Y. Therefore, the total number of functions is m^n.

Question 21

Use the last question to show that there are 2^n subsets of X.

Answer 21

Each element can either be included or excluded, giving 2 choices per element. For n elements, this results in 2^n subsets.

Question 23

Show that X has 2^(n-1) subsets of odd size.

Answer 23

Each subset either includes or excludes the new element, so half of the 2^n subsets have an odd size, which is 2^(n-1).

Question 24

Let
n=∣X∣ and m=∣Y∣. How many injective functions are there from X to Y?

Answer 24

There are m(m−1)(m−2)…(m−n+1) injective functions.

Question 25

Let
n=∣X∣ and m=∣Y∣. How many injective functions are there from X to Y? proof

Answer 25

The first element in
X has m choices, the second has m−1 choices, continuing until the last element has m−n+1 choices.

Question 26

Permutation

Answer 26

Permutation: A permutation of a set is a bijection from the set to itself.

Question 27

One-row notation

Answer 27

A permutation can be represented by listing the images of each element in order.

Question 28

Cycle in a permutation

Answer 28

A cycle is a subset of the permutation where elements are cyclically permuted.

Question 29

Show that the number of subsets of size 𝑘 of X equals (n k)

Answer 29

The number of ways to choose k elements from n elements is (𝑛𝑘), which counts the number of k-element subsets of X.

Question 30

Let (𝑖_1,…,𝑖_𝑟)∈𝑁^𝑟 be integers adding to n. How many such tuples of integers are there?

Answer 30

The number of ways to partition n into r parts is
(
n+r−1
r−1
).

Question 31

Let (𝑖_1,…,𝑖_𝑟)∈𝑁^𝑟 be integers adding to n. How many such tuples of integers are there? proof

Answer 31

This can be shown using the stars and bars method.

Question 32

Describe Pascal’s triangle.

Answer 32

A triangular array where each entry is the sum of the two directly above it.

Question 33

State the Binomial Theorem.

Answer 33

(x+y)^n=∑ ( n choose k )x^(n−k)y^k

Question 34

Rearranging “MISSISSIPPI” count number of ways to do it

Answer 34

Using multinomial coefficients, the number of ways is
(11!)/(4!4!2!1!).

​