login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
1

%I #14 Feb 09 2020 10:41:21

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

%N 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.

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

%C 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.

%H Bert Dobbelaere, <a href="/A332263/a332263.cpp.txt">C++ program</a>

%H MathOverflow, <a href="https://mathoverflow.net/questions/268428/sequences-with-3-letters">Sequences with 3 Letters</a>

%e Maximal strings for n = 1, 2, ..., 8 are:

%e 012

%e 0011220

%e 011122200012

%e 00111122220000121

%e 0100212111000002222211

%e 001011112122220200001012120200

%e 010010220212110100000202222212111110100

%e 021200201101121220202000010111111212222220200

%K nonn,more,hard

%O 1,1

%A _Nathaniel Johnston_, Feb 08 2020

%E a(9)-a(12) from _Bert Dobbelaere_, Feb 09 2020