A005802 -id:A005802 - cp's OEIS frontend

A224318 Number of 2-vexillary permutations in S_n, that, permutations whose Stanley symmetric function has at most 2 terms or at most 2 Edelman-Greene tableaux.

Original entry on oeis.org

1, 1, 2, 6, 24, 118, 661, 4011, 25654, 170420, 1165697

Offset: 0

Sara Billey, Apr 03 2013

This family is characterized by a finite set of permutation patterns.

S. Billey and B. Pawlowski, Permutation Patterns, Stanley symmetric functions and generalized Specht modules, arXiv:1304.7870 [math.CO], 2013.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.

Cf. A005802, A223905, A224287.

a(0)=1 prepended by Alois P. Heinz, Jul 31 2019

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

A342646 Maximal number of 4213 patterns in a permutation of 1,2,...,n.

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 6, 13, 24, 40, 62, 96, 138, 192, 264, 354

Offset: 0

Peter Kagey, Mar 20 2021

Equivalently the maximal number of 1342, 2431, and 3124 patterns.

			For n = 7, a(7) = 13 because the permutation 7532146 has 13 instances of the pattern 4213, namely: 7536, 7526, 7516, 7546, 7324, 7326, 7314, 7316, 7214, 7216, 5324, 5314, and 5214.
Moreover, all other permutations in S_7 have 13 or fewer instances of this pattern.

M. H. Albert, M. D. Atkinson, C. C.Handley, D. A. Holton, and W. Stromquist, On packing densities of permutations, The Electronic Journal of Combinatorics, 9(1) (2002).
David Bevan, The permutation class Av(4213,2143), arXiv:1510.06328 [math.CO], 2015.
FindStat, St000750: The number of occurrences of the pattern 4213 in a permutation.
Rob Pratt, Greatest number of occurrences of the pattern 4213 in a permutation, Mathematics Stack Exchange.
Eric Weisstein's World of Mathematics, Permutation Pattern

Analogous for other patterns: A000292 (123), A000332 (1234), A061061 (132), A100354 (1432).

Cf. A005802, A022558

a(10)-a(12) from Rob Pratt

a(13)-a(15) from Bert Dobbelaere, Mar 26 2021

A224287 Number of multiplicity free permutations in S_n, i.e., permutations whose Stanley symmetric function is multiplicity free.

Original entry on oeis.org

1, 2, 6, 24, 120, 718, 4956, 38180, 319280, 2837959

Offset: 1

Sara Billey, Apr 04 2013

This family is conjectured to be characterized by a finite set of patterns up to S_11.

S. Billey and B. Pawlowski, Permutation Patterns, Stanley symmetric functions and generalized Specht modules, arXiv:1304.7870 [math.CO], 2013.

Cf. A005802, A223905, A224318.

A246513 a(n) = (4/n^2)( Sum_{k=0..n-1} kA246459(k) ).

Original entry on oeis.org

0, 7, 52, 378, 2832, 21785, 171036, 1364391, 11023264, 89985681, 740894700, 6144227430, 51267563280, 430045297695, 3623966778180, 30662599042530, 260367332354496, 2217928838577641, 18947382204700044, 162281586037920126

Offset: 1

Zhi-Wei Sun, Aug 28 2014

nonn

Conjecture: a(n) is always an integer.

Note: the formula for a(n) in terms of A005802 proves that a(n) is an integer, divisible by n-1. - Mark van Hoeij, Nov 06 2023

			a(2) = 7 since (4/2^2)*( Sum_{k=0..1} k*A246459(k) ) = A246459(1) = 7.

Zhi-Wei Sun, Table of n, a(n) for n = 1..150
Zhi-Wei Sun, Two new kinds of numbers and their arithmetic properties, arXiv:1408.5381 [math.NT], 2014-2018.

Cf. A246459, A246460.

h := n -> hypergeom([1/2, 1 - n, -n], [2, 2], 4):
a := n -> (n - 1) * ((n + 1)^2 * h(n) / n - n * h(n - 1)):
seq(simplify(a(n)), n = 1..20);  # Peter Luschny, Nov 06 2023
ogf := (((-54*x^4+18*x^3+30*x^2+6*x)*hypergeom([4/3, 4/3],[2],-27*x*(x-1)^2/(9*x-1)^2)+(-1701*x^3+783*x^2-111*x+5)*hypergeom([1/3, 1/3],[1],-27*x*(x-1)^2/(9*x-1)^2))/(1-9*x)^(8/3) - 5)/6;
series(ogf, x=0, 25); # Mark van Hoeij, Nov 12 2023

s[n_] := Sum[Binomial[n, k]^2 Binomial[2 k, k] (2 k + 1), {k, 0, n}]
a[n_] := Sum[k s[k], {k, 0, n-1}] 4/n^2
Table[a[n], {n, 1, 20}]

