

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 i1 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 nth moment about 0 of X, i.e., the expected value of X^n.  Geoffrey Critzer, Jun 23 2020


LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275
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 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,..14,..41,.122,.365,.1094..; b=3, A007051 (A278985)
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
...
The rows tend to A000110.


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[bn+1, n], {b, 1, 12}, {n, b, 1, 1}] // Flatten (* JeanFranç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, A203641A203646.
The limit of the rows is A000110, the Bell numbers.
See A278985 for the words arising in row b=3.
Cf. A203647, A137855 (essentially same table).
Sequence in context: A057728 A176463 A098050 * A111579 A144374 A144018
Adjacent sequences: A278981 A278982 A278983 * A278985 A278986 A278987


KEYWORD

nonn,tabl


AUTHOR

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


STATUS

approved



