login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A111277 Number of permutations avoiding the patterns {2413,4213,2431,4231,4321}; also number of permutations avoiding the patterns {3142,3412,3421,4312,4321}; number of weak sorting class based on 2413 or 3142. 3
1, 1, 2, 6, 19, 59, 180, 544, 1637, 4917, 14758, 44282, 132855, 398575, 1195736, 3587220, 10761673, 32285033, 96855114, 290565358, 871696091, 2615088291, 7845264892, 23535794696, 70607384109, 211822152349, 635466457070 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

a(n) = number of permutation tableaux of size n (A000142) for which each row is constant (all 1's, all 0's, or empty). For example, a(4)=19 counts all 4! permutation tableaux of size 4 except the following five: {{0, 1}, {1}}, {{1, 1}, {0, 1}}, {{0, 1}, {1, 1}}, {{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}. - David Callan, Oct 06 2006

a(n) = number of distinct excedance specifications taken over all permutations on [n]. The excedance specification for a permutation (p_1, p_2, ..., p_n) is the sequence (a_1, a_2, ..., a_n) defined by a_i = 1, 0, or -1 according as p_i is greater than, equal to, or less than i. If all permutations with a given excedance specification are arranged in lex (dictionary) order, then the first--and only the first--avoids the pattern set {3142,3412,3421,4312,4321}. - David Callan, Jul 25 2008

a(n) = number of (-1,0,1)-sequences of length n such that the first nonzero entry is 1 and the last nonzero entry is -1 because these sequences are the valid excedance specifications. Example: a(3)=6 counts (1,1,-1), (1,0,-1), (1,-1,0), (1,-1,-1), (0,1,-1), (0,0,0). - David Callan, Jul 25 2008

Inverse binomial transformation leads to 0,1,0,3,3,9,... (offset 0), essentially to A062510. - R. J. Mathar, Jun 25 2011

A128308 is defined as A007318 * A128307; since A007318 is the Riordan array (1/(1-x), x/(1-x)) and A128307 is the Riordan array ((1-x)^2/(1-2x), x), the first column of A128308 has g.f. (1-2x)^2/((1-3x)(1-x)^2), which coincides with the g.f. of this sequence. - Peter J. Taylor, Jul 24 2014

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000 (corrected by Ray Chandler, Jan 19 2019)

M. Albert, R. Aldred, M. Atkinson, C. Handley, D. Holton, D. McCaughan and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb. 12 (2005) R31

Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.

Index entries for linear recurrences with constant coefficients, signature (5,-7,3).

FORMULA

a(n) = (3^n-2*n+3)/4.

a(n) = +5*a(n-1) -7*a(n-2) +3*a(n-3). - R. J. Mathar, Jun 25 2011

a(n+1) = sum of row 1 terms of M^n, an infinite bidiagonal matrix with all 1's in the superdiagonal and (1,3,0,0,0,...) in the main diagonal, and the rest zeros. Example: a(5) = 59 = (sum of row 1 terms of M^4) = (1 + 40 + 13 + 4 + 1). - Gary W. Adamson, Jun 23 2011

G.f.: (1-2*x)^2/((1-3*x)*(1-x)^2). - R. J. Mathar, Jun 25 2011

MAPLE

A111277 := proc(n) (3^n-2*n+3)/4 ; end proc:

seq(A111277(n), n=1..30) ; # R. J. Mathar, Jun 25 2011

MATHEMATICA

Table[(3^n - 2n + 3)/4, {n, 26}] (* Robert G. Wilson v *)

PROG

(MAGMA) [(3^n-2*n+3)/4: n in [1..30]]; // Vincenzo Librandi, Jun 24 2011

CROSSREFS

First column of A128308.

Sequence in context: A328658 A067675 A037512 * A014346 A183188 A118364

Adjacent sequences:  A111274 A111275 A111276 * A111278 A111279 A111280

KEYWORD

nonn,easy

AUTHOR

Len Smiley, Nov 01 2005

EXTENSIONS

a(0) and crossref to A128308 added by Peter J. Taylor, Jul 23 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 8 01:57 EDT 2020. Contains 333312 sequences. (Running on oeis4.)