Recurrence: (n-2)*n^2*(2*n-7)*(4*n-5)*a(n) = (n-1)*(80*n^4 - 532*n^3 + 1126*n^2 - 893*n + 195)*a(n-1) - 9*(n-2)^2*(n-1)*(2*n-5)*(4*n-1)*a(n-2). - Vaclav Kotesovec, Aug 28 2014
a(n) ~ 3^(2*n+1/2) / (2*Pi*n). - Vaclav Kotesovec, Aug 28 2014
a(n) = (n-1) * ((n+1)^2 * A005802(n-1) - (n-1)*n * A005802(n-2)). - Mark van Hoeij, Nov 06 2023

A128079 a(n) = Sum_{k=0..n} A000984(k)*A001263(n+1,k+1), where A000984 is the central binomial coefficients and A001263 is the Narayana triangle.

Original entry on oeis.org

1, 3, 13, 69, 411, 2633, 17739, 124029, 892327, 6567285, 49235715, 374841195, 2890994445, 22545855855, 177524073021, 1409591810133, 11275693221519, 90792020672429, 735367765159347, 5987665336600683, 48987680485918149

Offset: 0

Paul D. Hanna, Feb 23 2007

nonn

			Illustrate a(n) = Sum_{k=0..n} A000984(k)*A001263(n+1,k+1) by:
a(2) = 1*(1) + 2*(3) + 6*(1) = 13;
a(3) = 1*(1) + 2*(6) + 6*(6) + 20*(1) = 69;
a(4) = 1*(1) + 2*(10)+ 6*(20)+ 20*(10)+ 70*(1) = 411.
The Narayana triangle A001263(n+1,k+1) = C(n,k)*C(n+1,k)/(k+1) begins:
1;
1, 1;
1, 3, 1;
1, 6, 6, 1;
1, 10, 20, 10, 1;
1, 15, 50, 50, 15, 1; ...

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A000984, A001263.

