login
List of words of length n over an alphabet of size 3 that are in standard order.
3

%I #28 Jan 02 2022 18:21:23

%S 1,11,12,111,112,121,122,123,1111,1112,1121,1122,1123,1211,1212,1213,

%T 1221,1222,1223,1231,1232,1233,11111,11112,11121,11122,11123,11211,

%U 11212,11213,11221,11222,11223,11231,11232,11233,12111,12112,12113,12121,12122

%N List of words of length n over an alphabet of size 3 that are in standard order.

%C We study words made of letters from an alphabet of size b, where b >= 1. We assume the letters are labeled {1,2,3,...,b}. There are b^n possible words of length n.

%C We say that a word is in "standard order" if it has the property that whenever a letter i appears, the letter i-1 has already appeared in the word. This implies that all words begin with the letter 1.

%C These are the words described in row b=3 of the array in A278984.

%C A007051(n-1) gives the number of n-digit terms in this sequence. - _Rémy Sigrist_, Dec 18 2016

%H Rémy Sigrist and N. J. A. Sloane, <a href="/A278985/b278985.txt">Table of n, a(n) for n = 1..14767</a> [Terms 1 through 185 by N. J. A. Sloane]

%H Joerg Arndt and N. J. A. Sloane, <a href="/A278984/a278984.txt">Counting Words that are in "Standard Order"</a>

%p b:= proc(n) option remember; `if`(n=1, [[1]], map(x->

%p seq([x[], i], i=1..min(3, max(x[])+1)), b(n-1)))

%p end:

%p T:= n-> map(x-> parse(cat(x[])), b(n))[]:

%p seq(T(n), n=1..5); # _Alois P. Heinz_, Jan 02 2022

%t Table[FromDigits /@ Select[Tuples[Range@ 3, n], And[Times @@ Boole@ MapIndexed[#1 <= First@ #2 &, #] > 0, Max@ Differences@ # <= 1] &], {n, 5}] // Flatten (* _Michael De Vlieger_, Dec 18 2016 *)

%o (PARI) gen(n, len, mx) = if (len==0, print1 (n ", "), for (d=1, min(mx+1, 3), gen(10*n + d, len-1, max(mx, d))))

%o for (len=1, 5, gen(0, len, 0)) \\ _Rémy Sigrist_, Dec 18 2016

%Y Cf. A278984, A007051.

%Y Similar to but different from A071159.

%K nonn,base

%O 1,2

%A _N. J. A. Sloane_, Dec 05 2016