|
|
A278984
|
|
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.
|
|
28
|
|
|
1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 8, 5, 2, 1, 1, 16, 14, 5, 2, 1, 1, 32, 41, 15, 5, 2, 1, 1, 64, 122, 51, 15, 5, 2, 1, 1, 128, 365, 187, 52, 15, 5, 2, 1, 1, 256, 1094, 715, 202, 52, 15, 5, 2, 1, 1, 512, 3281, 2795, 855, 203, 52, 15, 5, 2, 1, 1, 1024, 9842, 11051, 3845, 876, 203, 52, 15, 5, 2, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
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.
Let X be the random variable that assigns to each permutation of {1,2,...,b} (with uniform distribution) its number of fixed points (as in A008290). Then T(b,n) is the n-th moment about 0 of X, i.e., the expected value of X^n. - Geoffrey Critzer, Jun 23 2020
|
|
LINKS
|
|
|
FORMULA
|
The number of words of length n over an alphabet of size b that are in standard order is Sum_{j = 1..b} Stirling2(n,j).
|
|
EXAMPLE
|
The array begins:
1,.1,..1,...1,...1,...1,...1,....1..; b=1, A000012
1,.2,..4,...8,..16,..32,..64,..128..; b=2, A000079
1,.2,..5,..15,..51,.187,.715,.2795..; b=4, A007581
1,.2,..5,..15,..52,.202,.855,.3845..; b=5, A056272
1,.2,..5,..15,..52,.203,.876,.4111..; b=6, A056273
...
|
|
MAPLE
|
with(combinat);
f1:=proc(L, b) local t1; i;
t1:=add(stirling2(L, i), i=1..b);
end:
Q1:=b->[seq(f1(L, b), L=1..20)]; # the rows of the array are Q1(1), Q1(2), Q1(3), ...
|
|
MATHEMATICA
|
T[b_, n_] := Sum[StirlingS2[n, j], {j, 1, b}]; Table[T[b-n+1, n], {b, 1, 12}, {n, b, 1, -1}] // Flatten (* Jean-François Alcover, Feb 18 2017 *)
|
|
CROSSREFS
|
Rows 1 through 16 of the array are: A000012, A000079, A007051 (or A124302), A007581 (or A124303), A056272, A056273, A099262, A099263, A164863, A164864, A203641-A203646.
The limit of the rows is A000110, the Bell numbers.
See A278985 for the words arising in row b=3.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|