Run-Maximal Strings

Introduction

Let r(x) return the number of runs in a string x, and let ρ(n) be the maximum number of runs over all strings of length n. Let ρd(n) be the maximum number of runs over all strings of length n with exactly d distinct characters.


Table of ρd(n) Values -- (d, n-d) Table

We present the ρd(n) values in a table where the columns are indexed by n-d and the rows are indexed by d. The key values are those which fall on the diagonal d = n-d.

The given ρ values are links to records of all the corresponding run-maximal strings. Each string is labelled with either "[pal]" or "[rev]". Consider a canonical representation of a string, in which the first unique character is represented by a, the second by b, and so on. If the canonical representation of the reversal of a string is equal to itself, we call it a p-palindrome, and it labelled "[pal]". (An example is the string "aabb": when reversed it becomes "bbaa", but putting it into canonical form yields the string "aabb" again, so it is a p-palindrome.) If the canonical representation of the reversal of a string is distinct from the original string, we call them "reversible twins". We only list the lexicographically lesser of the twins, and label it with "[rev]". (An example is the string "aab": when reversed it becomes "baa", and putting it into canonical form yields the string "abb", which is distinct from the original. "aab" and "abb" are reversible twins.)


n-d
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
d
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 2 2 3 4 5 5 6 7 8 8 10 10 11 12 13 14 15 15 16 17 18 19 20 21 22 23 24 25 26 27 27 28 29 30 30 31 32 33 35 35 36 37 38 39 40 41 42 43 44 45 46 46 47 48 49 50 51 52 53 54 55 56 56 57 58 59 60 61 62 63 64
3 1 2 3 3 4 5 6 6 7 8 9 10 11 11 12 13 14 15 16 16 17 18 19 20 21 22 23 24 25 26 27 28 28 29 30 31 31 32 33 35 36 36                                                            
4 1 2 3 4 4 5 6 7 7 8 9 10 11 12 12 13 14 15 16 17 17 18 19 20 21 22 23 24 25 26 27 28 29 29                                                                            
5 1 2 3 4 5 5 6 7 8 8 9 10 11 12 13 13 14 15 16 17 18 18 19 20 21 22 23 24 25                                                                                      
6 1 2 3 4 5 6 6 7 8 9 9 10 11 12 13 14 14 15 16 17 18 19 19 20 21                                                                                              
7 1 2 3 4 5 6 7 7 8 9 10 10 11 12 13 14 15 15 16 17 18 19 20                                                                                                  
8 1 2 3 4 5 6 7 8 8 9 10 11 11 12 13 14 15 16 16 17 18 19                                                                                                    
9 1 2 3 4 5 6 7 8 9 9 10 11 12 12 13 14 15 16 17 17 18                                                                                                      
10 1 2 3 4 5 6 7 8 9 10 10 11 12 13 13 14 15 16 17                                                                                                          
11 1 2 3 4 5 6 7 8 9 10 11 11 12 13 14 14                                                                                                                
12 1 2 3 4 5 6 7 8 9 10 11 12 12 13 14 15                                                                                                                
13 1 2 3 4 5 6 7 8 9 10 11 12 13 13 14                                                                                                                  
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 14                                                                                                                  
15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15                                                                                                                  
16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16                                                                                                                
17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17                                                                                                              
18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18                                                                                                            
19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19                                                                                                          
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20                                                                                                        
21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21                                                                                                      
22 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22                                                                                                    
23 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23                                                                                                  

This information can also be presented in a (d, n-2d) table.


Change Log

September 6, 2011 - Added link to (d, n-2d) table.

May 9, 2011 - Inserted unlinked entries calculated based on other entries in the table.

August 27, 2010 - Added links to the distinct run-maximal string generated for each ρd(n), and description of record notation.

June 14, 2010 - Chart posted.