Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Who's them? ${}$ The title seems to indicate that you want to count something, but the body of the question doesn't mention any count. –  joriki Oct 4 '12 at 22:11
    
oh, sorry I'll fix it –  andy Oct 4 '12 at 22:15
add comment

2 Answers

up vote 0 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.