|
| |
|
|
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
Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {1>2, 1>3, 4>3} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second and third elements, and the fourth element is larger than the third element. - Sergey Kitaev, Dec 09 2020
|
|
|
LINKS
|
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
|
|
|
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:
|
|
|
MATHEMATICA
|
|
|
|
PROG
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
