A203647 -id:A203647 - cp's OEIS frontend

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.

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

A203641 Number of arrays of n 0..10 integers with new values introduced in order 0..10 but otherwise unconstrained.

Original entry on oeis.org

1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213596, 27644358, 190895863, 1382847419, 10477213268, 82797679445, 680685836527, 5806124780384, 51245294979716, 466668627500968, 4371727233798927, 42000637216351225

Offset: 1

R. H. Hardin, Jan 04 2012

From Danny Rorabaugh, Mar 03 2015: (Start)
a(n) is also the number of ways of placing n labeled balls into 11 indistinguishable boxes.
a(n) is also the number of word structures of length n using an 11-ary alphabet.
(End)

R. H. Hardin, Table of n, a(n) for n = 1..210
Eric Weisstein's World of Mathematics, Set Partition.
Index entries for linear recurrences with constant coefficients, signature (56, -1365, 19020, -167223, 965328, -3686255, 9133180, -13926276, 11655216, -3991680).

Column k=10 of A203647.

Cf. A056272, A056273, A164863, A164864.

f:= n -> add(Stirling2(n,k),k=1..11):
map(f, [$1..100]); # Robert Israel, Aug 08 2016

a(n) = sum(k=1,11,stirling(n,k, 2)); \\ Michel Marcus, Mar 03 2015

Empirical: a(n) = 56*a(n-1) -1365*a(n-2) +19020*a(n-3) -167223*a(n-4) +965328*a(n-5) -3686255*a(n-6) +9133180*a(n-7) -13926276*a(n-8) +11655216*a(n-9) -3991680*a(n-10).
a(n) = Sum_{k=1..11} stirling2(n,k). - Danny Rorabaugh, Mar 03 2015
G.f.: Sum_{k=1..11} Product_{j=1..k} x/(1-j*x).  This confirms the empirical recurrence. - Robert Israel, Aug 08 2016

A137855 Triangle read by rows: T(n,k) = Sum_{j=1..n-k+1} Stirling2(k, j).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 5, 8, 1, 1, 2, 5, 14, 16, 1, 1, 2, 5, 15, 41, 32, 1, 1, 2, 5, 15, 51, 122, 64, 1, 1, 2, 5, 15, 52, 187, 365, 128, 1, 1, 2, 5, 15, 52, 202, 715, 1094, 256, 1, 1, 2, 5, 15, 52, 203, 855, 2795, 3281, 512, 1

Offset: 1

Gary W. Adamson, Feb 16 2008

Rows of the array tend to A000110 starting (1, 2, 5, 15, 52, ...).

			First few rows of the array:
  1, 1, 1,  1,  1, ...
  1, 2, 4,  8, 16, ...
  1, 2, 5, 14, 41, ...
  1, 2, 5, 14, 51, ...
  1, 2, 5, 14, 52, ...
  ...
First few rows of the triangle:
  1;
  1, 1;
  1, 2, 1;
  1, 2, 4,  1;
  1, 2, 5,  8,  1;
  1, 2, 5, 14, 16,   1;
  1, 2, 5, 15, 41,  32,   1;
  1, 2, 5, 15, 51, 122,  64,    1;
  1, 2, 5, 15, 52, 187, 365,  128,   1;
  1, 2, 5, 15, 52, 202, 715, 1094, 256, 1;
  ...

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

Row sums are A137856.

Cf. A008277, A000110, A203647, A278984.

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

Take antidiagonals of an array formed by A000012 * A008277(transform), where A000012 = (1; 1,1; 1,1,1; ...) and A008277 = the Stirling2 triangle.

Name changed by Andrew Howroyd, Aug 09 2018

A203646 Number of arrays of n 0..15 integers with new values introduced in order 0..15 but otherwise unconstrained.

Original entry on oeis.org

1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869803, 682076806005, 5832742192288, 51724157478221, 474869780161021, 4506714279517080, 44151953491540255

Offset: 1

R. H. Hardin, Jan 04 2012

nonn

Column 15 of A203647.

R. H. Hardin, Table of n, a(n) for n = 1..210
Index entries for linear recurrences with constant coefficients, signature (121, -6685, 223405, -5042947, 81308227, -965408015, 8576039615, -57312583328, 287212533608, -1066335473840, 2866534951280, -5367984964224, 6557974412544, -4622628648960, 1394852659200).

Cf. A203641.

Empirical: a(n) = 121*a(n-1) -6685*a(n-2) +223405*a(n-3) -5042947*a(n-4) +81308227*a(n-5) -965408015*a(n-6) +8576039615*a(n-7) -57312583328*a(n-8) +287212533608*a(n-9) -1066335473840*a(n-10) +2866534951280*a(n-11) -5367984964224*a(n-12) +6557974412544*a(n-13) -4622628648960*a(n-14) +1394852659200*a(n-15).

Empirical formula confirmed by extension of first ten columns, see A203641. - Ray Chandler, Jul 06 2024

A203642 Number of arrays of n 0..11 integers with new values introduced in order 0..11 but otherwise unconstrained.

Original entry on oeis.org

1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644436, 190899230, 1382953889, 10479970386, 82859701769, 681942165393, 5829591731684, 51656311613107, 473501669531146, 4480550589850064, 43672799989835155

