A128308 -id:A128308 - cp's OEIS frontend

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.

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

Offset: 0

Len Smiley, Nov 01 2005

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

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.
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Sergey Kitaev and Artem Pyatkin, On permutations avoiding partially ordered patterns defined by bipartite graphs, arXiv:2204.08936 [math.CO], 2022.
Qipeng Kuang, Václav Kůla, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations, arXiv:2508.11515 [cs.LO], 2025. See p. 20.
Index entries for linear recurrences with constant coefficients, signature (5,-7,3).

First column of A128308.

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

A111277 := proc(n) (3^n-2*n+3)/4 ; end proc:
seq(A111277(n),n=0..30) ; # R. J. Mathar, Jun 25 2011

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

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

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

A128307 Triangle, (1, 0, 1, 2, 4, 8, ...) in every column.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 2, 1, 0, 1, 8, 4, 2, 1, 0, 1, 16, 8, 4, 2, 1, 0, 1, 32, 16, 8, 4, 2, 1, 0, 1, 64, 32, 16, 8, 4, 2, 1, 0, 1, 128, 64, 32, 16, 8, 4, 2, 1, 0, 1, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0, 1, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0

Offset: 1

Gary W. Adamson, Feb 25 2007

Row sums = (1, 1, 2, 4, 8, ...). A128308 = binomial transform of A128307.

Riordan array ( 1 + x^2/(1 - 2*x), x ). T(n,k) gives the number of compositions of n of the form 1 + 1 + ... + 1 + a_1 + ... + a_m beginning with k 1's and with a_1 > 1. See Shapiro, Section 5. An example is given below. - Peter Bala, Aug 18 2014

			First few rows of the triangle:
  1;
  0, 1;
  1, 0, 1;
  2, 1, 0, 1;
  4, 2, 1, 0, 1;
  8, 4, 2, 1, 0, 1;
  ...
From _Peter Bala_, Aug 18 2014: (Start)
Row 4: [4,2,1,0,1]
              Compositions                Number
k = 0     4, 3 + 1, 2 + 2, 2 + 1 + 1        4
k = 1     1 + 3, 1 + 2 + 1                  2
k = 2     1 + 1 + 2                         1
k = 3                                       0
k = 4     1 + 1 + 1 + 1                     1
(End)

Harvey P. Dale, Table of n, a(n) for n = 1..1000
L. Shapiro, A survey of the Riordan group

Cf. A007318, A128308.

Join[{1,0,1},Table[Join[NestWhileList[#/2&,2^n,#!=1&],{0,1}],{n,0,10}]]//Flatten (* Harvey P. Dale, Nov 25 2018 *)

(1, 0, 1, 2, 4, 8, ...) in every column.

More terms from Harvey P. Dale, Nov 25 2018

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions