A245667 -id:A245667 - cp's OEIS frontend

A047874 Triangle of numbers T(n,k) = number of permutations of (1,2,...,n) with longest increasing subsequence of length k (1<=k<=n).

1, 1, 1, 1, 4, 1, 1, 13, 9, 1, 1, 41, 61, 16, 1, 1, 131, 381, 181, 25, 1, 1, 428, 2332, 1821, 421, 36, 1, 1, 1429, 14337, 17557, 6105, 841, 49, 1, 1, 4861, 89497, 167449, 83029, 16465, 1513, 64, 1, 1, 16795, 569794, 1604098, 1100902, 296326, 38281, 2521, 81, 1

Offset: 1

Eric Rains (rains(AT)caltech.edu)

Mirror image of triangle in A126065.
T(n,m) is also the sum of squares of n!/(product of hook lengths), summed over the partitions of n in exactly m parts (Robinson-Schensted correspondence). - Wouter Meeussen, Sep 16 2010
Table I "Distribution of L_n" on p. 98 of the Pilpel reference. - Joerg Arndt, Apr 13 2013
In general, for column k is a(n) ~ product(j!, j=0..k-1) * k^(2*n+k^2/2) / (2^((k-1)*(k+2)/2) * Pi^((k-1)/2) * n^((k^2-1)/2)) (result due to Regev) . - Vaclav Kotesovec, Mar 18 2014

			T(3,2) = 4 because 132, 213, 231, 312 have longest increasing subsequences of length 2.
Triangle T(n,k) begins:
  1;
  1,   1;
  1,   4,    1;
  1,  13,    9,    1;
  1,  41,   61,   16,   1;
  1, 131,  381,  181,  25,  1;
  1, 428, 2332, 1821, 421, 36,  1;
  ...

Leonid Petrov, Rows n = 1..120, flattened (first 60 rows from Alois P. Heinz)
P. Diaconis, Group Representations in Probability and Statistics, IMS, 1988; see p. 112.
FindStat - Combinatorial Statistic Finder, The length of the longest increasing subsequence of the permutation.
Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257-285.
J. M. Hammersley, A few seedings of research, in Proc. Sixth Berkeley Sympos. Math. Stat. and Prob., ed. L. M. le Cam et al., Univ. Calif. Press, 1972, Vol. I, pp. 345-394.
Guo-Niu Han, A promenade in the garden of hook length formulas, Slides, 61st SLC Curia, Portugal - September 22, 2008. [From _Wouter Meeussen_, Sep 16 2010]
J. Hunt and T. Szymanski, A fast algorithm for computing longest common subsequences, Commun. ACM, 20 (1977), 350-353.
E. Irurozki, B. Calvo, and J. A. Lozano, Sampling and learning the Mallows model under the Ulam distance, Technical Report, 2014.
S. Pilpel, Descending subsequences of random permutations, J. Combin. Theory, A 53 (1990), 96-116.
A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. in Math. 41 (1981), 115-136.
C. Schensted, Longest increasing and decreasing subsequences, Canadian J. Math. 13 (1961), 179-191.
Richard P. Stanley, Increasing and Decreasing Subsequences of Permutations and Their Variants, arXiv:math/0512035 [math.CO], 2005.
Wikipedia, Longest increasing subsequence problem

Cf. A047887 and A047888.
Columns k=1-10 give: A000012, A001453, A001454, A001455, A001456, A001457, A001458, A239432, A245665, A245666.
Row sums give A000142.
Cf. A047884. - Wouter Meeussen, Sep 16 2010
Cf. A224652 (Table II "Distribution of F_n" on p. 99 of the Pilpel reference).
Cf. A245667.
T(2n,n) gives A267433.
Cf. A003316.

h:= proc(l) local n; n:= nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
      +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n) end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
                add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
T:= n-> seq(g(n-k, min(n-k, k), [k]), k=1..n):
seq(T(n), n=1..12);  # Alois P. Heinz, Jul 05 2012

