A203641 -id:A203641 - 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).

A203647 T(n,k) = number of arrays of n 0..k integers with new values introduced in order 0..k but otherwise unconstrained. Array read by antidiagonals.

Original entry on oeis.org

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

Offset: 1

R. H. Hardin, Jan 04 2012

Table starts
....1.....1......1......1......1......1......1......1......1......1......1
....2.....2......2......2......2......2......2......2......2......2......2
....4.....5......5......5......5......5......5......5......5......5......5
....8....14.....15.....15.....15.....15.....15.....15.....15.....15.....15
...16....41.....51.....52.....52.....52.....52.....52.....52.....52.....52
...32...122....187....202....203....203....203....203....203....203....203
...64...365....715....855....876....877....877....877....877....877....877
..128..1094...2795...3845...4111...4139...4140...4140...4140...4140...4140
..256..3281..11051..18002..20648..21110..21146..21147..21147..21147..21147
..512..9842..43947..86472.109299.115179.115929.115974.115975.115975.115975
.1024.29525.175275.422005.601492.665479.677359.678514.678569.678570.678570
Lower left triangular part seems to be A102661. - R. J. Mathar, Nov 29 2015

			Some solutions for n=7, k=5:
..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0
..0....0....1....1....1....1....0....0....1....1....1....1....1....1....1....1
..1....0....2....1....2....2....1....1....2....2....2....2....1....2....1....2
..0....1....1....0....3....3....2....2....1....3....1....1....1....0....0....2
..0....0....3....1....0....4....3....0....2....3....1....1....1....0....2....1
..2....2....4....2....2....0....4....2....0....2....2....3....2....3....2....0
..1....3....1....0....2....5....0....0....0....0....0....2....2....1....1....1

R. H. Hardin, Table of n, a(n) for n = 1..10011

Column 1 is A000079(n-1).
Column 2 is A007051(n-1).
Column 3 is A007581(n-1).
Column 4 is A056272.
Column 5 is A056273.
Column 6 is A099262.
Column 7 is A099263.
Column 8 is A164863.
Column 9 is A164864.
Column 10 is A203641.
Column 11 is A203642.
Column 12 is A203643.
Column 13 is A203644.
Column 14 is A203645.
Column 15 is A203646.
Diagonal is A000110.

T:= proc(n,k) option remember;  if k = 1 then 2^(n-1)
else 1 + add(binomial(n-1,j-1)*procname(n-j,k-1),j=1..n-1)
fi
end proc:
seq(seq(T(k,m-k),k=1..m-1),m=2..10); # Robert Israel, May 20 2016

T[n_, k_] := Sum[StirlingS2[n, j], {j, 1, k+1}]; Table[T[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 31 2017, after Andrew Howroyd *)

T(n,k) = Sum_{j = 1..k+1} Stirling2(n,j). - Andrew Howroyd, Mar 19 2017
T(n,k) = A278984(k+1, n). - Andrew Howroyd, Mar 19 2017
Empirical for column k:
k=1: a(n) = 2*a(n-1)
k=2: a(n) = 4*a(n-1) -3*a(n-2)
k=3: a(n) = 7*a(n-1) -14*a(n-2) +8*a(n-3)
k=4: a(n) = 11*a(n-1) -41*a(n-2) +61*a(n-3) -30*a(n-4)
k=5: a(n) = 16*a(n-1) -95*a(n-2) +260*a(n-3) -324*a(n-4) +144*a(n-5)
k=6: a(n) = 22*a(n-1) -190*a(n-2) +820*a(n-3) -1849*a(n-4) +2038*a(n-5) -840*a(n-6)
k=7: a(n) = 29*a(n-1) -343*a(n-2) +2135*a(n-3) -7504*a(n-4) +14756*a(n-5) -14832*a(n-6) +5760*a(n-7)
k=8: a(n) = 37*a(n-1) -574*a(n-2) +4858*a(n-3) -24409*a(n-4) +74053*a(n-5) -131256*a(n-6) +122652*a(n-7) -45360*a(n-8)
k=9: a(n) = 46*a(n-1) -906*a(n-2) +9996*a(n-3) -67809*a(n-4) +291774*a(n-5) -790964*a(n-6) +1290824*a(n-7) -1136160*a(n-8) +403200*a(n-9)
k=10: 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)
k=11: 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)
k=12: 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)
k=13: 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)
k=14: 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)
k=15: 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)
From Robert Israel, May 20 2016: (Start)
T(n,k) = 1 + Sum_{j=1..n-1} binomial(n-1,j-1)*T(n-j,k-1).
G.f. for columns g_k(z) satisfies g_k(z) = (z/(1-z))*(1+ g_{k-1}(z/(1-z))) with g_1(z) = z/(1-2z).
Thus g_k is a rational function: it has a simple pole at z=1/j for 1<=j<=k+1 except j=k, and it has a finite limit at infinity (so the degree of the numerator is k).  This implies that column k satisfies the recurrences listed above, whose coefficients correspond to the expansion of (z-1/(k+1))* Product_{j=1..k-1}(z - 1/j).
(End)

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

A203647 T(n,k) = number of arrays of n 0..k integers with new values introduced in order 0..k but otherwise unconstrained. Array read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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