## 5.237. longest_increasing_sequence

Origin

constraint on sequences

Constraint

$\mathrm{𝚕𝚘𝚗𝚐𝚎𝚜𝚝}_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}\left(𝙻,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Synonym

$\mathrm{𝚜𝚒𝚣𝚎}_\mathrm{𝚕𝚘𝚗𝚐𝚎𝚜𝚝}_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}$.

Arguments
 $𝙻$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $𝙻\ge 0$ $𝙻<$$\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

$𝙻$ is the largest difference between the first and the last value of the maximum increasing sequences of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

A sequence of consecutive variables ${X}_{i},{X}_{i+1},\cdots ,{X}_{j}$ ($1\le i\le j\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$) of the collection of variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ is a maximum increasing sequence if all the following conditions simultaneously apply:

• ${X}_{i}\le {X}_{i+1}\le \cdots \le {X}_{j}$,

• $i=1$ or ${X}_{i-1}>{X}_{i}$,

• $i=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ or ${X}_{j}>{X}_{j+1}$.

Example
 $\left(7,〈10,8,8,6,4,9,11,8〉\right)$ $\left(0,〈10,8,7,5,4,3,1,0〉\right)$

Figure 5.237.1 gives a graphical representation of the first example of the Example slot with its two maximum increasing sequences in red of respective size 0 and 7. The corresponding $\mathrm{𝚕𝚘𝚗𝚐𝚎𝚜𝚝}_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}$ constraint holds since its first argument $𝙻$ is fixed to the maximum size 7.

##### Figure 5.237.1. Illustration of the first example of the Example slot: a sequence of eight variables ${V}_{1}$, ${V}_{2}$, ${V}_{3}$, ${V}_{4}$, ${V}_{5}$, ${V}_{6}$, ${V}_{7}$, ${V}_{8}$ respectively fixed to values 10, 8, 8, 6, 4, 9, 11, 8 and its two maximum increasing sequences in red of respective size $8-8=0$ and $11-4=7$. Typical
 $𝙻>0$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$ $\mathrm{𝚗𝚟𝚊𝚕}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>2$
Symmetry

One and the same constant can be added to the $\mathrm{𝚟𝚊𝚛}$ attribute of all items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Arg. properties

Functional dependency: $𝙻$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 9 64 625 7776 117649 2097152 43046721

Number of solutions for $\mathrm{𝚕𝚘𝚗𝚐𝚎𝚜𝚝}_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}$: domains $0..n$  Length ($n$)2345678
Total9646257776117649209715243046721
 Parameter value

062070252924343212870
1218122750441225382144314
211616113981136189132685090
3-101621942208162111062074365
4--1102024289303750844603682
5---1410301345067667792840
6----2107252264810197174
7-----36360210379696
8------7156690

Solution count for $\mathrm{𝚕𝚘𝚗𝚐𝚎𝚜𝚝}_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}$: domains $0..n$  Figure 5.237.2 depicts the automaton associated with the $\mathrm{𝚕𝚘𝚗𝚐𝚎𝚜𝚝}_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}$ constraint.
##### Figure 5.237.2. Automaton of the $\mathrm{𝚕𝚘𝚗𝚐𝚎𝚜𝚝}_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}$ constraint and its glue matrix (note that the reverse of the $\mathrm{𝚕𝚘𝚗𝚐𝚎𝚜𝚝}_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}$ constraint is the $\mathrm{𝚕𝚘𝚗𝚐𝚎𝚜𝚝}_\mathrm{𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}$ constraint) ##### Figure 5.237.3. Hypergraph of the reformulation corresponding to the automaton of the $\mathrm{𝚕𝚘𝚗𝚐𝚎𝚜𝚝}_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}$ constraint 