A026737 -id:A026737 - cp's OEIS frontend

A026736 Triangular array T read by rows: T(n,0) = T(n,n) = 1 for n >= 0; for n >= 2 and 1 <= k <= n-1, T(n,k) = T(n-1,k-1) + T(n-2,k-1) + T(n-1,k) if n is even and k=(n-2)/2, otherwise T(n,k) = T(n-1,k-1) + T(n-1,k).

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 5, 6, 4, 1, 1, 6, 11, 10, 5, 1, 1, 7, 22, 21, 15, 6, 1, 1, 8, 29, 43, 36, 21, 7, 1, 1, 9, 37, 94, 79, 57, 28, 8, 1, 1, 10, 46, 131, 173, 136, 85, 36, 9, 1, 1, 11, 56, 177, 398, 309, 221, 121, 45, 10, 1, 1, 12, 67, 233, 575, 707, 530, 342, 166, 55, 11, 1

Offset: 0

Clark Kimberling

T(n, k) is the number of paths from (0, 0) to (n-k, k) in directed graph having vertices (i, j) and edges (i, j)-to-(i+1, j) and (i, j)-to-(i, j+1) for i, j >= 0 and edges (i, i+2)-to-(i+1, i+3) for i >= 0.

			Triangle begins
  1;
  1,  1;
  1,  2,  1;
  1,  3,  3,   1;
  1,  5,  6,   4,   1;
  1,  6, 11,  10,   5,   1;
  1,  7, 22,  21,  15,   6,   1;
  1,  8, 29,  43,  36,  21,   7,   1;
  1,  9, 37,  94,  79,  57,  28,   8,   1;
  1, 10, 46, 131, 173, 136,  85,  36,   9,   1;
  1, 11, 56, 177, 398, 309, 221, 121,  45,  10,   1;
  1, 12, 67, 233, 575, 707, 530, 342, 166,  55,  11,  1;
  ...

G. C. Greubel, Rows n = 0..100 of triangle, flattened

Row sums give A026743.

T(2n,n) gives A026737(n) or A111279(n+1).

T:= function(n,k)
    if k=0 or k=n then return 1;
    elif (n mod 2)=0 and k=Int((n-2)/2) then return T(n-1, k-1) + T(n-2, k-1) + T(n-1, k);
    else return T(n-1, k-1) + T(n-1, k);
    fi;
  end;
Flat(List([0..12], n-> List([0..n], k-> T(n,k) ))); # G. C. Greubel, Jul 16 2019

T[, 0] = T[n, n_] = 1; T[n_, k_] := T[n, k] = If[EvenQ[n] && k == (n-2)/2, T[n-1, k-1] + T[n-2, k-1] + T[n-1, k], T[n-1, k-1] + T[n-1, k]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 22 2018 *)

T(n,k) = if(k==n || k==0, 1, if((n%2)==0 && k==(n-2)/2, T(n-1, k-1) + T(n-2, k-1) + T(n-1, k), T(n-1, k-1) + T(n-1, k) ));
for(n=0,12, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Jul 16 2019

def T(n, k):
    if (k==0 or k==n): return 1
    elif (mod(n,2)==0 and k==(n-2)/2): return T(n-1, k-1) + T(n-2, k-1) + T(n-1, k)
    else: return T(n-1, k-1) + T(n-1, k)
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Jul 16 2019

Offset corrected by Alois P. Heinz, Jul 23 2018

A111279 Number of permutations avoiding the patterns {3241,3421,4321}; number of weak sorting class based on 3241.

Original entry on oeis.org

1, 1, 2, 6, 21, 79, 309, 1237, 5026, 20626, 85242, 354080, 1476368, 6173634, 25873744, 108628550, 456710589, 1922354351, 8098984433, 34147706833, 144068881455, 608151037123, 2568318694867, 10850577045131, 45856273670841, 193850277807569, 819669810565949

Offset: 0

Len Smiley, Nov 01 2005

nonn

Is this the same sequence as A026737? - Andrew S. Plewe, May 09 2007
Yes, see the Callan reference "A bijection...". - Joerg Arndt, Feb 29 2016
a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {1>3, 1>4, 3>2} of length 4. That is, the number of length n permutations having no subsequences of length 4 in which the first element is the largest and the third element is larger than the second element. - Sergey Kitaev, Dec 10 2020

			a(4) = 21 since the top row terms of M^3 = (11, 6, 3, 1, 0, 0, 0, ...)

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n=1..300 from Vincenzo Librandi)
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.
David Callan, A bijection for two sequences in OEIS, arXiv:1602.08347 [math.CO], 2016.
David Callan, and Toufik Mansour, Five subsets of permutations enumerated as weak sorting permutations, arXiv:1602.05182 [math.CO], 2016.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao, and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.

Rest[ CoefficientList[ Series[(3 - 13x + 2x^2 + (5x - 1)*Sqrt[1 - 4x])/(2*(1 - 4x - x^2)), {x, 0, 24}], x]] (* Robert G. Wilson v, Nov 04 2005 *)

O.g.f.: (3-13*x+2*x^2+(5*x-1)*sqrt(1-4*x))/(2*(1-4*x-x^2)).
From Gary W. Adamson, Nov 14 2011: (Start)
a(n) is the sum of top row terms of M^(n-1), M is an infinite square production matrix with powers of 2 as the left border as follows:
  1, 1, 0, 0, 0, ...
  2, 1, 1, 0, 0, ...
  4, 1, 1, 1, 0, ...
  8, 1, 1, 1, 1, ...
  ... (End)
The top rows of these matrix powers, 1; 1,1; 3,2,1; 11,6,3,1; 43,21,10,4,1; appear also as columns in A026736. - R. J. Mathar, Nov 15 2011
D-finite with recurrence n*a(n) + (16-13*n)*a(n-1)+(55*n-134)*a(n-2) + (264-71*n)*a(n-3) + 10*(7-2*n)*a(n-4) = 0. - R. J. Mathar, Nov 15 2011
Shorter recurrence: n*(n+5)*a(n) = 2*(4*n^2 + 17*n - 30)*a(n-1) - 3*(5*n^2 + 17*n - 80)*a(n-2) - 2*(n+6)*(2*n-5)*a(n-3). - Vaclav Kotesovec, Oct 18 2012
a(n) ~ (5/2-11/10*sqrt(5))*(sqrt(5)+2)^n. - Vaclav Kotesovec, Oct 18 2012

More terms from Robert G. Wilson v, Nov 04 2005

a(0)=1 prepended by Alois P. Heinz, Dec 11 2020

cp's OEIS Frontend

A026736 Triangular array T read by rows: T(n,0) = T(n,n) = 1 for n >= 0; for n >= 2 and 1 <= k <= n-1, T(n,k) = T(n-1,k-1) + T(n-2,k-1) + T(n-1,k) if n is even and k=(n-2)/2, otherwise T(n,k) = T(n-1,k-1) + T(n-1,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Mathematica

PARI

Sage

Extensions