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.

Given integers:

$n,a_1, a_2, ..., a_n, b_1, b_2, ..., b_n$

How many nonincreasing integer sequences $(x_1, x_2, \dots, x_n)$ of length $n$ are there subject to the bounds:

$a_1 \le x_1 \le b_1$

$a_2 \le x_2 \le b_2$

$\dots$

$a_n \le x_n \le b_n$

?

For example for:

$n = 2$

$a_1 = 4$

$b_1 = 6$

$a_2 = 3$

$b_2 = 5$

There are 8 sequences. They are:

$(4,3), (4,4), (5,3), (5,4), (5,5), (6,3), (6,4), (6,5)$

share|improve this question
    
Are you making any assumptions on the ordering of the $a_i$? and on the ordering of the $b_i$? –  Gerry Myerson Aug 26 '12 at 6:41
    
@GerryMyerson: What do you mean? $a_i$ can be any integer, as can $b_i$. Obviously if for some $i$, $a_i > b_i$ than the answer to the question is zero. Likewise if for some $i$, $b_i < a_{i+1}$ then the answer is also zero. –  Andrew Tomazos Aug 26 '12 at 11:25
    
So, for example, you're not assuming $a_1\le a_2\le\cdots\le a_n$? My guess is that without some restrictions on the $a_i$ and $b_i$ the problem is not going to have any useful answer. Have you looked at any special cases, like $n=2$? –  Gerry Myerson Aug 26 '12 at 12:45
    
@GerryMyerson: I think you may have misread the problem. I have added an example where $a_1 > a_2$. –  Andrew Tomazos Aug 26 '12 at 20:00
add comment

2 Answers 2

Let's take the case $n=2$, rewrite the inequalities as $$a\le x\le b,\qquad c\le y\le d,\qquad x\ge y$$ We're given $a,b,c,d$ and want to count the number of pairs $x,y$. We assume $a\le b$ and $c\le d$, as otherwise the answer is zero. In fact, I'll assume $a,b,c,d$ distinct just to keep my calculations simple.

We have 6 cases:
$c\lt d\lt a\lt b$;
$c\lt a\lt b\lt d$;
$c\lt a\lt b\lt d$;
$a\lt c\lt d\lt b$;
$a\lt c\lt b\lt d$;
$a\lt b\lt c\lt d$.

In the first case, the answer is $$(b-a+1)(d-c+1)$$ In the second case, $$(a-c+1)+(a-c+2)+\cdots+(d-c)+(b-d+1)(d-c+1)$$ Third case case, $$(a-c+1)+(a-c+2)+\cdots+(b-c+1)$$ Fourth case, $$1+2+\cdots+(d-c)+(d-c+1)(b-d+1)$$ Fifth case, $$1+2+\cdots+(b-c+1)$$ Sixth case, zero.

All the $\cdots$ indicate the terms go up by one, so it shouldn't be hard to evaluate them all as sums of arithmetic progressions. My point is, that even in the case $n=2$ you get a slew of different answers, depending on the order relations among the parameters. I really don't think there's going to be a fully general yet useful answer to the question.

share|improve this answer
    
See my answer for what I was looking for. I guess you were thinking general solution or nothing. I just wanted a way to calculate it. –  Andrew Tomazos Aug 27 '12 at 14:00
add comment

Let $T_i(j)$ be the number of valid integer sequence suffixes of the form $(j, x_{i+1}, x_{i+2}, \dots, x_N)$.

($\mathbb{1}$ is the indicator function - it isn't rendering well)

Base case is:

$T_n(k) = \mathbb{1}(a_n \le k \le b_n)$

Recurrence is:

$T_{i-1}(k) = \mathbb{1}(a_{i-1} \le k \le b_{i-1})(\sum_{j=a_i}^{k}(T_i(j)))$

And final answer is $\sum_{j=a_1}^{b_1}(T_1(j))$

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.