# Combinations of nonincreasing sequences within bounds?

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)$

-
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

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.

-
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

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))$

-