A185416 -id:A185416 - cp's OEIS frontend

A080635 Number of permutations on n letters without double falls and without initial falls.

1, 1, 1, 3, 9, 39, 189, 1107, 7281, 54351, 448821, 4085883, 40533129, 435847959, 5045745069, 62594829027, 828229153761, 11644113200031, 173331882039141, 2723549731505163, 45047085512477049, 782326996336904679, 14233537708408467549, 270733989894887810547

Offset: 0

Emanuele Munarini, Feb 28 2003

A permutation w has a double fall at k if w(k) > w(k+1) > w(k+2) and has an initial fall if w(1) > w(2).
exp(x*(1-y+y^2)*D_y)*f(y)|_{y=0} = f(1-E(-x)) for any function f with a Taylor series. D_y means differentiation with respect to y and E(x) is the e.g.f. given below. For a proof of exp(x*g(y)*D_y)*f(y) = f(F^{-1}(x+F(y))) with the compositional inverse F^{-1} of F(y)=int(1/g(y),y) with F(0)=0 see, e.g., the Datolli et al. reference.
Number of increasing ordered trees on vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <= 2. - David Callan, Mar 30 2007
Number of increasing colored 1-2 trees of order n with choice of two colors for the right branches of the vertices of outdegree 2. - Wenjin Woan, May 21 2011

			E.g.f. = 1 + x + (1/2)*x^2 + (1/2)*x^3 + (3/8)*x^4 + (13/40)*x^5 + (21/80)*x^6 + ...
G.f. = 1 + x + x^2 + 3*x^3 + 9*x^4 + 39*x^5 + 189*x^6 + 1107*x^7 + ...
For n = 3: 123, 132, 231. For n = 4: 1234, 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
a(4)=9. The 9 plane (ordered) increasing unary-binary trees are
...................................................................
..4................................................................
..|................................................................
..3..........4...4...............4...4...............3...3.........
..|........./.....\............./.....\............./.....\........
..2....2...3.......3...2...3...2.......2...3...4...2.......2...4...
..|.....\./.........\./.....\./.........\./.....\./.........\./....
..1......1...........1.......1...........1.......1...........1.....
...................................................................
..3...4...4...3....................................................
...\./.....\./.....................................................
....2.......2......................................................
....|.......|......................................................
....1.......1......................................................
...................................................................

Alois P. Heinz, Table of n, a(n) for n = 0..464
M. Aigner, Catalan and other numbers: a recurrent theme, Algebraic combinatorics and computer science, 347-390, Springer Italia, Milan, 2001.
Cyril Banderier et al., Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv:1609.06473 [math.CO], 2016. See series expansion p. 35.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees, preprint.
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, in Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
Miklós Bóna and István Mező, Limiting probabilities for vertices of a given rank in rooted trees, arXiv:1803.05033 [math.CO], 2018.
Miklós Bóna and István Mező, Limiting Probabilities for Vertices of a Given Rank in 1-2 Trees, The Electronic Journal of Combinatorics (2019) Vol. 26, No. 3, P#3.41.
Daniel Chen, Expected Number of Dice Rolls Until an Increasing Run of Three, arXiv:2308.14635 [math.CO], 2023. See p. 17.
G. Datolli, P. L. Ottaviani, A. Torre and L. Vazquez, Evolution operator equations: integration with algebraic and finite differences methods.[...], La Rivista del Nuovo Cimento 20,2 (1997) 1-133. eq. (I.2.18).
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
R. Ehrenborg, Cyclically consecutive permutation avoidance, arXiv:1312.2051 [math.CO], 2013.
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.
M. E. Jones and J. B. Remmel, Pattern matching in the cycle structures of permutations, Pure Math. Appl. (PU.M.A.), 22 (2011) 173-208.
Kaarel Hänni, Asymptotics of descent functions, MIT Mathematics UROP+ Papers (2020).
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.
Markus Kuba and Alois Panholzer, Combinatorial families of multilabelled increasing trees and hook-length formulas, arXiv:1411.4587 [math.CO], 2014.
Rupert Li, Vincular Pattern Avoidance on Cyclic Permutations, arXiv:2107.12353 [math.CO], 2021, p. 6.
Christopher Zhu, Enumerating Permutations and Rim Hooks Characterized by Double Descent Sets, arXiv:1910.12818 [math.CO], 2019.