Offset: 1

R. H. Hardin Jan 04 2012

nonn

Column 11 of A203647

R. H. Hardin, Table of n, a(n) for n = 1..210
Index entries for linear recurrences with constant coefficients, signature (67, -1980, 33990, -375573, 2795331, -14241590, 49412660, -113667576, 163671552, -131172480, 43545600).

Cf. A203641.

Empirical: a(n) = 67*a(n-1) -1980*a(n-2) +33990*a(n-3) -375573*a(n-4) +2795331*a(n-5) -14241590*a(n-6) +49412660*a(n-7) -113667576*a(n-8) +163671552*a(n-9) -131172480*a(n-10) +43545600*a(n-11)

Empirical formula confirmed by extension of first ten columns, see A203641. - Ray Chandler, Jul 06 2024

A203643 Number of arrays of n 0..12 integers with new values introduced in order 0..12 but otherwise unconstrained.

Original entry on oeis.org

1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899321, 1382958439, 10480136006, 82864611947, 682068020031, 5832484170844, 51717380273487, 474706578749477, 4503047451718545, 44074082550176545

Offset: 1

R. H. Hardin Jan 04 2012

nonn

Column 12 of A203647

R. H. Hardin, Table of n, a(n) for n = 1..210
Index entries for linear recurrences with constant coefficients, signature (79, -2783, 57695, -782133, 7284057, -47627789, 219409685, -703202566, 1519272964, -2082477528, 1606986720, -518918400).

Cf. A203641.

Empirical: a(n) = 79*a(n-1) -2783*a(n-2) +57695*a(n-3) -782133*a(n-4) +7284057*a(n-5) -47627789*a(n-6) +219409685*a(n-7) -703202566*a(n-8) +1519272964*a(n-9) -2082477528*a(n-10) +1606986720*a(n-11) -518918400*a(n-12)

Empirical formula confirmed by extension of first ten columns, see A203641. - Ray Chandler, Jul 06 2024

A203644 Number of arrays of n 0..13 integers with new values introduced in order 0..13 but otherwise unconstrained.

Original entry on oeis.org

1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958544, 10480142026, 82864861847, 682076428809, 5832727748374, 51723682798067, 474855882753977, 4506342616999876, 44142711725983660

Offset: 1

R. H. Hardin, Jan 04 2012

nonn

R. H. Hardin, Table of n, a(n) for n = 1..210
Index entries for linear recurrences with constant coefficients, signature (92, -3809, 93808, -1530243, 17419116, -141963107, 835933384, -3542188936, 10614910592, -21727767984, 28528276608, -21289201920, 6706022400).

Column 13 of A203647.

Cf. A203641.

Empirical: a(n) = 92*a(n-1) -3809*a(n-2) +93808*a(n-3) -1530243*a(n-4) +17419116*a(n-5) -141963107*a(n-6) +835933384*a(n-7) -3542188936*a(n-8) +10614910592*a(n-9) -21727767984*a(n-10) +28528276608*a(n-11) -21289201920*a(n-12) +6706022400*a(n-13).

Empirical formula confirmed by extension of first ten columns, see A203641. - Ray Chandler, Jul 06 2024

A203645 Number of arrays of n 0..14 integers with new values introduced in order 0..14 but otherwise unconstrained.

Original entry on oeis.org

1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142146, 82864869667, 682076796009, 5832741665152, 51724135127267, 474868970216557, 4506688232943076, 44151191130412991

Offset: 1

R. H. Hardin, Jan 04 2012

nonn

Column 14 of A203647.

R. H. Hardin, Table of n, a(n) for n = 1..210
Index entries for linear recurrences with constant coefficients, signature (106, -5096, 147056, -2840838, 38786748, -385081268, 2816490248, -15200266081, 59999485546, -169679309436, 331303013496, -418753514880, 303268406400, -93405312000).

Cf. A203641.

Empirical: a(n) = 106*a(n-1) -5096*a(n-2) +147056*a(n-3) -2840838*a(n-4) +38786748*a(n-5) -385081268*a(n-6) +2816490248*a(n-7) -15200266081*a(n-8) +59999485546*a(n-9) -169679309436*a(n-10) +331303013496*a(n-11) -418753514880*a(n-12) +303268406400*a(n-13) -93405312000*a(n-14).

Empirical formula confirmed by extension of first ten columns, see A203641. - Ray Chandler, Jul 06 2024

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A203641 Number of arrays of n 0..10 integers with new values introduced in order 0..10 but otherwise unconstrained.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

A137855 Triangle read by rows: T(n,k) = Sum_{j=1..n-k+1} Stirling2(k, j).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A203646 Number of arrays of n 0..15 integers with new values introduced in order 0..15 but otherwise unconstrained.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A203642 Number of arrays of n 0..11 integers with new values introduced in order 0..11 but otherwise unconstrained.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A203643 Number of arrays of n 0..12 integers with new values introduced in order 0..12 but otherwise unconstrained.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A203644 Number of arrays of n 0..13 integers with new values introduced in order 0..13 but otherwise unconstrained.

Views

Author

Keywords

Links

Crossrefs

Formula

A203645 Number of arrays of n 0..14 integers with new values introduced in order 0..14 but otherwise unconstrained.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula