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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 1
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, 122, 51, 14, 4, 1, 0, 1, 128, 365, 187, 51, 14, 4, 1, 0, 1, 256, 1094, 715, 202, 51, 14, 4, 1, 0, 1, 512, 3281, 2795, 855, 202, 51, 14, 4, 1, 0, 1, 1024, 9842, 11051, 3845, 876, 202, 51, 14, 4, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,8

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

Table of n, a(n) for n=1..77.

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

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

EXAMPLE

The array begins:

0,.1,..1,...1,...1,...1,...1,....1..; b=1,

0,.1,..4,...8,..16,..32,..64,..128..; b=2,

0,.1,..4,..14,..41,.122,.365,.1094..; b=3,

0,.1,..4,..14,..51,.187,.715,.2795..; b=4,

0,.1,..4,..14,..51,.202,.855,.3845..; b=5,

0,.1,..4,..14,..51,.202,.876,.4111..; b=6,

...

MAPLE

with(combinat);

f2:=proc(L, b) local t1; i;

t1:=add(stirling2(L, i), i=1..b); if L <= b then t1:=t1-1; fi; t1; end;

Q2:=b->[seq(f2(L, b), L=1..20)];

for b from 1 to 6 do lprint(Q2(b)); od:

CROSSREFS

See A278984 for a closely related array.

The words for b=3 are listed in A278985, except that the words 1, 12, and 123 must be omitted from that list.

The words for b=9 are listed in A273977.

Sequence in context: A318623 A332055 A073027 * A292159 A099793 A273895

Adjacent sequences:  A278983 A278984 A278985 * A278987 A278988 A278989

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 August 3 14:40 EDT 2021. Contains 346438 sequences. (Running on oeis4.)