Cf. A049774, A185415, A185416, A185422, A185423, A139605, A232864.
Cf. A000182, A002105, A234797.
Column k=0 of A162976.

a:= proc(n) if n < 2 then 1 else n! * sum((sqrt(3)/(2*Pi*(k+1/3)))^(n+1), k=-infinity..infinity) fi end: seq(a(n), n=0..30); # Richard Ehrenborg, Dec 09 2013
a := proc(n) option remember; local k; if n < 3 then 1 else
add(binomial(n-1, k)*a(k)*a(n-k-1), k = 0..n-2) fi end:
seq(a(n), n = 0..23); # Peter Luschny, May 24 2024

Table[n!, {n, 0, 40}]*CoefficientList[Series[ (1 + 1/Sqrt[3] Tan[Sqrt[3]/2 x])/(1 - 1/Sqrt[3] Tan[Sqrt[3]/2 x]), {x, 0, 40}], x]
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1/2 + Sqrt[3]/2 Tan[ Pi/6 + Sqrt[3] x/2], {x, 0, n}]]; (* Michael Somos, May 22 2011 *)
Join[{1}, FullSimplify[Table[3^((n+1)/2) * n! * (Zeta[n+1, 1/3] - (-1)^n*Zeta[n+1, 2/3]) / (2*Pi)^(n+1), {n, 1, 20}]]] (* Vaclav Kotesovec, Aug 06 2021 *)

a(n):=if n=0 then 1 else sum((-3)^((n-k)/2)*((-1)^(n-k)+1)*sum(binomial(j+k-1,j)*(j+k)!*2^(-j-k)*(-1)^(j)*stirling2(n,j+k),j,0,n-k),k,1,n); /* Vladimir Kruchinin, Feb 13 2019 */

{a(n) = my(A); if( n<1, n==0, A = O(x); for( k=1, n, A = intformal( 1 + A + A^2)); n! * polcoeff( A, n))}; /* Michael Somos, Oct 04 2003 */

{a(n) = n! * polcoeff( exp( serreverse( intformal( 1/(2*cosh(x +x*O(x^n)) - 1) ) )), n)}
for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Feb 22 2016

