A137855 -id:A137855 - cp's OEIS frontend

A137856 Row sums of triangle A137855.

1, 2, 4, 8, 17, 39, 97, 261, 756, 2343, 7722, 26917, 98789, 380360, 1531698, 6434385, 28130890, 127729730, 601196428, 2928369917, 14738842361, 76547694741, 409718539681, 2257459567236, 12789959138943, 74439150889080, 444647798089245, 2723583835351855

Offset: 1

Gary W. Adamson, Feb 18 2008

nonn

			a(5) = 17 = sum of row 5 terms of triangle A137855: (1 + 2 + 5 + 8 + 1).

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A137855.

Partial sums of A024427.

a(n)={sum(k=1, n, sum(j=1, n-k+1, stirling(k,j,2)))} \\ Andrew Howroyd, Aug 09 2018

a(n) = Sum_{k=1..n} Sum_{j=1..n-k+1} Stirling2(k, j). - Andrew Howroyd, Aug 09 2018

Terms a(12) and beyond from Andrew Howroyd, Aug 09 2018

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.

Original entry on oeis.org

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

Offset: 1

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

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

			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.

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"
Pengyu Liu and Jingzhou Na, Word Motifs and a Generalized Hamming Distance, Contemp. Math. (2025) Vol. 6, Issue 1, 1255-1264. See p. 1257.

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

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

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 *)

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

cp's OEIS Frontend

A137856 Row sums of triangle A137855.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions