A332263 Maximal length of a string over the alphabet {0,1,2} with the property that its contiguous substrings of length n all have different quantities of 0's, 1's, or 2's.

3, 7, 12, 17, 22, 30, 39, 45, 56, 66, 77, 90

Offset: 1

Author

Nathaniel Johnston, Feb 08 2020

Keywords

• nonn
• more
• hard

Comments

In other words, the contiguous substrings of length n are all different if we interpret them as multisets.

Since there are binomial(n+2,2) different triples of nonnegative integers summing up to n, we have the bound a(n) <= binomial(n+2,2)+n-1. Equality holds if and only if n <= 3.

Examples

			Maximal strings for n = 1, 2, ..., 8 are:
012
0011220
011122200012
00111122220000121
0100212111000002222211
001011112122220200001012120200
010010220212110100000202222212111110100
021200201101121220202000010111111212222220200
		

Links

• Bert Dobbelaere, C++ program
• MathOverflow, Sequences with 3 Letters

Extensions

a(9)-a(12) from Bert Dobbelaere, Feb 09 2020