login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.

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[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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 01:05 EST 2020. Contains 330995 sequences. (Running on oeis4.)