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
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
	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
	3	1	2	3	3	4	5	6	6	7	8	9	10	11	11	12	13	14	15	16	16	17	18
	4	1	2	3	4	4	5	6	7	7	8	9	10	11
	5	1	2	3	4	5	5	6	7	8	8	9	10	11
	6	1	2	3	4	5	6	6	7	8	9	9	10
	7	1	2	3	4	5	6	7	7	8	9
	8	1	2	3	4	5	6	7	8	8	9
	9	1	2	3	4	5	6	7	8	9	9
	10	1	2	3	4	5	6	7	8	9	10
	11	1	2	3	4	5	6	7	8	9	10	11
	12	1	2	3	4	5	6	7	8	9	10	11	12
	13	1	2	3	4	5	6	7	8	9	10	11	12	13
	14	1	2	3	4	5	6	7	8	9	10	11	12	13	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.