A026671 -id:A026671 - cp's OEIS frontend

A107842 A number triangle of lattice walks.

1, 2, 1, 5, 5, 1, 14, 20, 8, 1, 42, 75, 44, 11, 1, 132, 275, 208, 77, 14, 1, 429, 1001, 910, 440, 119, 17, 1, 1430, 3640, 3808, 2244, 798, 170, 20, 1, 4862, 13260, 15504, 10659, 4655, 1309, 230, 23, 1, 16796, 48450, 62016, 48279, 24794, 8602, 2000, 299, 26, 1

Offset: 0

Paul Barry, May 24 2005

First column is A000108(n+1). Columns include A000344, A003518 and A000589. Row sums are A026671. Compare [1,1,1,...] DELTA [0,1,0,0,...] where DELTA is the operator defined in A084938.

Transposed version in A109450. - Philippe Deléham, Jun 05 2007

			Triangle begins
   1;
   2,  1;
   5,  5,  1;
  14, 20,  8,  1;
  42, 75, 44, 11,  1;
Triangle [1,1,1,1,1,...] DELTA [0,1,0,0,0,0,...] begins:
    1;
    1,   0;
    2,   1,   0;
    5,   5,   1,   0;
   14,  20,   8,   1,   0;
   42,  75,  44,  11,   1,   0;
  132, 275, 208,  77,  14,   1,   0; ...

Paul Barry, Chebyshev moments and Riordan involutions, arXiv:1912.11845 [math.CO], 2019.

Number triangle T(n, k) = (3k+2)*C(2n+k+1, n-k)/(n+2k+2).

Column k has g.f.: x^k*C(x)^(3k+2) where C(x) is the g.f. of A000108.

