cp's OEIS Frontend

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.

%I A278986 #21 Dec 06 2016 20:43:46
%S A278986 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,
%T A278986 122,51,14,4,1,0,1,128,365,187,51,14,4,1,0,1,256,1094,715,202,51,14,4,
%U A278986 1,0,1,512,3281,2795,855,202,51,14,4,1,0,1,1024,9842,11051,3845,876,202,51,14,4,1
%N 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.
%C A278986 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 A278986 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.
%H A278986 Joerg Arndt and N. J. A. Sloane, <a href="/A278984/a278984.txt">Counting Words that are in "Standard Order"</a>
%F A278986 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.
%F A278986 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,...
%e A278986 The array begins:
%e A278986 0,.1,..1,...1,...1,...1,...1,....1..; b=1,
%e A278986 0,.1,..4,...8,..16,..32,..64,..128..; b=2,
%e A278986 0,.1,..4,..14,..41,.122,.365,.1094..; b=3,
%e A278986 0,.1,..4,..14,..51,.187,.715,.2795..; b=4,
%e A278986 0,.1,..4,..14,..51,.202,.855,.3845..; b=5,
%e A278986 0,.1,..4,..14,..51,.202,.876,.4111..; b=6,
%e A278986 ...
%p A278986 with(combinat);
%p A278986 f2:=proc(L,b) local t1;i;
%p A278986 t1:=add(stirling2(L,i),i=1..b); if L <= b then t1:=t1-1; fi; t1; end;
%p A278986 Q2:=b->[seq(f2(L,b), L=1..20)];
%p A278986 for b from 1 to 6 do lprint(Q2(b)); od:
%Y A278986 See A278984 for a closely related array.
%Y A278986 The words for b=3 are listed in A278985, except that the words 1, 12, and 123 must be omitted from that list.
%Y A278986 The words for b=9 are listed in A273977.
%K A278986 nonn,tabl
%O A278986 1,8
%A A278986 _Joerg Arndt_ and _N. J. A. Sloane_, Dec 05 2016