Number of Unimodular Sequnces A sequence $c_1 , c_2, ... , c_k$, over {1,...,n} is called unimodular if it holds that there is an $1 \leq i \leq k $ such that $c_1 \leq c_2 \leq ... \leq c_i \geq c_{i+1} \geq... \geq c_k$.
Does anybody know a closed form for counting Unimodular Sequnces of length k over an alphabet of size n?
I dont think it is easy, maybe by using some generating functions.
But also asymptotic bounds would be interesting.
 A: I now outline how I would solve it. There likely exists shorter solutions:
1) 
First we define a function $f(m,l)$ that counts decreasing sequences of length $l$, with upper bound $m$. We see that $f(m,l) = C(m,l)$ since it corresponds to picking an $l$-element subset from a $m$-element set.
2) 
We see, that there are $l+1$ ways to form tuples $(a,b)$ s.t. $a+b = l$.
These are $(0,l), (1,l-1), \ldots, (l-1,1), (l,0)$.
Using this, we count
$g(l) = \sum_{j=0}^l \sum_{i=1}^n f(i-1, j) \cdot f(i-1,l-j)$
to get the number of sequences of total length $l+1$ (the maximum value, $i$, is spliced into the middle the sequences).
3)
Now sequences should be "padded" with repetitive elements. This is essentially the problem of $k$ indistinguishable balls in $l$ distinguishable boxes.
This is summed for all $l$.
$\sum_{l=1}^k  C(l + k - 1, k) \cdot g(l-1)$
gives the number of unimodular sequences.
Closed formula might exist, and Maple/Mathematica might even serve it directly to you :-).
A: Consider the sequence $1,2,\dotsc,m,\dotsc,2,1$. Distribute $k-1$ markers anywhere before any of the numbers (but not after the final $1$), and place a $k$-th marker before the $m$; then the numbers behind the markers form a unimodular sequence with highest value $m$, and these sequences are in one-to-one correspondence with the ways of placing these markers. There are
$$\binom{2m-2+k-1}{k-1}=\binom{2m+k-3}{k-1}$$
such ways, and summing over all possible values of $m$ yields
$$
\sum_{m=1}^n\binom{2m+k-3}{k-1}
$$
for the total number of unimodular sequences. Wolfram|Alpha has a sort of closed form for this, but it doesn't look very nice.
