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

                    Create new schema in PostgreSQL using DBeaver

                    Image
                    0 At the beginning of my current job I had limited access to DB but recently my role is changed to superuser, admin, and owner. My colleague who was the previous DB admin is able to create a schema or change the permissions as there is a permission tab in the properties and he can change permissions by clicking easily. Would you please let me know how I can create schema and change permissions as well? Why his dbeaver looks different from me? He can easily right click on the schema folder on top of all schemas on the left side column and select create new schema while I do not have that, like the following picture I found on the internet. postgresql database-schema dbeaver share | improve this question
                    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