@CachedFunction
def c(n,k) :
    if n==k: return 1
    if k<1 or k>n: return 0
    return ((n-k)//2+1)*c(n-1,k-1)+2*k*c(n-1,k+1)
def A080635(n):
    return add(c(n,k) for k in (0..n))
[A080635(n) for n in (0..23)] # Peter Luschny, Jun 10 2014

E.g.f.: (1 + 1/sqrt(3) * tan(sqrt(3)/2 * x)) / (1 - 1/sqrt(3) * tan( sqrt(3)/2 * x)).
Recurrence: a(n+1) = (Sum_{k=0..n} binomial(n, k) * a(k) * a(n-k)) - a(n) + 0^n.
E.g.f.: A(x) satisfies A' = 1 - A + A^2. - Michael Somos, Oct 04 2003
E.g.f.: E(x) = (3*cos((1/2)*3^(1/2)*x) + (3^(1/2))*sin((1/2)*3^(1/2)*x))/(3*cos((1/2)*3^(1/2)*x) - (3^(1/2))* sin((1/2)*3^(1/2)*x)). See the Michael Somos comment. - Wolfdieter Lang, Sep 12 2005
O.g.f.: A(x) = 1+x/(1-x-2*x^2/(1-2*x-2*3*x^2/(1-3*x-3*4*x^2/(1-... -n*x-n*(n+1)*x^2/(1- ...))))) (continued fraction). - Paul D. Hanna, Jan 17 2006
From Peter Bala: (Start)
An alternative form of the e.g.f. for this sequence taken from [Bergeron et al.] is
(1)... (sqrt(3)/2)*tan((sqrt(3)/2)*x+Pi/6) [with constant term 1/2].
By comparing the egf for this sequence with the egf for the Eulerian numbers A008292 we can show that
(2)... a(n) = A(n,w)/(1+w)^(n-1) for n >= 1,
where w = exp(2*Pi*i/3) and {A(n,x),n>=1} = [1, 1+x, 1+4*x+x^2, 1+11*x+11*x^2+x^3,...] denotes the sequence of Eulerian polynomials. Equivalently,
(3)... a(n) = (-i*sqrt(3))^(n-1)*Sum_{k=1..n} k!*Stirling2(n,k)*(-1/2 + sqrt(3)*i/6)^(k-1) for n >= 1, and
(4)... a(n) = (-i*sqrt(3))^(n-1)*Sum_{k=1..n} (-1/2 + sqrt(3)*i/6)^(k-1)* Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*j^n for n >= 1.
This explicit formula for a(n) may be used to obtain various congruence results. For example,
(5a)... a(p) == 1 (mod p) for prime p = 6*n+1,
(5b)... a(p) == -1 (mod p) for prime p = 6*n+5.
For the corresponding results for the case of non-plane unary-binary trees see A000111. For type B results see A001586. For a related sequence of polynomials see A185415. See also A185416 for a recursive method to compute this sequence. For forests of plane increasing unary binary trees see A185422 and A185423. (End)
O.g.f.: A(x) = x - (1/2)*x^2 + (1/2)*x^3 - (3/8)*x^4 + (13/40)*x^5 - (21/80)*x^6 + (123/560)*x^7 - (809/4480)*x^8 + (671/4480)*x^9 - (5541/44800)*x^10 + .... - Vladimir Kruchinin, Jan 18 2011
Let f(x) = 1+x+x^2. Then a(n+1) = (f(x)*d/dx)^n f(x) evaluated at x = 0. - Peter Bala, Oct 06 2011
From Sergei N. Gladkovskii, May 06 2013 - Dec 24 2013: (Start)
Continued fractions:
G.f.: 1 + 1/Q(0), where Q(k) = 1/(x*(k+1)) - 1 - 1/Q(k+1).
E.g.f.: 1 + 2*x/(W(0)-x), where W(k) = 4*k + 2 - 3*x^2/W(k+1).
G.f.: 1 + x/Q(0), m=1, where Q(k) = 1 - m*x*(2*k+1) - m*x^2*(2*k+1)*(2*k+2)/( 1 - m*x*(2*k+2) - m*x^2*(2*k+2)*(2*k+3)/Q(k+1) ).
G.f.: 1 + x/Q(0), where Q(k) = 1 - x*(k+1) - x^2*(k+1)*(k+2)/Q(k+1).
G.f.: 1 + T(0)*x/(1-x), where T(k) = 1 - x^2*(k+1)*(k+2)/( x^2*(k+1)*(k+2) - (1-x*(k+1))*(1-x*(k+2))/T(k+1) ).
G.f.: 1 + x/(G(0)-x), where G(k) = 1 + x*(k+1) - x*(k+1)/(1 - x*(k+2)/G(k+1) ). (End)
a(n) ~ 3^(3*(n+1)/2) * n^(n+1/2) / (exp(n)*(2*Pi)^(n+1/2)). - Vaclav Kotesovec, Oct 05 2013
a(n) = n! * Sum_{k=-oo..oo} (sqrt(3)/(2*Pi*(k+1/3)))^(n+1) for n >= 1. - Richard Ehrenborg, Dec 09 2013
From Peter Bala, Sep 11 2015: (Start)
The e.g.f. A(x) = (sqrt(3)/2)*tan((sqrt(3)/2)*x + Pi/6) satisfies the differential equation A"(x) = 2*A(x)*A'(x) with A(0) = 1/2 and A'(0) = 1, leading to the recurrence a(0) = 1/2, a(1) = 1, else a(n) = 2*Sum_{i = 0..n-2} binomial(n-2,i)*a(i)*a(n-1-i) for the sequence [1/2, 1, 1, 3, 9, 39, 189, 1107, ...].
Note, the same recurrence, but with the initial conditions a(0) = 1 and a(1) = 1, produces the sequence n! and with a(0) = 0 and a(1) = 1 produces A000182. Cf. A002105, A234797. (End)
E.g.f.: exp( Series_Reversion( Integral 1/(2*cosh(x) - 1) dx ) ). - Paul D. Hanna, Feb 22 2016
a(n) = Sum_{k=1..n} (-3)^((n-k)/2)*((-1)^(n-k)+1)*Sum_{j=0..n-k} C(j+k-1,j)*(j+k)!*2^(-j-k)*(-1)^j*Stirling2(n,j+k),n>0, a(0)=1. - Vladimir Kruchinin, Feb 13 2019
For n > 0, a(n) = 3^((n+1)/2) * n! * (zeta(n+1, 1/3) - (-1)^n*zeta(n+1, 2/3)) / (2*Pi)^(n+1). - Vaclav Kotesovec, Aug 06 2021

Several typos corrected by Olivier Gérard, Mar 26 2011

A185415 Table of coefficients of a polynomial sequence of binomial type related to A080635.

Original entry on oeis.org

1, 0, 1, 2, 0, 1, 0, 8, 0, 1, 18, 0, 20, 0, 1, 0, 148, 0, 40, 0, 1, 378, 0, 658, 0, 70, 0, 1, 0, 5040, 0, 2128, 0, 112, 0, 1, 14562, 0, 33992, 0, 5628, 0, 168, 0, 1, 0, 277164, 0, 158480, 0, 12936, 0, 240, 0, 1

Offset: 1

Peter Bala, Jan 27 2011

Define a sequence of polynomials P(n,x) by means of the recurrence relation
(1)... P(n+1,x) = x*{P(n,x-1)-P(n,x)+P(n,x+1)}
with starting value P(0,x) = 1. The first few polynomials are
  P(1,x) = x
  P(2,x) = x^2
  P(3,x) = x*(x^2+2),
  P(4,x) = x^2*(x^2+8),
  P(5,x) = x*(x^4+20*x^2+18).
This triangle lists the coefficients of these polynomials in ascending powers of x. The triangle has links with A080635, which gives the number of ordered increasing 0-1-2 trees on n nodes (plane unary-binary trees in the notation of [BERGERON et al.]). The number of forests of k such trees on n nodes is given by the formula
... 1/k!*Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*P(n,j).
See A185422.
We also have A080635(n) = P(n,1), which can be used to calculate the terms of A080635 - see A185416.
For similarly defined polynomial sequences for other families of trees see A147309 and A185419. See also A185417.
Exponential Riordan array [(3/2)*(1-sqrt(3)*tan((Pi+3*sqrt(3)*x)/6))/(-1+2*sin((Pi-6*sqrt(3)*x)/6)), log((1/2)*(1+sqrt(3)*tan(sqrt(3)*x/2+Pi/6)))]. Production matrix is the exponential Riordan array [2*cosh(x)-1,x] beheaded. A185422*A008277^{-1}.

			Triangle begins:
  n\k|....1......2......3......4......5......6......7......8
  ==========================================================
  ..1|....1
  ..2|....0......1
  ..3|....2......0......1
  ..4|....0......8......0......1
  ..5|...18......0.....20......0......1
  ..6|....0....148......0.....40......0......1..
  ..7|..378......0....658......0.....70......0......1
  ..8|....0...5040......0...2128......0....112......0......1

F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, in Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1922, pp. 24-48.

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees

Cf. A080635, A147309, A185417, A185419, A185422, A185423.

#A185415
P := proc(n,x)
description 'polynomial sequence P(n,x)'
if n = 0
return 1
else return
x*(P(n-1,x-1)-P(n-1,x)+P(n-1,x+1))
end proc:
with(PolynomialTools):
for n from 1 to 10
CoefficientList(P(n,x),x);
end do;

p[0][x_] = 1; p[n_][x_] := p[n][x] = x*(p[n-1][x-1] - p[n-1][x] + p[n-1][x+1]) // Expand; row[n_] := CoefficientList[ p[n][x], x]; Table[row[n] // Rest, {n, 1, 10}] // Flatten (* Jean-François Alcover, Sep 11 2012 *)

GENERATING FUNCTION
The e.g.f. is
(1)... F(x, t) = E(t)^x = Sum_{n >= 0} P(n, x) * t^n/n!,
where
E(t) = 1/2+sqrt(3)/2*tan[sqrt(3)/2*t+Pi/6] = 1 + t + t^2/2! + 3*t^3/3! + 9*t^4/4! + ... is the e.g.f. for A080635.
ROW POLYNOMIALS
One easily checks that
... d/dt(F(x,t)) = x*(F(x-1,t)-F(x,t)+F(x+1,t))
and hence the row generating polynomials P(n,x) satisfy the recurrence relation
(2)... P(n+1,x) = x*{P(n,x-1)-P(n,x)+P(n,x+1)}.
RELATIONS WITH OTHER SEQUENCES
A080635(n) = P(n,1).
A185422(n,k) = 1/k!*Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*P(n,j).
A185423(n,k) = Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*P(n,j).

A185414 Square array, read by antidiagonals, used to recursively calculate the zigzag numbers A000111.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 5, 5, 3, 1, 16, 16, 10, 4, 1, 61, 61, 39, 17, 5, 1, 272, 272, 176, 80, 26, 6, 1, 1385, 1385, 903, 421, 145, 37, 7, 1, 7936, 7936, 5200, 2464, 880, 240, 50, 8, 1, 50521, 50521, 33219, 15917, 5825, 1661, 371, 65, 9, 1

Offset: 1

Peter Bala, Jan 26 2011

The table entries T(n,k), for n,k>=1, are defined by means of the recurrence relation (1)... T(n+1,k) = 1/2*{(k-1)*T(n,k-1)+(k+1)*T(n,k+1)}, with boundary condition T(1,k) = 1.
The first column of the table produces the sequence of zigzag numbers A000111. Cf. A185416, A185418 and A185420.
Diagonal T(n,n+1) = A290579(n) for n>=1. - Paul D. Hanna, Aug 07 2017

			The array begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...;
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...;
2, 5, 10, 17, 26, 37, 50, 65, 82, ...;
5, 16, 39, 80, 145, 240, 371, 544, 765, ...;
16, 61, 176, 421, 880, 1661, 2896, 4741, 7376, ...;
61, 272, 903, 2464, 5825, 12336, 23947, 43328, 73989, ...;
272, 1385, 5200, 15917, 41936, 98377, 210320, 416765, ...;
1385, 7936, 33219, 112640, 326965, 840960, 1962191, ...; ...
Examples of the recurrence:
T(4,4) = 80 = (3*T(3,3) + 5*T(3,5))/2 = (3*10 + 5*26)/2;
T(5,3) = 176 = (2*T(4,2) + 4*T(4,4))/2 = (2*16 + 4*80)/2;
T(6,2) = 272 = (1*T(5,1) + 3*T(5,3))/2 = (1*16 + 3*176)/2.

Cf. A000111, A147309, A185416, A185418, A185420, A290579.

#A185414 Z := proc(n,x)
description 'zigzag polynomials A147309'
if n = 0 return 1 else return 1/2*x*(Z(n-1,x-1)+Z(n-1,x+1))
end proc:
# values of Z(n,x)/x
for n from 1 to 10 do seq(Z(n,k)/k, k = 1..10);
end do;

{T(n,k)=if(n==1,1,((k-1)*T(n-1,k-1)+(k+1)*T(n-1,k+1))/2)}
for(n=1,10, for(k=1,10, print1(T(n,k),", ")); print(""))

(1)... T(n,k) = Z(n,k)/k with Z(n,x) the zigzag polynomials described in A147309.

A185418 Square array, read by antidiagonals, used to recursively calculate the Springer numbers A001586.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 11, 11, 5, 1, 57, 57, 27, 7, 1, 361, 361, 175, 51, 9, 1, 2763, 2763, 1353, 413, 83, 11, 1, 24611, 24611, 12125, 3801, 819, 123, 13, 1, 250737, 250737, 123987, 39487, 8857, 1441, 171, 15, 1, 2873041, 2873041, 1424215, 458331, 105489, 18057, 2327, 227, 17, 1

Offset: 0

Peter Bala, Jan 30 2011

The table entries T(n,k), n,k>=0, are defined by the recurrence relation:
1)... T(n+1,k) = k*T(n,k-1)+(k+1)*T(n,k+1) with boundary condition T(0,k) = 1.
The first column of the table produces the sequence of Springer numbers A001586.
For similarly defined tables see A185414, A185416 and A185420.

			Square array begins
