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

Author

N. J. A. Sloane

Keywords

• nonn

Examples

			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).
		

Links

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

Crossrefs

Cf. A000312, A000984, A001700.

Programs

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 *)

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