Return to Question

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates). For example, $$\begin{array}{l} T_0^4 = (0,1,2,3),\\ T_1^4 = (0,1,3,2),\\ \ldots \\ T_{23}^4 = (3,2,1,0). \end{array}$$

(It does not matter how the tuples are enumerated; the example above implies the lexicographic order.)

Then $S_n$ denotes the set $\{T_0^n, T_1^n, \ldots, T_{n!-2}^n, T_{n!-1}^n\}.$ The cardinality of $S_n$ is equal to $n!$

Assuming that $(x, y)$ are two different elements of a given tuple $T$, let $d(T, x, y)$ denote the number of elements between $x$ and $y$ in $T$. For example, if $T = (3, 0, 1, 4, 2)$, we have $$\begin{array}{l} d(T, 3, 0) = d(T, 1, 0) = d(T, 2, 4) = d(T, 4, 2) = 0,\\ d(T, 3, 2) = 3. \end{array}$$

A subset $s$ of $S_n$ is called an “$[n, k]$-set” if and only if for any pair $(x, y)$ of elements of the set $\{0, 1, \ldots, n-2, n-1\}$ there exists an element $t \in s$ such that $d(t, x, y) \leq k$.

Question: given an arbitrary natural number $n > 2$ and a natural number $k$ such that $0 \leq k \le n - 3$, what is the minimal cardinality $M(n,k)$ of an $[n, k]$-set?

If it is impossible to obtain a formula for the exact value of $M(n,k)$, is it possible to obtain a reasonable generalized formula for the upper bound of the value of $M(n,0)$? For example, is it true that $M(n,0) \leq 2 \times \operatorname{ceil}(\sqrt{n})$ for all $n$?

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates). For example, $$\begin{array}{l} T_0^4 = (0,1,2,3),\\ T_1^4 = (0,1,3,2),\\ \ldots \\ T_{23}^4 = (3,2,1,0). \end{array}$$

(It does not matter how the tuples are enumerated; the example above implies the lexicographic order.)

Then $S_n$ denotes the set $\{T_0^n, T_1^n, \ldots, T_{n!-2}^n, T_{n!-1}^n\}.$ The cardinality of $S_n$ is equal to $n!$

Assuming that $(x, y)$ are two different elements of a given tuple $T$, let $d(T, x, y)$ denote the number of elements between $x$ and $y$ in $T$. For example, if $T = (3, 0, 1, 4, 2)$, we have $$\begin{array}{l} d(T, 3, 0) = d(T, 1, 0) = d(T, 2, 4) = d(T, 4, 2) = 0,\\ d(T, 3, 2) = 3. \end{array}$$

A subset $s$ of $S_n$ is called an “$[n, k]$-set” if and only if for any pair $(x, y)$ of elements of the set $\{0, 1, \ldots, n-2, n-1\}$ there exists an element $t \in s$ such that $d(t, x, y) \leq k$.

Question: given an arbitrary natural number $n > 2$ and a natural number $k$ such that $0 \leq k \le n - 3$, what is the minimal cardinality $M(n,k)$ of an $[n, k]$-set?

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates). For example, $$\begin{array}{l} T_0^4 = (0,1,2,3),\\ T_1^4 = (0,1,3,2),\\ \ldots \\ T_{23}^4 = (3,2,1,0). \end{array}$$

(It does not matter how the tuples are enumerated; the example above implies the lexicographic order.)

Then $S_n$ denotes the set $\{T_0^n, T_1^n, \ldots, T_{n!-2}^n, T_{n!-1}^n\}.$ The cardinality of $S_n$ is equal to $n!$

Assuming that $(x, y)$ are two different elements of a given tuple $T$, let $d(T, x, y)$ denote the number of elements between $x$ and $y$ in $T$. For example, if $T = (3, 0, 1, 4, 2)$, we have $$\begin{array}{l} d(T, 3, 0) = d(T, 1, 0) = d(T, 2, 4) = d(T, 4, 2) = 0,\\ d(T, 3, 2) = 3. \end{array}$$

A subset $s$ of $S_n$ is called an “$[n, k]$-set” if and only if for any pair $(x, y)$ of elements of the set $\{0, 1, \ldots, n-2, n-1\}$ there exists an element $t \in s$ such that $d(t, x, y) \leq k$.

