0
$\begingroup$

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

  • 0
    @GerryMyerson: I think you may have misread the problem. I have added an example where a_1 > a_2.2012-08-26

2 Answers 2

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.

  • 0
    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.2012-08-27
0

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