Table[Sum[Binomial[2*k,k]*Binomial[n,k]*Binomial[n+1,k]/(k+1),{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 20 2012 *)

{a(n)=sum(k=0,n,binomial(2*k,k)*binomial(n,k)*binomial(n+1,k)/(k+1))}

a(n) = Sum_{k=0..n} C(2k,k)*C(n,k)*C(n+1,k)/(k+1).
Recurrence: (n+1)*(n+2)*a(n) = (7*n^2+11*n+6)*a(n-1) + 3*(7*n^2-19*n+6)*a(n-2) - 27*(n-2)*(n-1)*a(n-3) . - Vaclav Kotesovec, Oct 20 2012
a(n) ~ 3^(2*n+7/2)/(8*Pi*n^2) . - Vaclav Kotesovec, Oct 20 2012
a(n) = ((n+3)^2*A005802(n+1)-(n-3)*(n+1)*A005802(n))/12. - Mark van Hoeij, Nov 12 2023

A135395 Number of walks of length 2n+3 from origin to (1,1,1) on a cubic lattice.

Original entry on oeis.org

6, 180, 5040, 143640, 4199580, 125621496, 3830266440, 118655943120, 3724872182460, 118248726796200, 3789926661961440, 122473276342326000, 3986235855826497000, 130561182081992667600, 4300094066688571550400

Offset: 0

Stefan Hollos (stefan(AT)exstrom.com), Dec 11 2007

a(n) is the number of walks of length 2*n+3 in a cubic lattice that begin at the origin and end at (1,1,1) using steps (1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1).

G. C. Greubel, Table of n, a(n) for n = 0..250
S. Hollos and R. Hollos, Lattice Paths and Walks.

Cf. A002896.

sq := (1-40*x+144*x^2)^(1/2); pb := 54*x*(108*x^2-27*x+1+(9*x-1)*sq);
H1 := hypergeom([7/6,1/3],[1],pb); H2 := hypergeom([1/6,4/3],[1],pb);
fa := (10-72*x-6*sq)^(1/2)/(432*x^3);
ogf := fa*((648*x^2-162*x+(54*x+3)*sq+5)*H1^2 - (648*x^2-342*x+(54*x+6)*sq+10)*H1*H2 - (180*x-5-3*sq)*H2^2);
series(ogf,x=0,20) # Mark van Hoeij, Nov 12 2011

Table[Binomial[2n+3,n]Sum[Binomial[n,k]Binomial[n+3,k+2]Binomial[2k+2,k+1],{k,0,n}],{n,0,20}] (* Harvey P. Dale, Mar 20 2012 *)

a(n) = binomial(2n+3,n) * sum( binomial(n,k) * binomial(n+3,k+2) * binomial(2k+2,k+1), k, 0, n )

a(n) = binomial(2*n+3,n) * sum(k=0,n, binomial(n,k) * binomial(n+3,k+2) * binomial(2*k+2,k+1)) \\ Charles R Greathouse IV, Oct 12 2016

a(n) = binomial(2n+3,n) * Sum_{k=0..n} (binomial(n,k) * binomial(n+3,k+2) * binomial(2k+2,k+1)).
G.f.: ((12*(4*x-1)*(36*x-1)/x)*g'' + (12*(288*x^2-60*x+1)/x^2)*g' + (72*(6*x-1)/x^2)*g)/288 where g is the o.g.f. of A002896. - Mark van Hoeij, Nov 12 2011
From Vaclav Kotesovec, Nov 27 2017: (Start)
Recurrence: n*(n+2)*(n+3)*a(n) = 4*(2*n + 3)*(5*n^2 + 10*n + 3)*a(n-1) - 36*n*(2*n + 1)*(2*n + 3)*a(n-2).
a(n) ~ 2^(2*n + 1) * 3^(2*n + 9/2) / (Pi*n)^(3/2). (End)
a(n) = (2*n+1)*(2*n+3)*binomial(2*n,n)*((n+3)*A005802(n+1)-(n+1)*A005802(n)). - Mark van Hoeij, Nov 12 2023

A212884 Number of permutations in S_n whose Rothe diagram can be rearranged to give the complement of a skew shape.

Original entry on oeis.org

1, 1, 2, 6, 24, 112, 572, 3116, 17871, 106959, 663526, 4243490, 27856087, 187029655, 1280660596, 8921737864, 63108620169, 452503644985, 3284213633684, 24098433889312, 178583179551488, 1335346240984360

Offset: 0

Joel B. Lewis, May 29 2012

nonn

Equivalent definitions:
(1) Permutations that have the form (a_1, a_2, ..., a_k, b_1, b_2, ..., b_(n - k)), where the subsequences (a_1, a_2, ..., a_k) and (b_1, b_2, ..., b_(n - k)) avoid the permutation pattern 2143 and a_i < b_j for all i, j.
(2) Permutations that avoid the nine permutation patterns 24153, 25143, 31524, 31542, 32514, 32541, 42153, 52143, and 214365.

Joel B. Lewis, Table of n, a(n) for n = 0..50
A. J. Klein, J. B. Lewis and A. H. Morales, Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams.
R. J. Mathar, D-finite recurrence

Ordinary g.f. is (1 - x)*V(x)^2 - V(x) + 1/(1 - x), where V(x) is the (ordinary) g.f. for A005802.

A223034 Number of 3-vexillary permutations in S_n, that is, permutations whose Stanley symmetric function has at most 3 terms or at most 3 Edelman-Greene tableaux.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 705, 4553, 30930, 216412, 1545469

Offset: 0

Sara Billey, Apr 04 2013

This family is characterized by a finite set of permutation patterns.

S. Billey and B. Pawlowski, Permutation Patterns, Stanley symmetric functions and generalized Specht modules, arXiv:1304.7870 [math.CO], 2013.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.

Cf. A005802, A223905, A224318, A224287.

a(0)=1 prepended by Alois P. Heinz, Jul 31 2019

A224249 Number of permutations in S_n containing exactly 2 increasing subsequences of length 4.

Original entry on oeis.org

0, 0, 0, 0, 4, 63, 665, 5982, 49748, 396642, 3089010, 23745117, 181282899, 1379847138, 10496697584, 79928658289, 609847716251, 4665446254886, 35801131210504, 275638351332190, 2129514056354378, 16509890253429971, 128449405928666831, 1002835093225654416, 7856166360951643384

Offset: 1

Brian Nakamura, Apr 02 2013

nonn

Andrew R. Conway and Anthony J. Guttmann, Counting occurrences of patterns in permutations, arXiv:2306.12682 [math.CO], 2023. See pp. 16, 24, 25.
B. Nakamura and D. Zeilberger, Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes
B. Nakamura and D. Zeilberger, Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes, Adv. in Appl. Math. 50 (2013), 356-366.

Cf. A005802, A217057.

# programs can be obtained from the Nakamura and Zeilberger link.

cp's OEIS Frontend

A224318 Number of 2-vexillary permutations in S_n, that, permutations whose Stanley symmetric function has at most 2 terms or at most 2 Edelman-Greene tableaux.

Views

Author

Keywords

Comments

Links

Crossrefs

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

A342646 Maximal number of 4213 patterns in a permutation of 1,2,...,n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A224287 Number of multiplicity free permutations in S_n, i.e., permutations whose Stanley symmetric function is multiplicity free.

Views

Author

Keywords

Comments

Links

Crossrefs

A246513 a(n) = (4/n^2)*( Sum_{k=0..n-1} k*A246459(k) ).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A128079 a(n) = Sum_{k=0..n} A000984(k)*A001263(n+1,k+1), where A000984 is the central binomial coefficients and A001263 is the Narayana triangle.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A135395 Number of walks of length 2n+3 from origin to (1,1,1) on a cubic lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

A212884 Number of permutations in S_n whose Rothe diagram can be rearranged to give the complement of a skew shape.

Views

Author

Keywords

Comments

Links

Formula

A223034 Number of 3-vexillary permutations in S_n, that is, permutations whose Stanley symmetric function has at most 3 terms or at most 3 Edelman-Greene tableaux.

A246513 a(n) = (4/n^2)( Sum_{k=0..n-1} kA246459(k) ).