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

Author

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

Keywords

• nonn
• tabl

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.

Examples

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

Links

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

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.

Programs

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:

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