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
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
KEYWORD
nonn,tabl
AUTHOR
Joerg Arndt and N. J. A. Sloane, Dec 05 2016
STATUS
approved