n\k|.....0......1.......2.......3........4........5........6
============================================================
..0|.....1......1.......1.......1........1........1........1
..1|.....1......3.......5.......7........9.......11.......13
..2|.....3.....11......27......51.......83......123......171
..3|....11.....57.....175.....413......819.....1441.....2327
..4|....57....361....1353....3801.....8857....18057....33321
..5|...361...2763...12125...39487...105489...244211...507013
..6|..2763..24611..123987..458331..1379003..3569523..8229891
..
Examples of recurrence relation:
T(4,3) = 3801 = 3*T(3,2) + 4*T(3,4) = 3*175 + 4*819;
T(5,1) = 2763 = 1*T(4,0)+ 2*T(4,2) = 1*57 + 2*1353.

Cf. A001586, A185417, A185414, A185416, A185420.

# A185418
S := proc(n, x) option remember; description `polynomials S(n, x)`;
if n = 0 then 1 else x*S(n-1,x-1)+(x+1)*S(n-1,x+1) end if end proc:
for n from 0 to 10 do seq(S(n, k), k = 0..10) end do;

T[n_, k_] := T[n, k] = If[n<0 || k<0, 0, If[n == 0, 1, k T[n-1, k-1] + (k+1)*T[n-1, k+1]]];
Table[T[n-k, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 22 2021 *)

{T(n,k)=if(n<0||k<0,0,if(n==0,1,k*T(n-1,k-1)+(k+1)*T(n-1,k+1)))}

(1)... T(n,k) = S(n,k) with S(n,x) the polynomials described in A185417.
(2)... First column: T(n,0) = A001586(n).
(3)... Second column: T(n,1) = A001586(n+1).
(4)... Second row: T(1,k) = A005408(k).
(5)... Third row: T(2,k) = A164897(k).

A185420 Square array, read by antidiagonals, used to recursively calculate the number of minimax trees A080795.

Original entry on oeis.org

1, 4, 1, 20, 5, 1, 128, 32, 6, 1, 1024, 256, 46, 7, 1, 9856, 2464, 432, 62, 8, 1, 110720, 27680, 4784, 662, 80, 9, 1, 1421312, 355328, 60864, 8224, 952, 100, 10, 1, 20525056, 5131264, 873664, 116128, 13048, 1308, 122, 11, 1

Offset: 1

Peter Bala, Jan 30 2011

The table entries T(n,k), for n,k>=1, are defined by means of the recurrence relation
(1)... T(n+1,k) = (2*k+2)*T(n,k+1)-(k-1)*T(n,k-1),
with boundary condition T(1,k) = 1.
The first column of the table gives A080795.
For similarly defined tables used to calculate the zigzag numbers A000111 and the Springer numbers A001586 see A185414 and A185418, respectively.
See also A185416.

			Square array begins
n\k|......1.......2.......3........4.......5.........6
======================================================
..1|......1.......1.......1........1........1........1
..2|......4.......5.......6........7........8........9
..3|.....20......32......46.......62.......80......100
..4|....128.....256.....432......662......952.....1308
..5|...1024....2464....4784.....8224....13048....19544
..6|...9856...27680...60864...116128...201632...327096
..7|.110720..355328..873664..1833728..3460640..6046720
..
Examples of recurrence relation:
T(4,3) = 432 = 8*T(3,4) - 2*T(3,2) = 8*62 - 2*32;
T(6,2) = 27680 = 6*T(5,3) - 1*T(5,1) = 6*4784 - 1*1024.

Cf. A080795, A185414, A185416, A185418, A185419.

#A185420
M := proc(n,x) option remember;
description 'minimax polynomials M(n,x)'
if n = 0
return 1
else return
x*(2*M(n-1,x+1)-M(n-1,x-1))
end proc:
for n from 1 to 10 do
seq(M(n,k)/k, k = 1..10);
end do;

M[n_, x_] := M[n, x] = If[n == 0, 1, x (2 M[n - 1, x + 1] - M[n - 1, x - 1])];
T[n_, k_] := M[n, k]/k;
Table[T[d - k + 1, k], {d, 1, 9}, {k, 1, d}] // Flatten (* Jean-François Alcover, Sep 24 2022 *)

{T(n,k)=if(n<1||k<1,0,if(n==1,1,(2*k+2)*T(n-1,k+1)-(k-1)*T(n-1,k-1)))}

(1)... T(n,k) = M(n,k)/k with M(n,x) the polynomials described in A185419.
(2)... First column: T(n,1) = A080795(n).
(3)... Second column: T(n,2) = (1/4)*A080795(n+1).

cp's OEIS Frontend

A080635 Number of permutations on n letters without double falls and without initial falls.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

Sage

Formula

Extensions

A185415 Table of coefficients of a polynomial sequence of binomial type related to A080635.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A185414 Square array, read by antidiagonals, used to recursively calculate the zigzag numbers A000111.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

Formula

A185418 Square array, read by antidiagonals, used to recursively calculate the Springer numbers A001586.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A185420 Square array, read by antidiagonals, used to recursively calculate the number of minimax trees A080795.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Formula