Question: given an arbitrary natural number $n > 2$ and a natural number $k$ such that $0 \leq k \le n - 3$, what is the minimal cardinality of an $[n, k]$-set?

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates). For example, $$\begin{array}{l} T_0^4 = (0,1,2,3),\\ T_1^4 = (0,1,3,2),\\ \ldots \\ T_{23}^4 = (3,2,1,0). \end{array}$$

(It does not matter how the tuples are enumerated; the example above implies the lexicographic order.)

Then $S_n$ denotes the set $\{T_0^n, T_1^n, \ldots, T_{n!-2}^n, T_{n!-1}^n\}.$ The cardinality of $S_n$ is equal to $n!$

Assuming that $(x, y)$ are two different elements of a given tuple $T$, let $d(T, x, y)$ denote the number of elements between $x$ and $y$ in $T$. For example, if $T = (3, 0, 1, 4, 2)$, we have $$\begin{array}{l} d(T, 3, 0) = d(T, 1, 0) = d(T, 2, 4) = d(T, 4, 2) = 0,\\ d(T, 3, 2) = 3. \end{array}$$

A subset $s$ of $S_n$ is called an “$[n, k]$-set” if and only if for any pair $(x, y)$ of elements of the set $\{0, 1, \ldots, n-2, n-1\}$ there exists an element $t \in s$ such that $d(t, x, y) \leq k$.

Question: given an arbitrary natural number $n > 2$ and a natural number $k$ such that $0 \leq k \le n - 3$, what is the minimal cardinality $M(n,k)$ of an $[n, k]$-set?

If it is impossible to obtain a formula for the exact value of $M(n,k)$, is it possible to obtain a reasonable generalized formula for the upper bound of the value of $M(n,0)$? For example, is it true that $M(n,0) \leq 2 \times \operatorname{ceil}(\sqrt{n})$ for all $n$?

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates). For example, $$\begin{array}{l} T_0^4 = (0,1,2,3),\\ T_1^4 = (0,1,3,2),\\ \ldots \\ T_{23}^4 = (3,2,1,0). \end{array}$$

(It does not matter how the tuples are enumerated; the example above implies the lexicographic order.)

Then $S_n$ denotes the set $\{T_0^n, T_1^n, \ldots, T_{n!-2}^n, T_{n!-1}^n\}.$ The cardinality of $S_n$ is equal to $n!$

Assuming that $(x, y)$ are two different elements of a given tuple $T$, let $d(T, x, y)$ denote the number of elements between $x$ and $y$ in $T$. For example, if $T = (3, 0, 1, 4, 2)$, we have $$\begin{array}{l} d(T, 3, 0) = d(T, 1, 0) = d(T, 2, 4) = d(T, 4, 2) = 0,\\ d(T, 3, 2) = 3. \end{array}$$

A subset of $S_n$ is called an “$[n, k]$-set” if and only if for any pair $(x, y)$ of elements of the set $\{0, 1, \ldots, n-2, n-1\}$ there exists an element $t \in S_n$ such that $d(t, x, y) \leq k$.

Question: given an arbitrary natural number $n > 2$ and a natural number $k$ such that $0 \leq k \le n - 3$, what is the minimal cardinality of an $[n, k]$-set?

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates). For example, $$\begin{array}{l} T_0^4 = (0,1,2,3),\\ T_1^4 = (0,1,3,2),\\ \ldots \\ T_{23}^4 = (3,2,1,0). \end{array}$$

(It does not matter how the tuples are enumerated; the example above implies the lexicographic order.)

Then $S_n$ denotes the set $\{T_0^n, T_1^n, \ldots, T_{n!-2}^n, T_{n!-1}^n\}.$ The cardinality of $S_n$ is equal to $n!$

Assuming that $(x, y)$ are two different elements of a given tuple $T$, let $d(T, x, y)$ denote the number of elements between $x$ and $y$ in $T$. For example, if $T = (3, 0, 1, 4, 2)$, we have $$\begin{array}{l} d(T, 3, 0) = d(T, 1, 0) = d(T, 2, 4) = d(T, 4, 2) = 0,\\ d(T, 3, 2) = 3. \end{array}$$

A subset $s$ of $S_n$ is called an “$[n, k]$-set” if and only if for any pair $(x, y)$ of elements of the set $\{0, 1, \ldots, n-2, n-1\}$ there exists an element $t \in s$ such that $d(t, x, y) \leq k$.

Question: given an arbitrary natural number $n > 2$ and a natural number $k$ such that $0 \leq k \le n - 3$, what is the minimal cardinality of an $[n, k]$-set?