## 5.247. max_occ_of_tuples_of_values

Origin

Design.

Constraint

$\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{𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢}_\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}〉$ (with ${v}_{1}<{v}_{2}\wedge \cdots \wedge {v}_{m-1}<{v}_{m}$) of $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ we generate all vectors $〈{u}_{1},{u}_{2},\cdots ,{u}_{𝙺}〉$ such that ${u}_{1}={v}_{{i}_{1}}$, ${u}_{2}={v}_{{i}_{2}}$, $\cdots$, ${u}_{𝙺}={v}_{{i}_{𝙺}}$ (with $1\le {i}_{1}<{i}_{2}<\cdots <{i}_{𝙺}\le m$).

Example
$\left(\begin{array}{c}1,2,〈\begin{array}{c}\mathrm{𝚟𝚎𝚌}-〈1,2,4〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈2,3,5〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈3,4,6〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈4,5,7〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈1,5,6〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈2,6,7〉,\hfill \\ \mathrm{𝚟𝚎𝚌}-〈1,3,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 $〈1,2,4〉$,

• 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,4,6〉$,

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

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

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

• the pairs $〈1,3〉$, $〈1,7〉$ and $〈3,7〉$ from the triple $〈1,3,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{𝚟𝚊𝚕𝚞𝚎𝚜}$ constraint holds since the components of the original seven vectors are strictly increasing, and since $\mathrm{𝙼𝙰𝚇}$ is set to one and all the generated pairs are distinct.

Typical
 $\mathrm{𝙼𝙰𝚇}\le 2$ $|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}|<𝙺+5$ $𝙺=2\vee 𝙺+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 [HellRosa72], [LindnerRosa80] such as Steiner or Kirkman triples.