| Displaying 1-8 of 8 results found.
page
1
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.
+10
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
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.
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
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, A0000121,.2,..4,...8,..16,..32,..64,..128..; b=2, A0000791,.2,..5,..15,..51,.187,.715,.2795..; b=4, A0075811,.2,..5,..15,..52,.202,.855,.3845..; b=5, A0562721,.2,..5,..15,..52,.203,.876,.4111..; b=6, A056273...
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.
Number of arrays of n 0..10 integers with new values introduced in order 0..10 but otherwise unconstrained.
+10
8
1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213596, 27644358, 190895863, 1382847419, 10477213268, 82797679445, 680685836527, 5806124780384, 51245294979716, 466668627500968, 4371727233798927, 42000637216351225
COMMENTS
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)
LINKS
Index entries for linear recurrences with constant coefficients, signature (56, -1365, 19020, -167223, 965328, -3686255, 9133180, -13926276, 11655216, -3991680).
FORMULA
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).
G.f.: Sum_{k=1..11} Product_{j=1..k} x/(1-j*x). This confirms the empirical recurrence. - Robert Israel, Aug 08 2016
MAPLE
f:= n -> add(Stirling2(n, k), k=1..11):
PROG
(PARI) a(n) = sum(k=1, 11, stirling(n, k, 2)); \\ Michel Marcus, Mar 03 2015
Triangle read by rows: T(n,k) = Sum_{j=1..n-k+1} Stirling2(k, j).
+10
3
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
COMMENTS
Rows of the array tend to A000110 starting (1, 2, 5, 15, 52, ...).
FORMULA
Take antidiagonals of an array formed by A000012 * A008277(transform), where A000012 = (1; 1,1; 1,1,1; ...) and A008277 = the Stirling2 triangle.
EXAMPLE
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;
...
PROG
(PARI) T(n, k)={sum(j=1, n-k+1, stirling(k, j, 2))} \\ Andrew Howroyd, Aug 09 2018
Number of arrays of n 0..15 integers with new values introduced in order 0..15 but otherwise unconstrained.
+10
3
1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869803, 682076806005, 5832742192288, 51724157478221, 474869780161021, 4506714279517080, 44151953491540255
LINKS
Index entries for linear recurrences with constant coefficients, signature (121, -6685, 223405, -5042947, 81308227, -965408015, 8576039615, -57312583328, 287212533608, -1066335473840, 2866534951280, -5367984964224, 6557974412544, -4622628648960, 1394852659200).
FORMULA
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
Number of arrays of n 0..11 integers with new values introduced in order 0..11 but otherwise unconstrained
+10
2
1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644436, 190899230, 1382953889, 10479970386, 82859701769, 681942165393, 5829591731684, 51656311613107, 473501669531146, 4480550589850064, 43672799989835155
LINKS
Index entries for linear recurrences with constant coefficients, signature (67, -1980, 33990, -375573, 2795331, -14241590, 49412660, -113667576, 163671552, -131172480, 43545600).
FORMULA
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
Number of arrays of n 0..12 integers with new values introduced in order 0..12 but otherwise unconstrained
+10
2
1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899321, 1382958439, 10480136006, 82864611947, 682068020031, 5832484170844, 51717380273487, 474706578749477, 4503047451718545, 44074082550176545
LINKS
Index entries for linear recurrences with constant coefficients, signature (79, -2783, 57695, -782133, 7284057, -47627789, 219409685, -703202566, 1519272964, -2082477528, 1606986720, -518918400).
FORMULA
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
Number of arrays of n 0..13 integers with new values introduced in order 0..13 but otherwise unconstrained.
+10
2
1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958544, 10480142026, 82864861847, 682076428809, 5832727748374, 51723682798067, 474855882753977, 4506342616999876, 44142711725983660
LINKS
Index entries for linear recurrences with constant coefficients, signature (92, -3809, 93808, -1530243, 17419116, -141963107, 835933384, -3542188936, 10614910592, -21727767984, 28528276608, -21289201920, 6706022400).
FORMULA
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
Number of arrays of n 0..14 integers with new values introduced in order 0..14 but otherwise unconstrained.
+10
2
1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142146, 82864869667, 682076796009, 5832741665152, 51724135127267, 474868970216557, 4506688232943076, 44151191130412991
LINKS
Index entries for linear recurrences with constant coefficients, signature (106, -5096, 147056, -2840838, 38786748, -385081268, 2816490248, -15200266081, 59999485546, -169679309436, 331303013496, -418753514880, 303268406400, -93405312000).
FORMULA
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
Search completed in 0.009 seconds
|