A045992 a(n) = binomial(2n,n) - n; number of (weakly) increasing or decreasing maps from 1,...,n to 1,...,n.

1, 1, 4, 17, 66, 247, 918, 3425, 12862, 48611, 184746, 705421, 2704144, 10400587, 40116586, 155117505, 601080374, 2333606203, 9075135282, 35345263781, 137846528800, 538257874419, 2104098963698, 8233430727577, 32247603683076

Offset

0,3

Links

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Formula

G.f.: (x^2 - (sqrt(1-4*x)+2)*x + 1)/(sqrt(1-4*x)*(x-1)^2). - Harvey P. Dale, Apr 18 2014

D-finite with recurrence: n*a(n) + (-7*n+5)*a(n-1) + 3*(5*n-8)*a(n-2) + (-13*n+33)*a(n-3) + 2*(2*n-7)*a(n-4) = 0. - R. J. Mathar, Jan 28 2020

Example

a(3)=17 since can map (1,2,3) to (1,1,1), (1,1,2), (1,1,3), (1,2,2), (1,2,3), (1,3,3), (2,1,1), (2,2,1), (2,2,2), (2,2,3), (2,3,3), (3,1,1), (3,2,1), (3,2,2), (3,3,1), (3,3,2), or (3,3,3) but not for example to (1,3,2).

Mathematica

Table[Binomial[2n, n]-n, {n, 0, 30}] (* or *) CoefficientList[Series[ (x^2- (Sqrt[1-4 x]+2) x+1)/(Sqrt[1-4 x] (x-1)^2), {x, 0, 30}], x] (* Harvey P. Dale, Apr 18 2014 *)

Crossrefs

Cf. A000312, A000984, A001700.

Sequence in context: A102207 A334827 A202555 * A217539 A046723 A291394

Adjacent sequences: A045989 A045990 A045991 * A045993 A045994 A045995

Keyword

nonn

Author

N. J. A. Sloane

Status

approved