{"entities":{"Q1422149":{"pageid":1432889,"ns":120,"title":"Item:Q1422149","lastrevid":70369560,"modified":"2026-04-13T14:18:45Z","type":"item","id":"Q1422149","labels":{"en":{"language":"en","value":"Strings with maximally many distinct subsequences and substrings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2038354"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422149$729B033A-BF35-40DB-941D-D4AF6D483C14","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"91960b39023ea6a360aba12b409937bf395dee5e","datavalue":{"value":{"text":"Strings with maximally many distinct subsequences and substrings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1422149$1B11F7F1-4384-47AB-A2F7-61038B59DC7E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f59f111bb619824796d63da85c143cc1ca921303","datavalue":{"value":"1034.68067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422149$E2D6EA44-95C8-41FE-977C-8DA0EAC1A37A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4dfb28150533e22d65d79bfa5f59ffd9b266d77f","datavalue":{"value":{"entity-type":"item","numeric-id":245971,"id":"Q245971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422149$CCB3373F-23D1-48F1-9EC3-CBACA6D9A4F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"28ed5aa3d9119097d19913a5fb93bbc03bba7846","datavalue":{"value":{"entity-type":"item","numeric-id":414886,"id":"Q414886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422149$449CCA85-A856-4932-B192-5214403A738D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"effec259dd2cfee2180fbd863f6260f5ca98ae9e","datavalue":{"value":{"entity-type":"item","numeric-id":452815,"id":"Q452815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422149$92B31CED-17D7-44DC-A588-D341CFC9C89F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422149$F55DC7E1-17A4-48AA-9DA7-D19B5BB3CAC2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4b42c06db7e24b19fc79361c42f9be31630ff05","datavalue":{"value":{"time":"+2004-02-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1422149$F9093E85-F7AF-42AC-AA7C-46F868B36436","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d33cef9113b6162d0dac820ddf29a8c356904eba","datavalue":{"value":"https://eudml.org/doc/123417","type":"string"},"datatype":"url"},"type":"statement","id":"Q1422149$24D541F9-78AA-42AC-919A-7CC49DBD0BDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"4c64866b6d986353f109b3ea48c570d41e8173ec","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_11/Abstracts/v11i1r8.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1422149$623F29F2-FC83-46EE-8A0B-D58C182CE26B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"36eee375cf9f623f539eaeebd4cb21d9e05610c6","datavalue":{"value":"Summary: A natural problem in extremal combinatorics is to maximize the number of distinct subsequences for any length-\\(n\\) string over a finite alphabet \\(\\Sigma\\); this value grows exponentially, but slower than \\(2^n\\). We use the probabilistic method to determine the maximizing string, which is a cyclically repeating string. The number of distinct subsequences is exactly enumerated by a generating function, from which we also derive asymptotic estimates. For the alphabet \\(\\Sigma={1,2}, (1,2,1,2,...)\\) has the maximum number of distinct subsequences, namely Fib \\((n+3)-1\\sim ((1+\\sqrt5)/2)^{n+3} / \\sqrt5\\).  We also consider the same problem with substrings in lieu of subsequences. Here, we show that an appropriately truncated de Bruijn word attains the maximum. For both problems, we compare the performance of random strings with that of the optimal ones.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422149$D49CE392-E571-480C-A776-00F5382CC5F1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422149$7495C169-D222-462F-B603-9ADA2D5CB7B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422149$DFEEBD5A-0B30-4901-9B3D-B082591C1DA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422149$74EE655E-C4EE-41AE-B417-386BB6DC0B38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b85c221f9847adc30512692a640a50dd4e3d1cb","datavalue":{"value":"05A16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422149$DBF8E22B-C3C2-4A95-AB9C-682A5AAD3A82","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ce0a1a5cec8d3d9bf1ba7972f77211d15116d019","datavalue":{"value":"2038354","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422149$ADA4C63D-5877-4DC4-B5BA-520C0B3DD055","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39911c6eb3357797f71228694114dda795773934","datavalue":{"value":"extremal combinatorics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422149$B1B7CF7A-62C4-44E8-B4EC-1BFE3A5DDD06","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422149$2FCB1F9A-65AE-4EDC-BEC8-2C7A819F1C71","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"1e833efb6a66b0b05cce0e9101355251f3f50e1c","datavalue":{"value":"bafkreig4vklyje7i26bw35gs3xuwfnatr56p6anwf4ifgg3usux6q2ky2u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422149$37F81324-E8E2-4228-BC59-468DA7351AD7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e22b856355950a0f89a32b901f950d381929b80","datavalue":{"value":{"entity-type":"item","numeric-id":3024802,"id":"Q3024802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aea76adb2ef4934e6886f52cf50117373bd8f62","datavalue":{"value":{"amount":"+0.7838804721832275","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422149$B9EF6C69-C098-4288-9EA7-C56FDF22CD5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa0ddce23f115998cbf61ee6babc2282066299e1","datavalue":{"value":{"entity-type":"item","numeric-id":2378518,"id":"Q2378518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24799eabd4c6cf97870dcb3580d3d73d92610dbf","datavalue":{"value":{"amount":"+0.7731422185897827","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422149$458600F6-90A3-439C-8451-DBC05808F18F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59b23dc3b6f7e70b6c5056546b9e3758101ba1d6","datavalue":{"value":{"entity-type":"item","numeric-id":5307502,"id":"Q5307502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2420fd6f77bc441819cc37483f616821bfb88372","datavalue":{"value":{"amount":"+0.7611635327339172","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422149$A8F2CAE7-48BA-4CC3-9A7D-04A57D808112","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e15968b0abb38fe899798cf37c2c9961e2d1cbe","datavalue":{"value":{"entity-type":"item","numeric-id":925072,"id":"Q925072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a4c12488cf50c59b136d3c61df87ea64091be14","datavalue":{"value":{"amount":"+0.7601680755615234","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422149$2ED75CA3-799C-441D-8AD6-15F687F4559D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c90405b6473f06c6332eece026ca4cb0a1bd7ffe","datavalue":{"value":{"entity-type":"item","numeric-id":4432080,"id":"Q4432080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c61cb0fba9de79001bb21e9596b31b946e5fefc","datavalue":{"value":{"amount":"+0.7462993264198303","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422149$4F2BD2D4-3394-4FD0-9651-C4A2111E19D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Strings with maximally many distinct subsequences and substrings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Strings_with_maximally_many_distinct_subsequences_and_substrings"}}}}}