This is no answer but a description of an efficient way for computing the cardinality of $S(n)$. I have to post it as an answer since it is too long for a comment.
Consider the subset subsets $U_a(n),C_a(n),L_a(n)$ of $S(n)$ defined as follows: all coefficients of $U_a(n),C_a(n),L_a(n)$ are $\leq a$ and satisfy the additional inequalities $t_i\leq i$ for $U,C$, respectively $t_{n-i}\leq i+1$ for $C,L$.
The set $S(n)$ is then in bijection with the union of the trivial element $(0,0,\dots,0)$ with $\cup_{\mu=1}^n\cup_{k=1}^{n+1} \cup_{\mu=1}^n\cup_{k=1}^n L_\mu(k-1)\times U_{\mu-1}(n-k)$. Indeed, a non-trivial element $(t_1,\dots,t_k)$ (t_1,\dots,t_n)\in S(n)$ with last index $k$ on which its coefficient takes the maximal value $\mu=\max_i t_i$ gives rise to an element $(t_1,\dots,t_{k-1})$ of $L_\mu(k-1)$ (its first $k-1$ coordinates) and to an element of $U_{\mu-1}(n-k)$ (its last (t_{k+1},t_{k+2},\dots,t_n)$ of $n-k$ coordinates). The missing U_{\mu-1}(n-k)$. These elements, together with the omitted $k-$th coordinate of $(t_1,\dots,t_n)$ equals of course t_k=\mu$, determine the initial vector $\mu$ by definition(t_1,\dots,t_n)$ uniquely.
One gets similar recursive decompositions of $U,C,L$ (standing for upper, central, lower) giving rise to recurrence relations among the cardinalities of $U,C,L$ which allow to compute their cardinalities in quadratic time.
By the way, here an idea which can perhaps be exploited: Elements of $S(n)$ with no coordinate equal to $0$ are in bijection with a subset (which can explicitely be described) of $\cup_{k=\lfloor n/2\rfloor}^{n-1}S(k)$ as follows: replace every coefficient $t_i$ of such an element $(t_1,\dots,t_n)$ by $t_i-1$ except if $t_i=1$ and $t_{i-1}>1$ in which case you remove it.
