3
$\begingroup$

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.

  • 0
    oh, sorry I'll fix it2012-10-04

2 Answers 2

0

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.

0

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 :-).