Skip to main content
updated
Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

Using some Mathematica, we we let $h(m,n)$ be defined as $$ h(m,n) = \max_{f : [n] \to [m] } | \mathrm{image}(f) |. $$

For For small combinations of $(m,n)$, we get the table $$ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 3 & 5 & 8 & 12 & 16 & 21 & 27 \\ 1 & 3 & 6 & 9 & 13 & 18 & 24 & 31 \\ 1 & 3 & 6 & 10 & 14 & 19 & 25 & 32 \\ 1 & 3 & 6 & 10 & 15 & 20 & 26 & 33 \\ \end{array} $$\begin{array}{cccccccc} 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 2 & 4 & 7 & 8 & 8 & 8 & 8 & 8 \\ 2 & 4 & 7 & 11 & 13 & 14 & 15 & 16 \\ 2 & 4 & 7 & 11 & 16 & 19 & 21 & 23 \\ 2 & 4 & 7 & 11 & 16 & 22 & 26 & 29 \\ \end{array} and the main diagonal are the numbers you found.$$ Rows are indexed by $m$.The code used here is:

cardSort[wrd_List] := Prepend[
   Union[Join @@ Table[
      Union[wrd[[i ;; j]]],
      {i, Length@wrd}, {j, i, Length@wrd}]]
   , {}];
h2[m_, n_] := 
  h2[m, n] = Max@Table[Length@cardSort[w], {w, Tuples[Range[m], n]}];

SomeOLD Answer: If we instead set $$ h'(m,n) = \max_{f : [n] \to [m] } | \mathrm{image}(f) |. $$ where the we now map to $f$ to the set of all contiguous substrings, we get the table $$ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 3 & 5 & 8 & 12 & 16 & 21 & 27 \\ 1 & 3 & 6 & 9 & 13 & 18 & 24 & 31 \\ 1 & 3 & 6 & 10 & 14 & 19 & 25 & 32 \\ 1 & 3 & 6 & 10 & 15 & 20 & 26 & 33 \\ \end{array} $$ Some search in the OEIS suggests that we (almost always have) $$ h(m,n) = \text{Number of edges in $(m+1)$-partite Turán graph of order $n+1$.} $$$$ h'(m,n) = \text{Number of edges in $(m+1)$-partite Turán graph of order $n+1$.} $$

The Mathematica code I used here is

card[wrd_List] := 
  Length@Union[
    Join @@ Table[wrd[[i ;; j]], {i, Length@wrd}, {j, i, Length@wrd}]];
h[m_, n_] := h[m, n] = Max@Table[card[w], {w, Tuples[Range[m], n]}];

Using some Mathematica, we we let $h(m,n)$ be defined as $$ h(m,n) = \max_{f : [n] \to [m] } | \mathrm{image}(f) |. $$

For small combinations of $(m,n)$, we get the table $$ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 3 & 5 & 8 & 12 & 16 & 21 & 27 \\ 1 & 3 & 6 & 9 & 13 & 18 & 24 & 31 \\ 1 & 3 & 6 & 10 & 14 & 19 & 25 & 32 \\ 1 & 3 & 6 & 10 & 15 & 20 & 26 & 33 \\ \end{array} $$ and the main diagonal are the numbers you found. Rows are indexed by $m$.

Some search in the OEIS suggests that we (almost always have) $$ h(m,n) = \text{Number of edges in $(m+1)$-partite Turán graph of order $n+1$.} $$

The Mathematica code I used is

card[wrd_List] := 
  Length@Union[
    Join @@ Table[wrd[[i ;; j]], {i, Length@wrd}, {j, i, Length@wrd}]];
h[m_, n_] := h[m, n] = Max@Table[card[w], {w, Tuples[Range[m], n]}];

Using some Mathematica, we we let $h(m,n)$ be defined as $$ h(m,n) = \max_{f : [n] \to [m] } | \mathrm{image}(f) |. $$ For small combinations of $(m,n)$, we get the table \begin{array}{cccccccc} 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 2 & 4 & 7 & 8 & 8 & 8 & 8 & 8 \\ 2 & 4 & 7 & 11 & 13 & 14 & 15 & 16 \\ 2 & 4 & 7 & 11 & 16 & 19 & 21 & 23 \\ 2 & 4 & 7 & 11 & 16 & 22 & 26 & 29 \\ \end{array} $$ The code used here is:

cardSort[wrd_List] := Prepend[
   Union[Join @@ Table[
      Union[wrd[[i ;; j]]],
      {i, Length@wrd}, {j, i, Length@wrd}]]
   , {}];
h2[m_, n_] := 
  h2[m, n] = Max@Table[Length@cardSort[w], {w, Tuples[Range[m], n]}];

