|
%I #34 Jul 01 2020 23:33:12
%S 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,
%T 122,51,15,5,2,1,1,128,365,187,52,15,5,2,1,1,256,1094,715,202,52,15,5,
%U 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
%N 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.
%C 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.
%C 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.
%C 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
%H Andrew Howroyd, <a href="/A278984/b278984.txt">Table of n, a(n) for n = 1..1275</a>
%H Joerg Arndt and N. J. A. Sloane, <a href="/A278984/a278984.txt">Counting Words that are in "Standard Order"</a>
%F 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).
%e The array begins:
%e 1,.1,..1,...1,...1,...1,...1,....1..; b=1, A000012
%e 1,.2,..4,...8,..16,..32,..64,..128..; b=2, A000079
%e 1,.2,..5,..14,..41,.122,.365,.1094..; b=3, A007051 (A278985)
%e 1,.2,..5,..15,..51,.187,.715,.2795..; b=4, A007581
%e 1,.2,..5,..15,..52,.202,.855,.3845..; b=5, A056272
%e 1,.2,..5,..15,..52,.203,.876,.4111..; b=6, A056273
%e ...
%e The rows tend to A000110.
%p with(combinat);
%p f1:=proc(L,b) local t1;i;
%p t1:=add(stirling2(L,i),i=1..b);
%p end:
%p Q1:=b->[seq(f1(L,b), L=1..20)]; # the rows of the array are Q1(1), Q1(2), Q1(3), ...
%t 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 *)
%Y Rows 1 through 16 of the array are: A000012, A000079, A007051 (or A124302), A007581 (or A124303), A056272, A056273, A099262, A099263, A164863, A164864, A203641-A203646.
%Y The limit of the rows is A000110, the Bell numbers.
%Y See A278985 for the words arising in row b=3.
%Y Cf. A203647, A137855 (essentially same table).
%K nonn,tabl
%O 1,5
%A _Joerg Arndt_ and _N. J. A. Sloane_, Dec 05 2016
|
