A005817 -id:A005817 - cp's OEIS frontend

A217324 Number of self-inverse permutations in S_n with longest increasing subsequence of length 4.

1, 4, 19, 69, 265, 929, 3356, 11626, 41117, 142206, 499836, 1734328, 6099193, 21282265, 75125770, 263906332, 936517637, 3313246237, 11827430209, 42139231729, 151339387003, 542857007499, 1961171657524, 7079621540798, 25720257983591, 93396276789196

Offset: 4

Alois P. Heinz, Sep 30 2012

Also the number of Young tableaux with n cells and 4 rows.

			a(4) = 1: 1234.
a(5) = 4: 12354, 12435, 13245, 21345.
a(6) = 19: 123654, 124365, 125436, 125634, 126453, 132465, 132546, 143256, 145236, 153426, 163452, 213465, 213546, 214356, 321456, 341256, 423156, 523416, 623451.

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

Column k=4 of A047884.

Cf. A001006, A005817, A182172.

a:= proc(n) option remember; `if`(n<4, 0, `if`(n=4, 1,
      ((2+n)*(30*n^5+199*n^4-374*n^3-1537*n^2-406*n+408)*a(n-1)
       -4*(n-1)*(n-2)*(120*n^4+46*n^3-471*n^2+371*n+204)*a(n-3)
       +(n-1)*(285*n^5-262*n^4-2755*n^3-1520*n^2+820*n-48)*a(n-2)
       -48*(n-1)*(n-3)*(3*n+7)*(5*n+4)*(n-2)^2*a(n-4))/
      ((n-4)*(5*n-1)*(3*n+4)*(n+4)*(n+3)*(n+2))))
    end:
seq(a(n), n=4..40);

