|
%I #54 Sep 08 2022 08:45:21
%S 1,1,2,6,19,59,180,544,1637,4917,14758,44282,132855,398575,1195736,
%T 3587220,10761673,32285033,96855114,290565358,871696091,2615088291,
%U 7845264892,23535794696,70607384109,211822152349,635466457070
%N 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.
%C 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
%C 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
%C 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
%C Inverse binomial transformation leads to 0,1,0,3,3,9,... (offset 0), essentially to A062510. - _R. J. Mathar_, Jun 25 2011
%C 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
%C 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
%H Vincenzo Librandi, <a href="/A111277/b111277.txt">Table of n, a(n) for n = 0..1000</a> (corrected by Ray Chandler, Jan 19 2019)
%H M. Albert, R. Aldred, M. Atkinson, C. Handley, D. Holton, D. McCaughan and H. van Ditmarsch, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r31">Sorting Classes</a>, Elec. J. of Comb. 12 (2005) R31
%H Alice L. L. Gao, Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.
%H Alice L. L. Gao, Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
%H Sergey Kitaev and Artem Pyatkin, <a href="https://arxiv.org/abs/2204.08936">On permutations avoiding partially ordered patterns defined by bipartite graphs</a>, arXiv:2204.08936 [math.CO], 2022.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5,-7,3).
%F a(n) = (3^n-2*n+3)/4.
%F a(n) = +5*a(n-1) -7*a(n-2) +3*a(n-3). - _R. J. Mathar_, Jun 25 2011
%F 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
%F G.f.: (1-2*x)^2/((1-3*x)*(1-x)^2). - _R. J. Mathar_, Jun 25 2011
%p A111277 := proc(n) (3^n-2*n+3)/4 ; end proc:
%p seq(A111277(n),n=0..30) ; # _R. J. Mathar_, Jun 25 2011
%t Table[(3^n - 2n + 3)/4, {n, 26}] (* _Robert G. Wilson v_ *)
%o (Magma) [(3^n-2*n+3)/4: n in [1..30]]; // _Vincenzo Librandi_, Jun 24 2011
%Y First column of A128308.
%K nonn,easy
%O 0,3
%A _Len Smiley_, Nov 01 2005
%E a(0) and crossref to A128308 added by _Peter J. Taylor_, Jul 23 2014
|
