A258306 -id:A258306 - cp's OEIS frontend

A258307 T(n,k) = 1/k! * Sum_{i=0..k} (-1)^(k-i) C(k,i) A258306(n,i); triangle T(n,k), n>=0, 0<=k<=floor(n/2), read by rows.

1, 1, 2, 1, 5, 2, 14, 9, 1, 43, 28, 3, 141, 114, 21, 1, 490, 421, 82, 4, 1785, 1750, 442, 38, 1, 6789, 7114, 1941, 180, 5, 26809, 30854, 9868, 1210, 60, 1, 109632, 134239, 46337, 6191, 335, 6, 462755, 609276, 235035, 37321, 2700, 87, 1, 2012441, 2800134, 1157603, 199424, 15806, 560, 7

Offset: 0

Alois P. Heinz, May 25 2015

			Triangle T(n,k) begins:
:     1;
:     1;
:     2,     1;
:     5,     2;
:    14,     9,    1;
:    43,    28,    3;
:   141,   114,   21,    1;
:   490,   421,   82,    4;
:  1785,  1750,  442,   38,  1;
:  6789,  7114, 1941,  180,  5;
: 26809, 30854, 9868, 1210, 60, 1;

Alois P. Heinz, Rows n = 0..200, flattened

Column k=0 gives A258312.
Row sums give A258308.
Cf. A258306, A258310.

b:= proc(x, y, t, k) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, b(x-1, y-1, false, k)*`if`(t, (x+k*y)/y, 1)
                  +b(x-1, y, false, k) +b(x-1, y+1, true, k)))
    end:
A:= (n, k)-> b(n, 0, false, k):
T:= proc(n, k) option remember;
       add(A(n, i)*(-1)^(k-i)*binomial(k, i), i=0..k)/k!
    end:
seq(seq(T(n, k), k=0..n/2), n=0..13);

b[x_, y_, t_, k_] := b[x, y, t, k] = If[y > x || y < 0, 0, If[x == 0, 1, b[x - 1, y - 1, False, k]*If[t, (x + k*y)/y, 1] + b[x - 1, y, False, k] + b[x - 1, y + 1, True, k]]];
A[n_, k_] :=  b[n, 0, False, k];
T[n_, k_] := T[n, k] = Sum[A[n, i]*(-1)^(k-i)*Binomial[k, i], {i, 0, k}]/ k!;
Table[T[n, k], {n, 0, 13}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, Jun 06 2018, from Maple *)

A140456 a(n) is the number of indecomposable involutions of length n.

Original entry on oeis.org

1, 1, 1, 3, 7, 23, 71, 255, 911, 3535, 13903, 57663, 243871, 1072031, 4812575, 22278399, 105300287, 510764095, 2527547455, 12794891007, 66012404863, 347599231103, 1863520447103, 10178746224639, 56548686860543, 319628408814847, 1835814213846271

Offset: 1

Joel B. Lewis, Jul 22 2008

nonn

An involution is a self-inverse permutation. A permutation of [n] = {1, 2, ..., n} is indecomposable if it does not fix [j] for any 0 < j < n.
From Paul Barry, Nov 26 2009: (Start)
G.f. of a(n+1) is 1/(1-x-2x^2/(1-x-3x^2/(1-x-4x^2/(1-x-5x^2/(1-...))))) (continued fraction).
a(n+1) is the binomial transform of the aeration of A000698(n+1). Hankel transform of a(n+1) is A000178(n+1). (End)
From Groux Roland, Mar 17 2011: (Start)
a(n) is the INVERTi transform of A000085(n+1)
a(n) is also the moment of order n for the density: sqrt(2/Pi^3)*exp((x-1)^2/2)/(1-(erf(I*(x-1)/sqrt(2)))^2).
More generally, if c(n)=int(x^n*rho(x),x=a..b) with rho(x) a probability density function of class C1, then the INVERTi transform of (c(1),..c(n),..) starting at n=2 gives the moments of mu(x) = rho(x) / ((s(x))^2+(Pi*rho(x))^2) with s(x) = int( rho'(t)*log(abs(1-t/x)), t=a..b) + rho(b)*log(x/(b-x)) + rho(a)*log((x-a)/x).
(End)
For n>1 sum over all Motzkin paths of length n-2 of products over all peaks p of (x_p+y_p)/y_p, where x_p and y_p are the coordinates of peak p. - Alois P. Heinz, May 24 2015

			The unique indecomposable involution of length 3 is 321. The indecomposable involutions of length 4 are 3412, 4231 and 4321.
G.f. = x + x^2 + 3*x^3 + 7*x^4 + 23*x^5 + 71*x^6 + 255*x^7 + 911*x^8 + ...

Alois P. Heinz, Table of n, a(n) for n = 1..800 (terms n = 1..50 from Joel B. Lewis)
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Claudia Malvenuto and Christophe Reutenauer, Primitive Elements of the Hopf Algebras of Tableaux, arXiv:2010.06731 [math.CO], 2020.

Cf. A000085 (involutions), A000698 (indecomposable fixed-point free involutions), and A003319 (indecomposable permutations).

Cf. A001006, A258306.

b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, b(x-1, y-1, false)*`if`(t, (x+y)/y, 1)
                 + b(x-1, y, false) + b(x-1, y+1, true)))
    end:
a:= n-> `if`(n=1, 1, b(n-2, 0, false)):
seq(a(n), n=1..35);  # Alois P. Heinz, May 24 2015

CoefficientList[Series[1 - 1/Total[CoefficientList[Series[E^(x + x^2/2), {x, 0, 50}], x] * Range[0, 50]! * x^Range[0, 50]], {x, 0, 50}], x]

G.f.: 1 - 1/I(x), where I(x) is the ordinary generating function for involutions (A000085).

