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
    Are you making any assumptions on the ordering of the $a_i$? and on the ordering of the $b_i$?2012-08-26
  • 0
    @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.2012-08-26
  • 0
    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$?2012-08-26
  • 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