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. 1 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$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} L_\mu(k-1)\times U_{\mu-1}(n-k)$. Indeed, a non-trivial element$(t_1,\dots,t_k)$with last index$k$on which its coefficient takes the maximal value$\mu=\max_i t_i$gives rise to an element of$L_\mu(k-1)$(its first$k-1$coordinates) and to an element of$U_{\mu-1}(n-k)$(its last$n-k$coordinates). The missing$k-$th coordinate of$(t_1,\dots,t_n)$equals of course$\mu$by definition. 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.