h[l_] := With[{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_] := g[n, i, l] = If[n == 0 || i == 1, Function[p, h[p]*x^If[p == {}, 0, p[[1]]]][Join[l, Array[1&, n]]], Sum[g[n - i*j, i - 1, Join[l, Array[i&, j]]], {j, 0, n/i}]];
a[n_] := a[n] = Coefficient[g[n, n, {}], x, 4];
Table[Print[n, " ", a[n]]; a[n], {n, 4, 40}]
(* or: *)
MotzkinNumber = DifferenceRoot[Function[{y, n}, {(-3n-3)*y[n] + (-2n-5)*y[n+1] + (n+4)*y[n+2] == 0, y[0] == 1, y[1] == 1}]];
a[n_] := CatalanNumber[Quotient[n+1, 2]]*CatalanNumber[Quotient[n+2, 2]] - MotzkinNumber[n];
Table[a[n], {n, 4, 40}]
(* Jean-François Alcover, Oct 27 2021, after Alois P. Heinz in A047884 and second formula *)

a(n) = A182172(n,4)-A182172(n,3) = A005817(n)-A001006(n).

A217325 Number of self-inverse permutations in S_n with longest increasing subsequence of length 5.

Original entry on oeis.org

1, 5, 29, 127, 583, 2446, 10484, 43363, 181546, 748840, 3114308, 12878441, 53594473, 222761422, 930856456, 3893811380, 16365678160, 68937445765, 291656714515, 1237403762663, 5271285939671, 22524961082326, 96620152734652, 415768621923904, 1795530067804295

Offset: 5

Alois P. Heinz, Sep 30 2012

nonn

Also the number of Young tableaux with n cells and 5 rows.

			a(5) = 1: 12345.
a(6) = 5: 123465, 123546, 124356, 132456, 213456.

Alois P. Heinz, Table of n, a(n) for n = 5..1449 (terms 501..1000 from Seiichi Manyama)

Column k=5 of A047884.

Cf. A005817, A049401, A182172.

a:= proc(n) option remember; `if`(n<5, 0, `if`(n=5, 1,
     ((n+3)*(166075637*n^5+3319452867*n^4+10706068615*n^3-39910302747*n^2
       -182846631872*n-159926209260)*a(n-1) +(840221898216*n+133982123900
       -322021480097*n^3-83890810854*n^4+12016871251*n^5+3735622433*n^6
       +111397917411*n^2)*a(n-2)-(n-2)*(2142183361*n^5+66617759078*n^4
       -47640468971*n^3-611402096064*n^2+15449945364*n+452645243780)*a(n-3)
       -(n-2)*(n-3)*(33769818805*n^4-54918997862*n^3 -469629276839*n^2
       +789889969148*n +94438295920)*a(-4+n) -4*(n-2)*(n-3)*(-4+n)*
       (2060107324*n^3 -87569131518*n^2+293565842963*n -151080184425)*a(n-5)
       +240*(n-2)*(n-3)*(n-5)*(168175627*n-312397451)*(-4+n)^2*a(n-6))/
       (8*(13927136*n+37088781)*(n-5)*(n+6)*(n+4)*(n+3)^2)))
    end:
seq(a(n), n=5..40);

a(n) = A182172(n,5) - A182172(n,4) = A049401(n) - A005817(n).

A218265 Number of standard Young tableaux of n cells and height >= 5.

Original entry on oeis.org

1, 6, 36, 176, 856, 3952, 18272, 83524, 384463, 1777010, 8304636, 39254076, 188160268, 915651672, 4527595824, 22771294440, 116496899100, 606656445480, 3214574890480, 17337658462800, 95128543350576, 530998366724576, 3013524116661952, 17385349086129304

Offset: 5

Alois P. Heinz, Oct 24 2012

nonn

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= 5. a(5)=1: 12345; a(6)=6: 123456, 123465, 123546, 124356, 132456, 213456.

Alois P. Heinz, Table of n, a(n) for n = 5..800
Wikipedia, Involution (mathematics)
Wikipedia, Young tableau

Column k=5 of A182222.

a:= proc(n) option remember; `if`(n<13,
      [0$5, 1, 6, 36, 176, 856, 3952, 18272, 83524][n+1],
      ((n^4-2*n^3-179*n^2+256*n+804) *a(n-1)
      +(n-1)*(n^4+6*n^3-295*n^2+1108*n+100) *a(n-2)
      -4*(n-1)*(n-2)*(6*n^2-83*n+67) *a(n-3)
      -16*(n-11)*(n-1)*(n-3)*(n-2)^2 *a(n-4))/
      ((n-12)*(n-5)*(n+4)*(n+3)))
    end:
seq(a(n), n=5..30);

a(n) = A000085(n) - A005817(n) = A182172(n,n) - A182172(n,4).

A229068 Number of standard Young tableaux of n cells and height <= 12.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568503, 2390466, 10349340, 46204720, 211779200, 997134592, 4808141824, 23745792032, 119848119307, 618058083314, 3251373425356, 17442275104496, 95297400355320, 530067682582320, 2998503402985440

Offset: 0

Vaclav Kotesovec, Sep 12 2013

nonn

Conjecture: generally (for tableaux with height <= k), a(n) ~ k^n/Pi^(k/2) * (k/n)^(k*(k-1)/4) * Product_{j=1..k} Gamma(j/2); set k=12 for this sequence.

Vaclav Kotesovec and Alois P. Heinz, Table of n, a(n) for n = 0..400

Cf. A182172, A001405 (k=2), A001006 (k=3), A005817 (k=4), A049401 (k=5), A007579 (k=6), A007578 (k=7), A007580 (k=8), A212915 (k=9), A212916 (k=10), A229053 (k=11).

Column k=12 of A182172.

RecurrenceTable[{-147456 (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) (12+n) a[-6+n]-110592 (-4+n) (-3+n) (-2+n) (-1+n) (29+2 n) a[-5+n]+256 (-3+n) (-2+n) (-1+n) (121272+32786 n+2343 n^2+49 n^3) a[-4+n]+128 (-2+n) (-1+n) (438597+90321 n+5391 n^2+98 n^3) a[-3+n]-16 (-1+n) (8718630+5347213 n+804616 n^2+49754 n^3+1372 n^4+14 n^5) a[-2+n]-8 (27335490+10162354 n+1206473 n^2+63328 n^3+1533 n^4+14 n^5) a[-1+n]+(11+n) (20+n) (27+n) (32+n) (35+n) (36+n) a[n]==0, a[1]==1, a[2]==2, a[3]==4, a[4]==10, a[5]==26, a[6]==76}, a, {n, 20}]

Recurrence: (n+11)*(n+20)*(n+27)*(n+32)*(n+35)*(n+36)*a(n) = 8*(14*n^5 + 1533*n^4 + 63328*n^3 + 1206473*n^2 + 10162354*n + 27335490)*a(n-1) + 16*(n-1)*(14*n^5 + 1372*n^4 + 49754*n^3 + 804616*n^2 + 5347213*n + 8718630)*a(n-2) - 128*(n-2)*(n-1)*(98*n^3 + 5391*n^2 + 90321*n + 438597)*a(n-3) - 256*(n-3)*(n-2)*(n-1)*(49*n^3 + 2343*n^2 + 32786*n + 121272)*a(n-4) + 110592*(n-4)*(n-3)*(n-2)*(n-1)*(2*n + 29)*a(n-5) + 147456*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n+12)*a(n-6).