Table[Total[NumberOfTableaux[#]^2&/@ IntegerPartitions[n,{k}]],{n,7},{k,n}] (* Wouter Meeussen, Sep 16 2010, revised Nov 19 2013 *)
h[l_List] := Module[{n = Length[l]}, Total[l]!/Product[Product[1+l[[i]]-j+Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]]; g[n_, i_, l_List] := If[n == 0 || i == 1, h[Join[l, Array[1&, n]]]^2, If[i<1, 0, Sum[g[n-i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; T[n_] := Table[g[n-k, Min[n-k, k], {k}], {k, 1, n}]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Mar 06 2014, after Alois P. Heinz *)

Sum_{k=1..n} k * T(n,k) = A003316(n). - Alois P. Heinz, Nov 04 2018

A239295 Number of words of length n over the alphabet {0,...,n-1} that avoid the pattern 123.

Original entry on oeis.org

1, 1, 4, 26, 210, 1897, 18368, 186636, 1965414, 21277685, 235493544, 2653779856, 30357956720, 351719984280, 4119552129280, 48708104589368, 580682799531822, 6973356315752445, 84286657672243880, 1024694111031383100, 12522664914160322460, 153762682439070435390

Offset: 0

Chad Brewbaker, Mar 14 2014

nonn

			a(0) = [].
a(1) = [0].
a(2) = [0,0], [0,1], [1,0], [1,1].
a(3) = [0,0,0], [0,0,1], [0,0,2], [0,1,0], [0,1,1], [0,2,0], [0,2,1], [0,2,2], [1,0,0], [1,0,1], [1,0,2], [1,1,0], [1,1,1], [1,1,2], [1,2,0], [1,2,1], [1,2,2], [2,0,0], [2,0,1], [2,0,2], [2,1,0], [2,1,1], [2,1,2], [2,2,0], [2,2,1], [2,2,2].

Alois P. Heinz, Table of n, a(n) for n = 0..800

Cf. A000108 (the permutation analog for 123-avoiding), A000312, A245667.

a:= proc(n) option remember; `if`(n<3, [1, 1, 4][n+1],
      ((7324*n^4-36350*n^3+58408*n^2-36126*n+8352) *a(n-1)
      -3*(n-3)*(2083*n^3-5374*n^2+2979*n+816) *a(n-2)
      -63*(n-3)*(n-4)*(3*n-7)*(3*n-8) *a(n-3)) /
      (4*n*(n-2)*(n+1)*(127*n-261)))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Mar 15 2014

b[n_, l_] := b[n, l] = If[n == 0, 1, Sum[b[n-1, Table[Min[l[[j]], If[j == 1 || l[[j-1]] < i, i, l[[j]]]], {j, 1, Length[l]}]], {i, 1, l[[-1]]}]];
A[n_, k_] := A[n, k] = If[k == 0, If[n == 0, 1, 0], b[n, Array[n&, k]]];
T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k-1]];
a[n_] := Sum[T[n, k], {k, 0, 2}];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 29 2017, after Alois P. Heinz (cf. A245667) *)

a(n) = Sum_{k=0..2} A245667(n,k).

a(n) ~ 3^(3*n-1/2) / (5^(3/2) * Pi * 2^(n-3) * n^2). - Vaclav Kotesovec, Sep 11 2014

a(8)-a(11) from Giovanni Resta, Mar 14 2014

a(12)-a(21) from Alois P. Heinz, Mar 15 2014

A239299 Number of words of length n over the alphabet {0,...,n-1} that are 1234-avoiding.

Original entry on oeis.org

1, 1, 4, 27, 255, 3028, 41979, 647790, 10803237, 191122140, 3542732908, 68213661464, 1355643940248, 27673150807344, 578051855658450, 12318499151821116, 267156147212406393, 5884501351433388108, 131418738987996420708, 2971588663914996425000

Offset: 0

Chad Brewbaker, Mar 14 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..500
Alois P. Heinz, Maple program for A239299

The permutation analog is A005802.

Cf. A000312, A245667.

# for an efficient program see link above.
# for initial terms only:
b:= proc(n, s, u, t) option remember; `if`(n=0, 1,
      add(b(n-1, min(s, i), min(u, `if`(s b(n, n+1$3):
seq(a(n), n=0..20); # Alois P. Heinz, Mar 18 2014

b[n_, s_, u_, t_] := b[n, s, u, t] = If[n == 0, 1,
    Sum[b[n - 1, Min[s, i], Min[u, If[s < i, i, u]],
    Min[t, If[u < i, i + 1, t]]], {i, 1, t - 1}]];
a[n_] := b[n, n+1, n+1, n+1];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 40}] (* Jean-François Alcover, Dec 21 2020, after Alois P. Heinz *)

Recurrence (of order 3): 9*(n-3)^2*(n-2)*n*(n+2)^2*(1057*n^7 - 19522*n^6 + 153671*n^5 - 668749*n^4 + 1738472*n^3 - 2700169*n^2 + 2319664*n - 849696)*a(n) = (n-3)*(327670*n^12 - 7739849*n^11 + 80785028*n^10 - 489037999*n^9 + 1890857973*n^8 - 4828424052*n^7 + 8060049557*n^6 - 8146857268*n^5 + 3520960348*n^4 + 1831667104*n^3 - 3220309536*n^2 + 1597874688*n - 295612416)*a(n-1) - (n-4)*(1633065*n^12 - 41573919*n^11 + 478203433*n^10 - 3285690086*n^9 + 15017055239*n^8 - 48092317343*n^7 + 110651362619*n^6 - 184276357364*n^5 + 220420044268*n^4 - 184591308504*n^3 + 102631197456*n^2 - 33947092224*n + 5033249280)*a(n-2) + 8*(n-5)*(n-4)^2*(2*n-5)*(4*n-11)*(4*n-9)*(1057*n^7 - 12123*n^6 + 58736*n^5 - 156229*n^4 + 246741*n^3 - 231170*n^2 + 118368*n - 25272)*a(n-3). - Vaclav Kotesovec, Mar 20 2014
a(n) ~ 2^(8*n-3/2) /  (7^4 * Pi^(3/2) * n^(9/2) * 3^(2*n-9)). - Vaclav Kotesovec, Mar 20 2014
a(n) = Sum_{k=0..3} A245667(n,k). - Alois P. Heinz, Jul 31 2014

a(8)-a(10) from Giovanni Resta, Mar 14 2014

a(11)-a(19) from Alois P. Heinz, Mar 17 2014

A268869 Number of sequences in {1,...,n}^n with longest increasing subsequence of length two.

Original entry on oeis.org

1, 16, 175, 1771, 17906, 184920, 1958979, 21253375, 235401166, 2653427140, 30356604642, 351714783980, 4119532070980, 48708027030608, 580682498991627, 6973355148949335, 84286653134676230, 1024694093358751200, 12522664845237058050, 153762682169941498170

Offset: 2

Alois P. Heinz, Feb 15 2016

			a(2) = 1: 12.
a(3) = 16: 112, 113, 121, 122, 131, 132, 133, 212, 213, 223, 231, 232, 233, 312, 313, 323.
a(4) = 175: 1112, 1113, 1114, 1121, ..., 4414, 4423, 4424, 4434.

Alois P. Heinz, Table of n, a(n) for n = 2..900

Column k=2 of A245667.

Cf. A001700, A088218, A239295.

a(n) = A239295(n) - A088218(n) = A239295(n) - A001700(n-1).

A268870 Number of sequences in {1,...,n}^n with longest increasing subsequence of length three.

Original entry on oeis.org

1, 45, 1131, 23611, 461154, 8837823, 169844455, 3307239364, 65559881608, 1325285983528, 27321430823064, 573932303529170, 12269791047231748, 266575464412874571, 5877527995117635663, 131334452330324176828, 2970563969803965041900, 67935408457473145627500

Offset: 3

Alois P. Heinz, Feb 15 2016

			a(3) = 1: 123.
a(4) = 45: 1123, 1124, 1134, 1213, 1214, 1223, 1224, 1231, 1232, 1233, 1241, 1242, 1243, 1244, 1314, 1323, 1324, 1334, 1341, 1342, 1343, 1344, 1423, 1424, 1434, 2123, 2124, 2134, 2234, 2314, 2324, 2334, 2341, 2342, 2343, 2344, 2434, 3123, 3124, 3134, 3234, 4123, 4124, 4134, 4234.

Alois P. Heinz, Table of n, a(n) for n = 3..700

Column k=3 of A245667.

Cf. A239295, A239299.

a(n) = A239299(n) - A239295(n).

A268871 Number of sequences in {1,...,n}^n with longest increasing subsequence of length four.

Original entry on oeis.org

1, 96, 4501, 161876, 5179791, 157279903, 4678809652, 138712471261, 4137680201304, 124857897038252, 3823102196348462, 118974270767513360, 3765555655525713427, 121224440332571253975, 3968401901135750428284, 132031213465208461376221, 4461459275271493097987384

Offset: 4

Alois P. Heinz, Feb 15 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..50

Column k=4 of A245667.

A268936 Number of sequences in {1,...,n}^n with longest increasing subsequence of length n-2.

Original entry on oeis.org

0, 0, 0, 10, 175, 1131, 4501, 13588, 34245, 75925, 152911, 285726, 502723, 841855, 1352625, 2098216, 3157801, 4629033, 6630715, 9305650, 12823671, 17384851, 23222893, 30608700, 39854125, 51315901, 65399751, 82564678, 103327435, 128267175, 158030281, 193335376

Offset: 0

Alois P. Heinz, Feb 16 2016

			a(3) = 10: 111, 211, 221, 222, 311, 321, 322, 331, 332, 333.
a(4) = 175: 1112, 1113, 1114, 1121, ..., 4414, 4423, 4424, 4434.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

A diagonal of A245667.

G.f.: x^3*(3*x^6-20*x^5+57*x^4-91*x^3+116*x^2+105*x+10)/(1-x)^7.

A275576 Sums of lengths of longest (strictly) increasing subsequences of all n^n length-n lists of integers from {1,2,...,n}.

Original entry on oeis.org

1, 5, 45, 524, 7450, 125992, 2472197, 55163096, 1379215566, 38203654070, 1161476316583, 38452206880034, 1376997068182450, 53036098532973584, 2186272797635061105, 96043562430904351024, 4479387734051244791950, 221051522602427094486042

Offset: 1

Jeffrey Shallit, Aug 02 2016

			For n = 2 there are 4 such sequences:  (1,1), (1,2), (2,1), and (2,2).
The corresponding lengths of longest (strictly) increasing subsequences of these is 1, 2, 1, 1, so a(2) = 5.

Cf. A003316, which computes the same thing for permutations.
Cf. A275577, which computes the same thing for not necessarily strictly increasing subsequences.
Cf. A245667.

a(n) = Sum_{k=1..n} k * A245667(n,k). - Alois P. Heinz, Nov 02 2018

a(8)-a(18) from Alois P. Heinz, Nov 02 2018

A268872 Number of sequences in {1,...,n}^n with longest increasing subsequence of length five.

Original entry on oeis.org

1, 175, 13588, 759501, 36156355, 1583828620, 66491165533, 2737728212583, 112090372848832, 4602189131156358, 190484294908691424, 7973928826104231407, 338278741165301388903, 14560566988020799890812, 636291650516785368941061, 28237066917878338656194296

Offset: 5

Alois P. Heinz, Feb 15 2016

nonn

Column k=5 of A245667.

A268873 Number of sequences in {1,...,n}^n with longest increasing subsequence of length six.

Original entry on oeis.org

1, 288, 34245, 2785525, 185896876, 11100594319, 621893381187, 33618910532156, 1784707075033338, 94099086097525864, 4964605274558064279, 263409209192451795339, 14101758253290661842556, 763439165118083467069181, 41856403816213923164705832

Offset: 6

Alois P. Heinz, Feb 15 2016

nonn

Column k=6 of A245667.

cp's OEIS Frontend

A047874 Triangle of numbers T(n,k) = number of permutations of (1,2,...,n) with longest increasing subsequence of length k (1<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A239295 Number of words of length n over the alphabet {0,...,n-1} that avoid the pattern 123.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A239299 Number of words of length n over the alphabet {0,...,n-1} that are 1234-avoiding.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A268869 Number of sequences in {1,...,n}^n with longest increasing subsequence of length two.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A268870 Number of sequences in {1,...,n}^n with longest increasing subsequence of length three.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A268871 Number of sequences in {1,...,n}^n with longest increasing subsequence of length four.

Views

Author

Keywords

Links

Crossrefs

A268936 Number of sequences in {1,...,n}^n with longest increasing subsequence of length n-2.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A275576 Sums of lengths of longest (strictly) increasing subsequences of all n^n length-n lists of integers from {1,2,...,n}.

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

A268872 Number of sequences in {1,...,n}^n with longest increasing subsequence of length five.

Views

Author

Keywords

Crossrefs

A268873 Number of sequences in {1,...,n}^n with longest increasing subsequence of length six.