A278986 Array read by antidiagonals downwards: T(b,n) = number of words of length n over an alphabet of size b that are in standard order and which have the property that at least one letter is repeated.

0, 1, 0, 1, 1, 0, 1, 4, 1, 0, 1, 8, 4, 1, 0, 1, 16, 14, 4, 1, 0, 1, 32, 41, 14, 4, 1, 0, 1, 64, 122, 51, 14, 4, 1, 0, 1, 128, 365, 187, 51, 14, 4, 1, 0, 1, 256, 1094, 715, 202, 51, 14, 4, 1, 0, 1, 512, 3281, 2795, 855, 202, 51, 14, 4, 1, 0, 1, 1024, 9842, 11051, 3845, 876, 202, 51, 14, 4, 1

Offset

1,8

Comments

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.

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.

Links

Table of n, a(n) for n=1..77.

Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

Formula

The number of words of length n over an alphabet of size b that are in standard order and in which at least one symbol is repeated is Sum_{j = 1..b} Stirling2(n,j), except we must subtract 1 if and only if n <= b.

So this array is obtained from the array in A278984 by subtracting 1 from the first b entries in row b, for b = 1,2,3,...

Example

The array begins:
0,.1,..1,...1,...1,...1,...1,....1..; b=1,
0,.1,..4,...8,..16,..32,..64,..128..; b=2,
0,.1,..4,..14,..41,.122,.365,.1094..; b=3,
0,.1,..4,..14,..51,.187,.715,.2795..; b=4,
0,.1,..4,..14,..51,.202,.855,.3845..; b=5,
0,.1,..4,..14,..51,.202,.876,.4111..; b=6,
...

Maple

with(combinat);
f2:=proc(L, b) local t1; i;
t1:=add(stirling2(L, i), i=1..b); if L <= b then t1:=t1-1; fi; t1; end;
Q2:=b->[seq(f2(L, b), L=1..20)];
for b from 1 to 6 do lprint(Q2(b)); od:

Crossrefs

See A278984 for a closely related array.

The words for b=3 are listed in A278985, except that the words 1, 12, and 123 must be omitted from that list.

The words for b=9 are listed in A273977.

Sequence in context: A332055 A073027 A370073 * A292159 A099793 A273895

Adjacent sequences: A278983 A278984 A278985 * A278987 A278988 A278989

Keyword

nonn,tabl

Author

Joerg Arndt and N. J. A. Sloane, Dec 05 2016

Status

approved