a(n) ~ 602791875/128 * 12^(n+33)/(Pi^3*n^33).

A302093 a(n) = floor(C(n/2)*C(n/2+1)), where C = Catalan numbers (A000108).

Original entry on oeis.org

1, 1, 2, 4, 10, 25, 70, 199, 588, 1784, 5544, 17569, 56628, 185202, 613470, 2054998, 6952660, 23732911, 81662152, 283026021, 987369656, 3465222945, 12228193432, 43369190282, 154532114800, 552998717472, 1986841476000, 7164993393905, 25928281261800, 94132464529902

Offset: 0

Vincenzo Librandi, Apr 11 2018

nonn

			k         a(k) is prime
2          2
7          199
11         17569
17         23732911
81         102313363987695596246576033222404783284068513
619        200823128294216578246...307006792344011246479 (366 digits)

Robert Israel, Table of n, a(n) for n = 0..1667

Cf. A000108, A005568 (bisection, even part), A005817.

a108:= n -> binomial(2*n,n)/(n+1):
seq(floor(a108(n/2)*a108(n/2+1)),n=0..40); # Robert Israel, May 12 2025

Table[Floor[CatalanNumber[n/2] CatalanNumber[n/2 + 1]], {n, 0, 35}]

A306295 Maximal number of coalescent histories among non-matching pairs consisting of a caterpillar gene tree and a caterpillar species tree with n+2 leaves.

Original entry on oeis.org

1, 3, 10, 32, 107, 359, 1234, 4274, 15032, 53242, 190588, 686272, 2490399, 9081375, 33312770, 122692130, 453999656, 1685601038, 6282014804, 23478897364, 88026769844, 330831420218, 1246635155180, 4707414286652, 17815452662152, 67546709440004, 256595322436760

Offset: 1

Noah A Rosenberg, Feb 04 2019

nonn

			For n=1, a non-matching caterpillar gene tree and species tree with n+2=3 leaves have only one coalescent history: all coalescences must take place above the root of the species tree. Hence, a(1)=1.

Z. M. Himwich and N. A. Rosenberg, Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees, arXiv:1901.04465 [q-bio.pE] (2019); Adv. Appl. Math. 113 (2020), 101939.

A000108 minus A005817.

b[n_] :=
Binomial[2 n - 2, n - 1]/
   n - (2 Floor[(n - 1)/2])!/(Floor[(n - 1)/2]! Floor[(n + 1)/
         2]!) (2 Ceiling[(n - 1)/2])!/(Ceiling[(n - 1)/
         2]! Ceiling[(n + 1)/2]!)
a[n_] := b[n+2]
Table[a[n], {n,1,30}]

a(n) = C(n+1) - C(floor((n+1)/2))*C(ceiling((n+1)/2)), where C(n) is the n-th term in the Catalan sequence A000108.

