Maximal size of a set of ordered words such that no pair of letters occurs twice












2












$begingroup$


Consider an alphabet $Sigma={1,dots,n}$.
An ordered word is a word $w=w_1w_2dots w_kinSigma^*$ such that $w_1<w_2<dots<w_k$. In other words, an ordered word is a strictly increasing sequence over ${1,dots,n}$.



Let us call $O_{n,k}$ the set of all ordered words over ${1,dots,n}$ of length $k$. Clearly, there are $binom{n}{k}$ many ordered words of length $k$.



Now, what I am looking for is the maximal size of a subset $Msubseteq O_{n,k}$ such that each pair of letters $ij$ ($1le i<jle n$) occurs at most once as a consecutive substring in any word of $M$. What is the maximal size of such a subset?



Formally, let $#_{ij}(M)$ be the number of words in $M$ that contain $ij$ as a consecutive substring, then
$$m_{n,k}=max{|M|:Msubseteq O_{n,k}text{ and }#_{ij}(M)le 1text{ for all }i,jtext{ with }1le i<jle n}.$$
What is $m_{n,k}$?



Asymptotic behavior as well as some non-trivial lower and upper bounds would be helpful.



$ $



Example: $Sigma={1,2,3,4}$ and $k=3$.



All ordered words of length $3$ are
$$O_{4,3}={123,124,134,234}.$$
A maximal subset such that no pair occurs more than once would be
$$M={123,134},$$
because all pairs $(12,13,14,23,24,34)$ occur at most once as a consecutive substring in $M$ and there is no set of size $3$ with this property. It follows that $m_{4,3}=2$.



Thank for any help.






combinatorics word-combinatorics







share|cite|improve this question











$endgroup$

















    2












    $begingroup$


    Consider an alphabet $Sigma={1,dots,n}$.
    An ordered word is a word $w=w_1w_2dots w_kinSigma^*$ such that $w_1<w_2<dots<w_k$. In other words, an ordered word is a strictly increasing sequence over ${1,dots,n}$.



    Let us call $O_{n,k}$ the set of all ordered words over ${1,dots,n}$ of length $k$. Clearly, there are $binom{n}{k}$ many ordered words of length $k$.



    Now, what I am looking for is the maximal size of a subset $Msubseteq O_{n,k}$ such that each pair of letters $ij$ ($1le i<jle n$) occurs at most once as a consecutive substring in any word of $M$. What is the maximal size of such a subset?



    Formally, let $#_{ij}(M)$ be the number of words in $M$ that contain $ij$ as a consecutive substring, then
    $$m_{n,k}=max{|M|:Msubseteq O_{n,k}text{ and }#_{ij}(M)le 1text{ for all }i,jtext{ with }1le i<jle n}.$$
    What is $m_{n,k}$?



    Asymptotic behavior as well as some non-trivial lower and upper bounds would be helpful.



    $ $



    Example: $Sigma={1,2,3,4}$ and $k=3$.



    All ordered words of length $3$ are
    $$O_{4,3}={123,124,134,234}.$$
    A maximal subset such that no pair occurs more than once would be
    $$M={123,134},$$
    because all pairs $(12,13,14,23,24,34)$ occur at most once as a consecutive substring in $M$ and there is no set of size $3$ with this property. It follows that $m_{4,3}=2$.



    Thank for any help.






    combinatorics word-combinatorics







    share|cite|improve this question











    $endgroup$















      2












      2








      2





      $begingroup$


      Consider an alphabet $Sigma={1,dots,n}$.
      An ordered word is a word $w=w_1w_2dots w_kinSigma^*$ such that $w_1<w_2<dots<w_k$. In other words, an ordered word is a strictly increasing sequence over ${1,dots,n}$.



      Let us call $O_{n,k}$ the set of all ordered words over ${1,dots,n}$ of length $k$. Clearly, there are $binom{n}{k}$ many ordered words of length $k$.



      Now, what I am looking for is the maximal size of a subset $Msubseteq O_{n,k}$ such that each pair of letters $ij$ ($1le i<jle n$) occurs at most once as a consecutive substring in any word of $M$. What is the maximal size of such a subset?



      Formally, let $#_{ij}(M)$ be the number of words in $M$ that contain $ij$ as a consecutive substring, then
      $$m_{n,k}=max{|M|:Msubseteq O_{n,k}text{ and }#_{ij}(M)le 1text{ for all }i,jtext{ with }1le i<jle n}.$$
      What is $m_{n,k}$?



      Asymptotic behavior as well as some non-trivial lower and upper bounds would be helpful.



      $ $



      Example: $Sigma={1,2,3,4}$ and $k=3$.



      All ordered words of length $3$ are
      $$O_{4,3}={123,124,134,234}.$$
      A maximal subset such that no pair occurs more than once would be
      $$M={123,134},$$
      because all pairs $(12,13,14,23,24,34)$ occur at most once as a consecutive substring in $M$ and there is no set of size $3$ with this property. It follows that $m_{4,3}=2$.



      Thank for any help.






      combinatorics word-combinatorics







      share|cite|improve this question











      $endgroup$




      Consider an alphabet $Sigma={1,dots,n}$.
      An ordered word is a word $w=w_1w_2dots w_kinSigma^*$ such that $w_1<w_2<dots<w_k$. In other words, an ordered word is a strictly increasing sequence over ${1,dots,n}$.



      Let us call $O_{n,k}$ the set of all ordered words over ${1,dots,n}$ of length $k$. Clearly, there are $binom{n}{k}$ many ordered words of length $k$.



      Now, what I am looking for is the maximal size of a subset $Msubseteq O_{n,k}$ such that each pair of letters $ij$ ($1le i<jle n$) occurs at most once as a consecutive substring in any word of $M$. What is the maximal size of such a subset?



      Formally, let $#_{ij}(M)$ be the number of words in $M$ that contain $ij$ as a consecutive substring, then
      $$m_{n,k}=max{|M|:Msubseteq O_{n,k}text{ and }#_{ij}(M)le 1text{ for all }i,jtext{ with }1le i<jle n}.$$
      What is $m_{n,k}$?



      Asymptotic behavior as well as some non-trivial lower and upper bounds would be helpful.



      $ $



      Example: $Sigma={1,2,3,4}$ and $k=3$.



      All ordered words of length $3$ are
      $$O_{4,3}={123,124,134,234}.$$
      A maximal subset such that no pair occurs more than once would be
      $$M={123,134},$$
      because all pairs $(12,13,14,23,24,34)$ occur at most once as a consecutive substring in $M$ and there is no set of size $3$ with this property. It follows that $m_{4,3}=2$.



      Thank for any help.






      combinatorics word-combinatorics




      combinatorics word-combinatorics






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited 2 hours ago







      Danny

















      asked 4 hours ago









      DannyDanny

      73939




      73939






















          1 Answer
          1






          active

          oldest

          votes


















          2












          $begingroup$

          There is a simple upper bound of $$frac{binom{n}{2}}{k-1},$$ following from the fact that there are $binom{n}{2}$ ordered pairs of elements, and each ordered word contains $k-1$ of them.



          There is an almost matching lower bound of
          $$
          frac{binom{n-k+1}{2}}{k-1}.
          $$
          This shows that for fixed $k$, the answer is asymptotically
          $$
          frac{n^2}{2(k-1)} pm O(n).
          $$



          For every $c geq 1$ and $1 leq d leq c$, we can consider the collection of ordered words of the form
          $$
          d,d+c,ldots,d+(k-1)c \
          d+(k-1)c,d+(k+1)c,ldots,d+2(k-1)c \
          ldots
          $$
          These collections for all $c,d$ have disjoint pairs. For a given $m leq n$ and $c$, there is a word of this type if $m-(k-1)c geq 1$, that is, if $c leq frac{m-1}{k-1}$. Therefore, the total number of words is
          $$
          sum_{m=k}^n leftlfloor frac{m-1}{k-1} rightrfloor.
          $$
          We can estimate this sum roughly by
          $$
          sum_{m=k}^n left(frac{m-1}{k-1}-1right) =
          sum_{m=k}^n frac{m-k}{k-1} = frac{binom{n-k+1}{2}}{k-1}.
          $$






          share|cite|improve this answer









          $endgroup$














            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "419"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106296%2fmaximal-size-of-a-set-of-ordered-words-such-that-no-pair-of-letters-occurs-twice%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            2












            $begingroup$

            There is a simple upper bound of $$frac{binom{n}{2}}{k-1},$$ following from the fact that there are $binom{n}{2}$ ordered pairs of elements, and each ordered word contains $k-1$ of them.



            There is an almost matching lower bound of
            $$
            frac{binom{n-k+1}{2}}{k-1}.
            $$
            This shows that for fixed $k$, the answer is asymptotically
            $$
            frac{n^2}{2(k-1)} pm O(n).
            $$



            For every $c geq 1$ and $1 leq d leq c$, we can consider the collection of ordered words of the form
            $$
            d,d+c,ldots,d+(k-1)c \
            d+(k-1)c,d+(k+1)c,ldots,d+2(k-1)c \
            ldots
            $$
            These collections for all $c,d$ have disjoint pairs. For a given $m leq n$ and $c$, there is a word of this type if $m-(k-1)c geq 1$, that is, if $c leq frac{m-1}{k-1}$. Therefore, the total number of words is
            $$
            sum_{m=k}^n leftlfloor frac{m-1}{k-1} rightrfloor.
            $$
            We can estimate this sum roughly by
            $$
            sum_{m=k}^n left(frac{m-1}{k-1}-1right) =
            sum_{m=k}^n frac{m-k}{k-1} = frac{binom{n-k+1}{2}}{k-1}.
            $$






            share|cite|improve this answer









            $endgroup$


















              2












              $begingroup$

              There is a simple upper bound of $$frac{binom{n}{2}}{k-1},$$ following from the fact that there are $binom{n}{2}$ ordered pairs of elements, and each ordered word contains $k-1$ of them.



              There is an almost matching lower bound of
              $$
              frac{binom{n-k+1}{2}}{k-1}.
              $$
              This shows that for fixed $k$, the answer is asymptotically
              $$
              frac{n^2}{2(k-1)} pm O(n).
              $$



              For every $c geq 1$ and $1 leq d leq c$, we can consider the collection of ordered words of the form
              $$
              d,d+c,ldots,d+(k-1)c \
              d+(k-1)c,d+(k+1)c,ldots,d+2(k-1)c \
              ldots
              $$
              These collections for all $c,d$ have disjoint pairs. For a given $m leq n$ and $c$, there is a word of this type if $m-(k-1)c geq 1$, that is, if $c leq frac{m-1}{k-1}$. Therefore, the total number of words is
              $$
              sum_{m=k}^n leftlfloor frac{m-1}{k-1} rightrfloor.
              $$
              We can estimate this sum roughly by
              $$
              sum_{m=k}^n left(frac{m-1}{k-1}-1right) =
              sum_{m=k}^n frac{m-k}{k-1} = frac{binom{n-k+1}{2}}{k-1}.
              $$






              share|cite|improve this answer









              $endgroup$
















                2












                2








                2





                $begingroup$

                There is a simple upper bound of $$frac{binom{n}{2}}{k-1},$$ following from the fact that there are $binom{n}{2}$ ordered pairs of elements, and each ordered word contains $k-1$ of them.



                There is an almost matching lower bound of
                $$
                frac{binom{n-k+1}{2}}{k-1}.
                $$
                This shows that for fixed $k$, the answer is asymptotically
                $$
                frac{n^2}{2(k-1)} pm O(n).
                $$



                For every $c geq 1$ and $1 leq d leq c$, we can consider the collection of ordered words of the form
                $$
                d,d+c,ldots,d+(k-1)c \
                d+(k-1)c,d+(k+1)c,ldots,d+2(k-1)c \
                ldots
                $$
                These collections for all $c,d$ have disjoint pairs. For a given $m leq n$ and $c$, there is a word of this type if $m-(k-1)c geq 1$, that is, if $c leq frac{m-1}{k-1}$. Therefore, the total number of words is
                $$
                sum_{m=k}^n leftlfloor frac{m-1}{k-1} rightrfloor.
                $$
                We can estimate this sum roughly by
                $$
                sum_{m=k}^n left(frac{m-1}{k-1}-1right) =
                sum_{m=k}^n frac{m-k}{k-1} = frac{binom{n-k+1}{2}}{k-1}.
                $$






                share|cite|improve this answer









                $endgroup$



                There is a simple upper bound of $$frac{binom{n}{2}}{k-1},$$ following from the fact that there are $binom{n}{2}$ ordered pairs of elements, and each ordered word contains $k-1$ of them.



                There is an almost matching lower bound of
                $$
                frac{binom{n-k+1}{2}}{k-1}.
                $$
                This shows that for fixed $k$, the answer is asymptotically
                $$
                frac{n^2}{2(k-1)} pm O(n).
                $$



                For every $c geq 1$ and $1 leq d leq c$, we can consider the collection of ordered words of the form
                $$
                d,d+c,ldots,d+(k-1)c \
                d+(k-1)c,d+(k+1)c,ldots,d+2(k-1)c \
                ldots
                $$
                These collections for all $c,d$ have disjoint pairs. For a given $m leq n$ and $c$, there is a word of this type if $m-(k-1)c geq 1$, that is, if $c leq frac{m-1}{k-1}$. Therefore, the total number of words is
                $$
                sum_{m=k}^n leftlfloor frac{m-1}{k-1} rightrfloor.
                $$
                We can estimate this sum roughly by
                $$
                sum_{m=k}^n left(frac{m-1}{k-1}-1right) =
                sum_{m=k}^n frac{m-k}{k-1} = frac{binom{n-k+1}{2}}{k-1}.
                $$







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered 1 hour ago









                Yuval FilmusYuval Filmus

                195k14184349




                195k14184349






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Computer Science Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid …



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106296%2fmaximal-size-of-a-set-of-ordered-words-such-that-no-pair-of-letters-occurs-twice%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    -

                    Popular posts from this blog

                    Costa Masnaga

                    Image
                    .mw-parser-output .avviso .mbox-text-div>div,.mw-parser-output .avviso .mbox-text-full-div>div{font-size:90%}.mw-parser-output .avviso .mbox-image div{width:52px}.mw-parser-output .avviso .mbox-text-full-div .hide-when-compact{display:block} Questa voce o sezione sull'argomento Lombardia non cita le fonti necessarie o quelle presenti sono insufficienti . Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Costa Masnaga comune Localizzazione Stato   Italia Regione Lombardia Provincia Lecco Amministrazione Sindaco Sabina Panzeri (Al centro il cittadino) dall'08/06/2009 Territorio Coordinate 45°46′N 9°17′E  /  45.766667°N 9.283333°E 45.766667; 9.283333  ( Costa Masnaga ) Coordinate: 45°46′N 9°17′E  /  45.766667°N 9.283333°E 45.766667; 9.283333  ( Costa Masnaga ) Altitudine 318 m s.l.m...
                    Read more

                    Fotorealismo

                    Image
                    Guerrino Boatto, Venice's St. Barnaba Church and canal Il fotorealismo è un genere di pittura basato sull'uso di una o più fotografie dalle quali l'artista prende le informazioni necessarie da utilizzare poi nel processo della creazione dell'opera, in genere ad olio o ad acrilico, al fine di avere un aspetto finale il più simile possibile alla fotografia. Indice 1 Storia 2 Lista dei fotorealisti 3 Note 4 Voci correlate 5 Altri progetti Storia | Il fotorealismo è un movimento che nasce negli Stati Uniti d'America alla fine degli anni sessanta [1] sulla scia della Pop Art [2] [3] [4] , e insieme condividono il carattere reazionario verso la travolgente ascesa dei media, che alla metà del ventesimo secolo si trasforma in un fenomeno di massa talmente imponente da minacciare il valore dell'immagine nell'arte. [5] [6] Ne consegue così che, colto il gesto d'inizio che fu della Pop Art, i fotorealisti aprono ad un ...
                    Read more

                    Sidney Franklin

                    Image
                    Questa voce sull'argomento registi statunitensi è solo un abbozzo . Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Sidney Franklin, foto di Carl Van Vechten Oscar alla memoria Irving G. Thalberg 1943 Sidney Franklin , all'anagrafe Sidney Arnold Franklin , (San Francisco, 21 marzo 1893 – Santa Monica, 18 maggio 1972), è stato un regista, produttore cinematografico e attore statunitense. Il 20 giugno 1963, si sposò con l'attrice australiana Enid Bennett. Il matrimonio durò fino alla morte dell'attrice, il 14 maggio 1969 [1] Indice 1 Filmografia 1.1 Regista 1.2 Aiuto regia (parziale) 1.3 Produttore 1.4 Attore (parziale) 2 Note 3 Altri progetti 4 Collegamenti esterni Filmografia | Regista | The Baby , co-regia Chester M. Franklin (1915) The Rivals , co-regia Chester M. Franklin (1915) Little Dick's First Case , co-regia Chester M. Franklin (1915) Her Filmland Hero , co-...
                    Read more