A109450 Triangle T(n,k), 0<=k<=n, read by rows, given by [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...] DELTA [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 5, 5, 0, 1, 8, 20, 14, 0, 1, 11, 44, 75, 42, 0, 1, 14, 77, 208, 275, 132, 0, 1, 17, 119, 440, 910, 1001, 429, 0, 1, 20, 170, 798, 2244, 3808, 3640, 1430, 0, 1, 23, 230, 1309, 4655, 10659, 15504, 13260, 4862, 0, 1, 26, 299, 2000

Offset: 0

Philippe Deléham, Aug 26 2005

Row sums : 1, 1, 3, 11, 43, 173, .... (see A026671).

Transposed version in A107842.

			Triangle begins:
1;
0, 1;
0, 1, 2;
0, 1, 5, 5;
0, 1, 8, 20, 14;
0, 1, 11, 44, 75, 42;
0, 1, 14, 77, 208, 275, 132

Cf. A000108, A000344, A003518, A000589, A107842.

T(0, 0) = 1, T(n, 0) = 0 if n>0, T(n, k) = 0 if k>n, T(n, k) = (3n-3k+2)*binomial(3n-k-1, k-1)/(3n-2k+1).

T(n, n) = A000108(n), Catalan numbers.

A164651 Number of permutations of length n that avoid both 1243 and 2134.

Original entry on oeis.org

1, 1, 2, 6, 22, 87, 354, 1459, 6056, 25252, 105632, 442916, 1860498, 7826120, 32956964, 138911074, 585926818, 2472923499, 10442263142, 44112331275, 186413949540, 788000866243, 3331853294090, 14090947775581, 59604161832772

Offset: 0

Vincent Vatter, Aug 19 2009

nonn

Le proved that this also gives the number of permutations of length n that avoid both 1342 and 3124.

For n>=1, a(n) is the number of paths of North steps N = (0,1), East steps E = (1,0), and Diagonal steps D = (1,1) from the origin to (n-1,n-1) such that all D steps lie on the diagonal line y = x and the first step away from the diagonal (if there is one) is a North step. For example, a(3) = 6 counts DD, DNE, NED, NENE, NEEN, NNEE. - David Callan, Jun 25 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..300
David Callan, The number of {1243, 2134}-avoiding permutations, arXiv:1303.3857 [math.CO], 2013.
David Callan, Permutations avoiding 4321 and 3241 have an algebraic generating function, arXiv:1306.3193 [math.CO], 2013.
Darla Kremer and Wai Chee Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
Ian Le, Wilf classes of pairs of permutations of length 4, Electron. J. Combin., 12(1) (2005), Research article 25, 26 pages.
Wikipedia, Permutation classes avoiding two patterns of length 4.

Cf. A026671, A358092.

CoefficientList[Series[(3*x^2-9*x+2+x*(1-x)*Sqrt[1-4*x])/(2*(x-1)*(x^2+4*x-1)), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 28 2012 *)

From Vaclav Kotesovec, Oct 24 2012: (Start)
G.f.: (3*x^2-9*x+2+x*(1-x)*sqrt(1-4*x))/(2*(x-1)*(x^2+4*x-1)).
Recurrence: (n-4)*(n-1)*a(n) = (9*n^2 - 51*n + 62)*a(n-1) - (23*n^2 - 145*n + 222)*a(n-2) + (11*n^2 - 73*n + 122)*a(n-3) + 2*(n-3)*(2*n-7)*a(n-4).
a(n) ~ (1/2-1/sqrt(5))*(sqrt(5)+2)^n. (End)
These formulas were conjectured by Vaclav Kotesovec and proved correct by David Callan (see Link).
a(n) = (A026671(n-1) + 1)/2 for n >= 1. - David Callan, Jun 25 2013
a(n-1) = Sum_{k=0..n} binomial(n, k)*A358092(k) for n >= 1. - Peter Luschny, Oct 29 2022

A305561 Expansion of 2x(1 - 2x)/(1 + 2x - 8x^2 - sqrt(1 - 4x^2)).

Original entry on oeis.org

1, 1, 3, 8, 23, 64, 182, 512, 1451, 4096, 11594, 32768, 92710, 262144, 741548, 2097152, 5931955, 16777216, 47454210, 134217728, 379628818, 1073741824, 3037013748, 8589934592, 24296051198, 68719476736, 194368201572, 549755813888, 1554944869676, 4398046511104

Offset: 0

Ilya Gutkovskiy, Jun 21 2018

nonn

Invert transform of A001405.

N. J. A. Sloane, Transforms
Eric Weisstein's World of Mathematics, Central Binomial Coefficient

Cf. A001405, A026671, A054341, A075436, A293732, A293741.

m:=35; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!( 2*x*(1 - 2*x)/(1 + 2*x - 8*x^2 - Sqrt(1 - 4*x^2)))); // Vincenzo Librandi, Jan 27 2020

a:= proc(n) option remember; `if`(n=0, 1, add(
      a(n-i)*binomial(i, floor(i/2)), i=1..n))
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Jun 21 2018

nmax = 29; CoefficientList[Series[2 x (1 - 2 x)/(1 + 2 x - 8 x^2 - Sqrt[1 - 4 x^2]), {x, 0, nmax}], x]
nmax = 29; CoefficientList[Series[1/(1 - Sum[Binomial[k, Floor[k/2]] x^k, {k, 1, nmax}]), {x, 0, nmax}], x]
a[0] = 1; a[n_] := a[n] = Sum[Binomial[k, Floor[k/2]] a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 29}]

G.f.: 1/(1 - Sum_{k>=1} binomial(k,floor(k/2))*x^k).
D-finite with recurrence: n*(n+1)*a(n) +(n-1)*(n-5)*a(n-1) -12*(n-1)*(n+1)*a(n-2) -12*(n-2)*(n-5)*a(n-3) +32*(n+1)*(n-3)*a(n-4) +32*(n-4)*(n-5)*a(n-5)=0. - R. J. Mathar, Jan 25 2020
a(n) ~ 2^(3*(n-1)/2). - Vaclav Kotesovec, Jan 29 2020

cp's OEIS Frontend

A107842 A number triangle of lattice walks.

Views

Author

Keywords

Comments

Examples

Links

Formula

A109450 Triangle T(n,k), 0<=k<=n, read by rows, given by [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...] DELTA [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A164651 Number of permutations of length n that avoid both 1243 and 2134.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A305561 Expansion of 2x(1 - 2x)/(1 + 2x - 8x^2 - sqrt(1 - 4x^2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

cp's OEIS Frontend

A107842 A number triangle of lattice walks.

Views

Author

Keywords

Comments

Examples

Links

Formula

A109450 Triangle T(n,k), 0<=k<=n, read by rows, given by [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...] DELTA [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A164651 Number of permutations of length n that avoid both 1243 and 2134.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A305561 Expansion of 2*x*(1 - 2*x)/(1 + 2*x - 8*x^2 - sqrt(1 - 4*x^2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A305561 Expansion of 2x(1 - 2x)/(1 + 2x - 8x^2 - sqrt(1 - 4x^2)).