A339754 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k symmetric vertices (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 0, 2, 0, 2, 3, 0, 2, 6, 6, 0, 4, 12, 16, 10, 0, 8, 24, 40, 40, 20, 0, 20, 60, 104, 120, 90, 35, 0, 50, 150, 270, 350, 330, 210, 70, 0, 140, 420, 768, 1040, 1080, 840, 448, 126, 0, 392, 1176, 2184, 3080, 3468, 3108, 2128, 1008, 252

Offset: 1

Sergi Elizalde, Feb 12 2021

A symmetric vertex is a vertex in the first half of the path (not including the midpoint) that is a mirror image of a vertex in the second half, with respect to reflection along the vertical line through the midpoint of the path.

			For n=5 there are 4 Dyck paths with 2 symmetric vertices: uuuuddddud, uduuuudddd, uuudddudud, ududuuuddd.
Triangle begins:
  1;
  0,   2;
  0,   2,    3;
  0,   2,    6,    6;
  0,   4,   12,   16,   10;
  0,   8,   24,   40,   40,   20;
  0,  20,   60,  104,  120,   90,   35;
  0,  50,  150,  270,  350,  330,  210,   70;
  0, 140,  420,  768, 1040, 1080,  840,  448,  126;
  0, 392, 1176, 2184, 3080, 3468, 3108, 2128, 1008, 252;
  ...

Alois P. Heinz, Rows n = 1..200, flattened
Sergi Elizalde, The degree of symmetry of lattice paths, arXiv:2002.12874 [math.CO], 2020.
Sergi Elizalde, Measuring symmetry in lattice paths and partitions, Sem. Lothar. Combin. 84B.26, 12 pp (2020).

Row sums give A000108.
Main diagonal gives A001405.
Column k=2 gives 2*A005817(n-3) (for n>2).

b:= proc(x, y, v) option remember; expand(
      `if`(min(y, v, x-max(y, v))<0, 0, `if`(x=0, 1, (l-> add(add(
      `if`(y+i=v+j, z, 1)*b(x-1, y+i, v+j), i=l), j=l))([-1, 1]))))
    end:
g:= proc(n) option remember; add(b(n, j$2), j=0..n) end:
T:= (n, k)-> coeff(g(n), z, k):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Feb 12 2021

b[x_, y_, v_] := b[x, y, v] = Expand[If[Min[y, v, x - Max[y, v]] < 0, 0, If[x == 0, 1, Function[l, Sum[Sum[If[y + i == v + j, z, 1]*b[x - 1, y + i, v + j], {i, l}], {j, l}]][{-1, 1}]]]];
g[n_] := g[n] = Sum[b[n, j, j], {j, 0, n}];
T[n_, k_] := Coefficient[g[n], z, k];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Feb 13 2021, after Alois P. Heinz *)

A367495 Number of up-down permutations p of [n] such that for all ii+1 differs from the number of elements p(k) between p(i+1) and p(i+2) for k>i+2.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 11, 37, 147, 684, 3611, 21345, 139794, 1004293, 7853728, 66413562, 603851552, 5874507617, 60886603188, 669797203196, 7794401498440, 95662364870740, 1234953443995817, 16728449735374081, 237245379727483160, 3515622139828164851

Offset: 0

Alois P. Heinz, Nov 20 2023

nonn

			a(0) = 1: (), the empty permutation.
a(1) = 1: 1.
a(2) = 1: 12.
a(3) = 1: 132.
a(4) = 2: 1423, 3412.
a(5) = 4: 13254, 15243, 35142, 45132.
a(6) = 11: 132645, 142635, 162534, 164523, 264513, 341625, 361524, 364512, 461523, 561423, 563412.

Alois P. Heinz, Table of n, a(n) for n = 0..250
Wikipedia, Permutation

Cf. A000111, A005817.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      add(`if`(j=t, 0, b(o-1+j, u-j, j)), j=1..u))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..30);

A306422 Maximal number of coalescent histories among matching pairs of binary, rooted leaf-labeled gene trees and species trees with n leaves.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 138, 462, 1663

Offset: 1

Noah A Rosenberg, Feb 14 2019

Consider the unlabeled binary, rooted, leaf-labeled tree topologies with n leaves (A001190). For each unlabeled topology, choose an arbitrary labeling with distinct labels for the n leaves, and assign it to both gene tree and species tree. Compute the number of coalescent histories for that matching (gene tree, species tree) pair according to a recursion (Rosenberg 2007, Theorem 3.1). The sequence a(n) gives the largest number observed among all unlabeled topologies.

N. A. Rosenberg, Counting coalescent histories, J. Comput. Biol. 14 (2007), 360-377.

Cf. A001190.

A000108 and A005817 give the numbers of coalescent histories for specific families of matching gene trees and species trees.

cp's OEIS Frontend

A217324 Number of self-inverse permutations in S_n with longest increasing subsequence of length 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A217325 Number of self-inverse permutations in S_n with longest increasing subsequence of length 5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A218265 Number of standard Young tableaux of n cells and height >= 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A229068 Number of standard Young tableaux of n cells and height <= 12.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A302093 a(n) = floor(C(n/2)*C(n/2+1)), where C = Catalan numbers (A000108).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A306295 Maximal number of coalescent histories among non-matching pairs consisting of a caterpillar gene tree and a caterpillar species tree with n+2 leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A339754 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k symmetric vertices (n >= 1, 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A367495 Number of up-down permutations p of [n] such that for all ii+1 differs from the number of elements p(k) between p(i+1) and p(i+2) for k>i+2.

Views

Author

Keywords

Examples