how many monotonically increasing functions with respect to subset relation are there? Let $f:[n]\to \mathcal{P}([k])$ be a weakly monotonic increasing function with respect to the subset relation if $\forall i,j\in [n]$ if $i\le j$ then $f(i)\subseteq f(j)$, and strongly monotonic increasing with respect to the subset relation if $\forall i,j\in [n]$ if $i\le j$ then $f(i)\subsetneq f(j)$.
How many functions are there that are weakly \ strongly monotonic increasing?
My attempt: for the weak case, I think it's like solving the equation $x_1 + x_2 +... + x_n =k$ because we can think of $n$ cells in which we need to put up to $k$ distinct items. for example, if the first cell has the set $\{1,2,3\}$ in the next cell we can put up to $k-3$ additional items (maybe we need to have n+1 cells, because we don't have to pick all of the items). So perhaps the answer is $S(n,k)$. Then for the strong case we might need to subtract the amount of functions to avoid repetitions, so maybe $S(n,k-n)$. I'm really not certain that's the right way to approach the problem though.
 A: Let us consider the weakly monotonic case first. We have $S(n,n)=1$ (cf. Wikipedia), but the number of functions is $2^{n}$ for $k=n$ since we can choose any set.
Now, for the first set $f(1)$ we can choose any size $m_1$, and then select the elements. For the next set, we can choose any size $M_2$ at least $m_1$ and the remaining $m_2=M_2-m_1$ elements. Iterating this idea yields $\sum_{m_1}\binom{k}{m_1}\sum_{m_2}\binom{k-m_1}{m_2}\cdots\sum_{m_n}\binom{k-\sum_{i=1}^{k-1}m_i}{m_k}=\sum_{m_1,\dots,m_k}\binom{k}{m_1,\dots,m_n,k-\sum_{i=1}^nm_i}=(n+1)^k$, using the multinomial theorem. To obtain the right hand side directly, we consider the bijection $x\mapsto f_x$ where for given $x\in[n+1]^k$ we set $f_x(i)=\{j\in[k]:x_j\le i\}$ for $i\in[n]$.
For the strictly increasing functions we try induction over $n$. Let $N_n=(n+1)^k$ be the number of non-decreasing functions and $S_n$ the number of strictly increasing functions. For $n=1$ we have $S_1=2^k=N_1$. For $n=2$ we have $N_2=S_1+S_2$ since we can either choose $f(2)=f(1)$ or a strictly increasing function. This gives $S_2=3^k-2^k$. For $n=3$ we can choose $f(3)=f(2)=f(1)$ or $f(3)=f(2)\neq f(1)$ or $f(3)\neq f(2)=f(1)$ or all distinct, thus $N_3=S_1+2S_2+S_3$. The $2$ is obtained by taking $2$ distinct values, or categories, and deciding where to place the $3-2=1$ "redundant" value. This is the stars and bars pattern with one bar and one star, i.e. $\binom{3-2+2-1}{2-1}=2$.
Hence, we have $S_3=4^k-2(3^k-2^k)-2^k=4^k-2\cdot 3^k+2^k$.
So, the general formula is $N_n=\sum_{i=1}^n\binom{n-i+i-1}{i-1}S_i$, which gives the recursive formula $S_n=N_n-\sum_{i=1}^{n-1}\binom{n-1}{i-1}S_i=(n+1)^k-\sum_{i=1}^{n-1}\binom{n-1}{i-1}S_i$.
I checked quite a bit, I plotted $S_n$ for $k\le 5$ and the results make sense, in particular for $n>k+1$ we have $S_n=0$. Unfortunately, I did not find a closed form.
