%I #52 Feb 21 2022 01:19:14
%S 1,7,31,121,456,1709,6427,24301,92368,352705,1352066,5200287,20058286,
%T 77558745,300540179,1166803093,4537567632,17672631881,68923264390,
%U 269128937199,1052049481838,4116715363777,16123801841526,63205303218851,247959266474026,973469712824029
%N Number of (partially defined) monotone maps from intervals of 1..n to 1..n.
%C More precisely, number of ways to pick a subinterval [i,i+1,...,j] of [1..n] and to map it to a nondecreasing sequence of the same length with symbols from [1..n]. If s is the length of the subinterval (1 <= s <= n), there are n+1-s ways to choose the subinterval and binomial(n+s-1,s) ways to choose the sequence, for a total of Sum_{s=1..n} (n+1-s)*binomial(n+s-1,s) = binomial(2*n+1, n+1)-(n+1) ways. - _N. J. A. Sloane_, Feb 02 2009
%C Arises in the classification of endomorphisms of certain finite-dimensional operator algebras.
%C Equals binomial transform of A163765 (using a different offset). - _Gary W. Adamson_, Aug 03 2009
%C From _David Spivak_, Dec 12 2012: (Start)
%C Number of morphisms of full subcategories of Simplex category.
%C A finite nonempty linear order of size m is isomorphic to [m]:={0,1,...,m}. The weakly monotone maps [k]->[m] form a category, often called the simplex category and denoted Delta. For m starting at -1, let D_m denote the full subcategory of Delta, spanned by objects {[0],[1],...,[m]}. The number of morphisms in D_m is a(n+1).
%C (End)
%C This sequence is the bisection of the 1st column of the triangle defined by T(n,k) = 1 if n=0 else T(n,k) = binomial(n-1,k2-1)-binomial(k2,k-1) where k2 = binomial(n,k) mod n. - _Nikita Sadkov_, Oct 08 2018
%H Harvey P. Dale, <a href="/A048775/b048775.txt">Table of n, a(n) for n = 1..1000</a>
%H David Applegate and N. J. A. Sloane, <a href="http://arxiv.org/abs/0907.0513">The Gift Exchange Problem</a>, arXiv:0907.0513 [math.CO], 2009.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Simplex_category">Simplex category</a>
%F a(n) = binomial(2*n+1, n+1)-(n+1) = A001700(n)-n-1.
%F a(n) = (1/2)*Sum[Sum[(i+j)!/(i!*j!),{i,1,n}],{j,1,n}]. - _Alexander Adamchuk_, Jul 04 2006; corrected by _N. J. A. Sloane_, Jan 30 2009
%F G.f.: (1/(2*x))*(1/sqrt(1-4*x)-1) - 1/(1-x)^2. - _N. J. A. Sloane_, Feb 02 2009
%F a(n) = Sum_{k=0..n} (n-k+1)*C(n+k+1,n) = [x^n](1+x)^n*F(-n-2,-n-1;1;x/(1+x)). - _Paul Barry_, Oct 01 2010
%F Conjecture: (n+1)*a(n) + (-7*n-2)*a(n-1) + 3*(5*n-3)*a(n-2) + (-13*n+20)*a(n-3) + 2*(2*n-5)*a(n-4) = 0. - _R. J. Mathar_, Nov 30 2012
%F a(n) = (1/2) * Sum_{k=1..n} Sum_{i=1..n} C(k+i,i). - _Wesley Ivan Hurt_, Sep 19 2017
%F E.g.f.: exp(2*x)*(BesselI(0,2*x) + BesselI(1,2*x)) - exp(x)*(1 + x). - _Ilya Gutkovskiy_, Sep 19 2017
%e a(2) = 7 because there are two maps with domain {1}, two with domain {2} and three maps with domain {1,2}.
%e When n=2, we are looking at the full subcategory of Delta spanned by [0],[1]. There is one monotone map [0]->[0], one monotone map [1]->[0], two monotone maps [0]->[1], and three monotone maps [1]->[1] (namely (0,0), (0,1), (1,1)). The total is 1+1+2+3=7. - _David Spivak_, Dec 12 2013
%p seq(coeff(series(factorial(n)*(exp(2*x)*(BesselI(0,2*x)+BesselI(1,2*x))-exp(x)*(1+x)),x,n+1), x, n), n = 1 .. 26); # _Muniru A Asiru_, Oct 09 2018
%t Table[Binomial[2n+1,n+1]-(n+1),{n,30}] (* _Harvey P. Dale_, Feb 08 2013 *)
%t From _Stefano Spezia_, Oct 09 2018: (Start)
%t a[n_]:=(1/2)*Sum[Sum[(i+j) !/(i !*j !),{i,1,n}],{j,1,n}]; Array[a, 50] (* or *)
%t CoefficientList[Series[((1/(2*x))*(1/Sqrt[1-4*x]-1) - 1/(1-x)^2)/x, {x, 0, 50}], x] (* or *)
%t CoefficientList[Series[(Exp[2*x]*(BesselI[0,2*x] + BesselI[1,2*x]) - Exp[x]*(1 + x))/x, {x, 0, 50}], x]*Table[(k+1) !, {k, 0, 50}]
%t (End)
%o (PARI) Vec((1/(2*x))*(1/sqrt(1-4*x)-1) - 1/(1-x)^2 + O(x^15)) \\ _Stefano Spezia_, Oct 09 2018
%o (GAP) List([1..26],n->Binomial(2*n+1,n+1)-(n+1)); # _Muniru A Asiru_, Oct 09 2018
%o (Magma) [Binomial(2*n+1, n+1)-(n+1): n in [1..30]]; // _Vincenzo Librandi_, Oct 10 2018
%Y Cf. A001700, A144657, A305161.
%K easy,nonn,nice
%O 1,2
%A Stephen C. Power (s.power(AT)lancaster.ac.uk)
%E More terms from _N. J. A. Sloane_, Dec 15 2008