G.f.: Q(0) +1/x, where Q(k) = 1 - 1/x - (k+1)/Q(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Sep 16 2013

A258309 A(n,k) is the sum over all Motzkin paths of length n of products over all peaks p of (k*x_p+y_p)/y_p, where x_p and y_p are the coordinates of peak p; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 7, 9, 1, 1, 5, 10, 23, 21, 1, 1, 6, 13, 43, 71, 51, 1, 1, 7, 16, 69, 151, 255, 127, 1, 1, 8, 19, 101, 261, 703, 911, 323, 1, 1, 9, 22, 139, 401, 1485, 2983, 3535, 835, 1, 1, 10, 25, 183, 571, 2691, 6973, 14977, 13903, 2188

Offset: 0

Alois P. Heinz, May 25 2015

			Square array A(n,k) begins:
:  1,   1,   1,    1,    1,    1,    1, ...
:  1,   1,   1,    1,    1,    1,    1, ...
:  2,   3,   4,    5,    6,    7,    8, ...
:  4,   7,  10,   13,   16,   19,   22, ...
:  9,  23,  43,   69,  101,  139,  183, ...
: 21,  71, 151,  261,  401,  571,  771, ...
: 51, 255, 703, 1485, 2691, 4411, 6735, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Wikipedia, Motzkin number

Columns k=0-1 give: A001006, A140456(n+2).
Main diagonal gives A261785.
Cf. A258306, A258310.

b:= proc(x, y, t, k) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, b(x-1, y-1, false, k)*`if`(t, (k*x+y)/y, 1)
                  +b(x-1, y, false, k) +b(x-1, y+1, true, k)))
    end:
A:= (n, k)-> b(n, 0, false, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[x_, y_, t_, k_] := b[x, y, t, k] = If[y > x || y < 0, 0, If[x == 0, 1, b[x - 1, y - 1, False, k]*If[t, (k*x + y)/y, 1] + b[x - 1, y, False, k] + b[x - 1, y + 1, True, k]]];
A[n_, k_] := b[n, 0, False, k];
Table[A[n, d - n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 04 2017, translated from Maple *)

A(n,k) = Sum_{i=0..min(floor(n/2),k)} C(k,i) * i! * A258310(n,i).

A258312 Sum over all Motzkin paths of length n of products over all peaks p of x_p/y_p, where x_p and y_p are the coordinates of peak p.

Original entry on oeis.org

1, 1, 2, 5, 14, 43, 141, 490, 1785, 6789, 26809, 109632, 462755, 2012441, 8997402, 41297927, 194306557, 936082502, 4612095475, 23219012907, 119328025012, 625545408219, 3342370197206, 18190297736313, 100768960522871, 567886743369378, 3253833477309093

Offset: 0

Alois P. Heinz, May 25 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..800
Wikipedia, Motzkin number

Column k=0 of A258306 and A258307.

b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, b(x-1, y-1, false) *`if`(t, x/y, 1)
                  +b(x-1, y, false)+b(x-1, y+1, true)))
    end:
a:= n-> b(n, 0, false):
seq(a(n), n=0..30);

b[x_, y_, t_] := b[x, y, t] = If[y>x || y<0, 0, If[x == 0, 1, b[x-1, y-1, False]*If[t, x/y, 1] + b[x-1, y, False] + b[x-1, y+1, True]]];
a[n_] := b[n, 0, False];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 10 2017, translated from Maple *)

A266386 Sum over all Motzkin paths of length n of products over all peaks p of (x_p+n*y_p)/y_p, where x_p and y_p are the coordinates of peak p.

Original entry on oeis.org

1, 1, 4, 11, 62, 243, 1575, 7721, 54985, 316407, 2427309, 15798261, 129072167, 927577835, 8008756470, 62499194297, 567017727805, 4747097031375, 45051331382395, 400942371431173, 3965769826314532, 37252002703698003, 382848953452815450, 3774255187367667473

Offset: 0

Alois P. Heinz, Dec 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..500
Wikipedia, Motzkin number

Main diagonal of A258306.

b:= proc(x, y, t, k) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, b(x-1, y-1, false, k)*`if`(t, (x+k*y)/y, 1)
                  +b(x-1, y, false, k) +b(x-1, y+1, true, k)))
    end:
a:= n-> b(n, 0, false, n):
seq(a(n), n=0..30);

b[x_, y_, t_, k_] := b[x, y, t, k] = If[y > x || y < 0, 0, If[x == 0, 1, b[x - 1, y - 1, False, k]*If[t, (x + k*y)/y, 1] + b[x - 1, y, False, k] + b[x - 1, y + 1, True, k]]];
a[n_] := b[n, 0, False, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 10 2017, translated from Maple *)

a(n) = A258306(n,n).

cp's OEIS Frontend

A258307 T(n,k) = 1/k! * Sum_{i=0..k} (-1)^(k-i) *C(k,i) * A258306(n,i); triangle T(n,k), n>=0, 0<=k<=floor(n/2), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A140456 a(n) is the number of indecomposable involutions of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A258309 A(n,k) is the sum over all Motzkin paths of length n of products over all peaks p of (k*x_p+y_p)/y_p, where x_p and y_p are the coordinates of peak p; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A258312 Sum over all Motzkin paths of length n of products over all peaks p of x_p/y_p, where x_p and y_p are the coordinates of peak p.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A266386 Sum over all Motzkin paths of length n of products over all peaks p of (x_p+n*y_p)/y_p, where x_p and y_p are the coordinates of peak p.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A258307 T(n,k) = 1/k! * Sum_{i=0..k} (-1)^(k-i) C(k,i) A258306(n,i); triangle T(n,k), n>=0, 0<=k<=floor(n/2), read by rows.