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

%I #18 Mar 08 2020 04:46:47

%S 1,1,4,17,66,247,918,3425,12862,48611,184746,705421,2704144,10400587,

%T 40116586,155117505,601080374,2333606203,9075135282,35345263781,

%U 137846528800,538257874419,2104098963698,8233430727577,32247603683076

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

%H Harvey P. Dale, <a href="/A045992/b045992.txt">Table of n, a(n) for n = 0..1000</a>

%F G.f.: (x^2 - (sqrt(1-4*x)+2)*x + 1)/(sqrt(1-4*x)*(x-1)^2). - _Harvey P. Dale_, Apr 18 2014

%F 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

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

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

%Y Cf. A000312, A000984, A001700.

%K nonn

%O 0,3

%A _N. J. A. Sloane_