OLD Answer: If we instead set $$ h'(m,n) = \max_{f : [n] \to [m] } | \mathrm{image}(f) |. $$ where the we now map to $f$ to the set of all contiguous substrings, we get the table $$ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 3 & 5 & 8 & 12 & 16 & 21 & 27 \\ 1 & 3 & 6 & 9 & 13 & 18 & 24 & 31 \\ 1 & 3 & 6 & 10 & 14 & 19 & 25 & 32 \\ 1 & 3 & 6 & 10 & 15 & 20 & 26 & 33 \\ \end{array} $$ Some search in the OEIS suggests that we (almost always have) $$ h'(m,n) = \text{Number of edges in $(m+1)$-partite Turán graph of order $n+1$.} $$

The Mathematica code I used here is

card[wrd_List] := 
  Length@Union[
    Join @@ Table[wrd[[i ;; j]], {i, Length@wrd}, {j, i, Length@wrd}]];
h[m_, n_] := h[m, n] = Max@Table[card[w], {w, Tuples[Range[m], n]}];
updated
Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

Using some Mathematica, we we let $h(m,n)$ be defined as $$ h(m,n) = \max_{f : [n] \to [m] } | \mathrm{image}(f) |. $$

For small combinations of $(m,n)$, we get the table $$ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 3 & 5 & 8 & 12 & 16 & 21 & 27 \\ 1 & 3 & 6 & 9 & 13 & 18 & 24 & 31 \\ 1 & 3 & 6 & 10 & 14 & 19 & 25 & 32 \\ 1 & 3 & 6 & 10 & 15 & 20 & 26 & 33 \\ \end{array} $$ and the main diagonal are the numbers you found. Rows are indexed by $m$.

Some search in the OEIS suggests that $$ h(m,n) = \text{Number of edges in $(m-1)$-partite Turán graph of order $n$.} $$ we (almost always have) I'll think about a bijection once$$ h(m,n) = \text{Number of edges in $(m+1)$-partite Turán graph of order $n+1$.} $$

The Mathematica code I remember what a Turán graphused is.

card[wrd_List] := 
  Length@Union[
    Join @@ Table[wrd[[i ;; j]], {i, Length@wrd}, {j, i, Length@wrd}]];
h[m_, n_] := h[m, n] = Max@Table[card[w], {w, Tuples[Range[m], n]}];

Using some Mathematica, we we let $h(m,n)$ be defined as $$ h(m,n) = \max_{f : [n] \to [m] } | \mathrm{image}(f) |. $$

For small combinations of $(m,n)$, we get the table $$ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 3 & 5 & 8 & 12 & 16 & 21 & 27 \\ 1 & 3 & 6 & 9 & 13 & 18 & 24 & 31 \\ 1 & 3 & 6 & 10 & 14 & 19 & 25 & 32 \\ 1 & 3 & 6 & 10 & 15 & 20 & 26 & 33 \\ \end{array} $$ and the main diagonal are the numbers you found. Rows are indexed by $m$.

Some search in the OEIS suggests that $$ h(m,n) = \text{Number of edges in $(m-1)$-partite Turán graph of order $n$.} $$ I'll think about a bijection once I remember what a Turán graph is.

Using some Mathematica, we we let $h(m,n)$ be defined as $$ h(m,n) = \max_{f : [n] \to [m] } | \mathrm{image}(f) |. $$

For small combinations of $(m,n)$, we get the table $$ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 3 & 5 & 8 & 12 & 16 & 21 & 27 \\ 1 & 3 & 6 & 9 & 13 & 18 & 24 & 31 \\ 1 & 3 & 6 & 10 & 14 & 19 & 25 & 32 \\ 1 & 3 & 6 & 10 & 15 & 20 & 26 & 33 \\ \end{array} $$ and the main diagonal are the numbers you found. Rows are indexed by $m$.

Some search in the OEIS suggests that we (almost always have) $$ h(m,n) = \text{Number of edges in $(m+1)$-partite Turán graph of order $n+1$.} $$

The Mathematica code I used is

card[wrd_List] := 
  Length@Union[
    Join @@ Table[wrd[[i ;; j]], {i, Length@wrd}, {j, i, Length@wrd}]];
h[m_, n_] := h[m, n] = Max@Table[card[w], {w, Tuples[Range[m], n]}];
Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

Using some Mathematica, we we let $h(m,n)$ be defined as $$ h(m,n) = \max_{f : [n] \to [m] } | \mathrm{image}(f) |. $$

For small combinations of $(m,n)$, we get the table $$ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 3 & 5 & 8 & 12 & 16 & 21 & 27 \\ 1 & 3 & 6 & 9 & 13 & 18 & 24 & 31 \\ 1 & 3 & 6 & 10 & 14 & 19 & 25 & 32 \\ 1 & 3 & 6 & 10 & 15 & 20 & 26 & 33 \\ \end{array} $$ and the main diagonal are the numbers you found. Rows are indexed by $m$.

Some search in the OEIS suggests that $$ h(m,n) = \text{Number of edges in $(m-1)$-partite Turán graph of order $n$.} $$ I'll think about a bijection once I remember what a Turán graph is.