give just the answers

Question 1

By [𝑛][n]we denote the set {1,…,𝑛}{1,…,n}. A function 𝑓:[𝑚]→[𝑛]f:[m]→[n] is called monotone if 𝑓(𝑖)≤𝑓(𝑗)f(i)≤f(j)whenever 𝑖<𝑗i<j. Let 𝑆(𝑚,𝑛)S(m,n) be the number of monotone injective functions from [𝑚][m] to [𝑛][n]. What is the number of monotone injective functions from [100][100] to [80][80]?

1 point

Question 2

Let 𝑇(𝑚,𝑛)T(m,n) be the number of monotone functions 𝑓f from [𝑚][m] to [𝑛][n]. That is, functions 𝑓:[𝑚]→[𝑛]f:[m]→[n] such that 1≤𝑖≤𝑗≤𝑚1≤i≤j≤m implies 𝑓(𝑖)≤𝑓(𝑗)f(i)≤f(j). What is 𝑇(10,3)T(10,3)?

1 point

Question 3

Let 𝜏(𝑚,𝑛)=[𝑇(𝑚,𝑛)𝑇(𝑛,𝑚)]τ(m,n)=[T(n,m)T(m,n)​], where [𝑥][x] means 𝑥x rounded down. What is 𝜏(10⋅109,5⋅109)τ(10⋅109,5⋅109)?

1 point

Question 4

We call a function 𝑓:𝐴→𝐵f:A→B almost injective if for every 𝑏∈𝐵b∈B the number of elements 𝑎a with 𝑓(𝑎)=𝑏f(a)=b is at most two. Let 𝑀(𝑛)M(n) be the number of almost injective monotone functions from [𝑛][n] to [𝑛][n]. What is 𝑀(5)M(5)?

1 point

Question 5

A function {0,…,𝑛}→𝑍{0,…,n}→Z is a walk function if consecutive values differ by exactly 11, i.e., ∣𝑓(𝑖)−𝑓(𝑖−1)∣=1∣f(i)−f(i−1)∣=1 for all 1=1,…,𝑛1=1,…,n. How many walk functions are there from {0,…,6}{0,…,6} to 𝑍Z with 𝑓(0)=𝑓(6)=0f(0)=f(6)=0?

1 point

Question 6

A function {0,…,𝑛}→𝑍{0,…,n}→Z is a Lipschitz function if consecutive values differ by at most 11, i.e., ∣𝑓(𝑖)−𝑓(𝑖−1)∣≤1∣f(i)−f(i−1)∣≤1 for all 𝑖=1,…,𝑛i=1,…,n. Let 𝐿(𝑛)L(n) be the number Lipschitz functions 𝑓:{0,…,𝑛}→𝑍f:{0,…,n}→Z with 𝑓(0)=𝑓(𝑛)=0f(0)=f(n)=0. What is 𝐿(5)L(5)?

1 point