## 5.246. max_occ_of_sorted_tuples_of_values

Origin

Design.

Constraint

$\mathrm{𝚖𝚊𝚡}_\mathrm{𝚘𝚌𝚌}_\mathrm{𝚘𝚏}_\mathrm{𝚜𝚘𝚛𝚝𝚎𝚍}_\mathrm{𝚝𝚞𝚙𝚕𝚎𝚜}_\mathrm{𝚘𝚏}_\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}\left(\mathrm{𝙼𝙰𝚇},𝙺,\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}\right)$

Type
 $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Arguments
 $\mathrm{𝙼𝙰𝚇}$ $\mathrm{𝚒𝚗𝚝}$ $𝙺$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚎𝚌}-\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}\right)$
Restrictions
 $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁},\mathrm{𝚟𝚊𝚛}\right)$ $|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}|\ge 2$ $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}\right)$ $\mathrm{𝙼𝙰𝚇}\ge 1$ $𝙺\ge 2$ $𝙺<|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂},\mathrm{𝚟𝚎𝚌}\right)$ $|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}|\ge 1$ $\mathrm{𝚜𝚊𝚖𝚎}_\mathrm{𝚜𝚒𝚣𝚎}$$\left(\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂},\mathrm{𝚟𝚎𝚌}\right)$
Purpose

$\mathrm{𝙼𝙰𝚇}$ is equal to the maximum number of occurrences of identical vectors derived from the vectors $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ in the following way. To each vector $〈{v}_{1},{v}_{2},\cdots ,{v}_{m}〉$ of $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ (with ${v}_{1},{v}_{2},\cdots ,{v}_{m}$ distinct) let $〈{s}_{1},{s}_{2},\cdots ,{s}_{m}〉$ be the corresponding sorted vector by increasing component. We generate all vectors $〈{u}_{1},{u}_{2},\cdots ,{u}_{𝙺}〉$ such that ${u}_{1}={s}_{{i}_{1}}$, ${u}_{2}={s}_{{i}_{2}}$, $\cdots$, ${u}_{𝙺}={s}_{{i}_{𝙺}}$ (with $1\le {i}_{1}<{i}_{2}<\cdots <{i}_{𝙺}\le m$).

Example
$\left(\begin{array}{c}1,2,〈\begin{array}{c}\mathrm{𝚟𝚎𝚌}-〈4,2,1〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈2,3,5〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈3,6,4〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈5,4,7〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈6,5,1〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈7,6,2〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈3,1,7〉\hfill \end{array}〉\hfill \end{array}\right)$

Given the seven vectors of the example we respectively generate:

• the pairs $〈1,2〉$, $〈1,4〉$ and $〈2,4〉$ from the triple $〈4,2,1〉$,

• the pairs $〈2,3〉$, $〈2,5〉$ and $〈3,5〉$ from the triple $〈2,3,5〉$,

• the pairs $〈3,4〉$, $〈3,6〉$ and $〈4,6〉$ from the triple $〈3,6,4〉$,

• the pairs $〈4,5〉$, $〈4,7〉$ and $〈5,7〉$ from the triple $〈5,4,7〉$,

• the pairs $〈1,5〉$, $〈1,6〉$ and $〈5,6〉$ from the triple $〈6,5,1〉$,

• the pairs $〈2,6〉$, $〈2,7〉$ and $〈6,7〉$ from the triple $〈7,6,2〉$,

• the pairs $〈1,3〉$, $〈1,7〉$ and $〈3,7〉$ from the triple $〈3,1,7〉$.

Putting these pairs together, we get the set of pairs $\left\{〈1,2〉$, $〈1,3〉$, $〈1,4〉$, $〈1,5〉$, $〈1,6〉$, $〈1,7〉$, $〈2,3〉$, $〈2,4〉$, $〈2,5〉$, $〈2,6〉$, $〈2,7〉$, $〈3,4〉$, $〈3,5〉$, $〈3,6〉$, $〈3,7〉$, $〈4,5〉$, $〈4,6〉$, $〈4,7〉$, $〈5,6〉$, $〈5,7〉$, $〈6,7〉\right\}$. The $\mathrm{𝚖𝚊𝚡}_\mathrm{𝚘𝚌𝚌}_\mathrm{𝚘𝚏}_\mathrm{𝚜𝚘𝚛𝚝𝚎𝚍}_\mathrm{𝚝𝚞𝚙𝚕𝚎𝚜}_\mathrm{𝚘𝚏}_\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$ constraint holds since each vector has pairwise distinct components, and since $\mathrm{𝙼𝙰𝚇}$ is set to one and all the generated pairs are distinct.

Typical
 $\mathrm{𝙼𝙰𝚇}=1$ $𝙺+1=|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}|$ $|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}|>2$
Arg. properties
• Functional dependency: $\mathrm{𝙼𝙰𝚇}$ determined by $𝙺$ and $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$.

• Contractible wrt. $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ when $\mathrm{𝙼𝙰𝚇}=1$.

Usage

This constraint occurs in balanced block design problems where all vectors are not necessarily sorted.