login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A048775 Number of (partially defined) monotone maps from intervals of 1..n to 1..n. 14
1, 7, 31, 121, 456, 1709, 6427, 24301, 92368, 352705, 1352066, 5200287, 20058286, 77558745, 300540179, 1166803093, 4537567632, 17672631881, 68923264390, 269128937199, 1052049481838, 4116715363777, 16123801841526, 63205303218851, 247959266474026, 973469712824029 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
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
Arises in the classification of endomorphisms of certain finite-dimensional operator algebras.
Equals binomial transform of A163765 (using a different offset). - Gary W. Adamson, Aug 03 2009
From David Spivak, Dec 12 2012: (Start)
Number of morphisms of full subcategories of Simplex category.
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).
(End)
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
LINKS
David Applegate and N. J. A. Sloane, The Gift Exchange Problem, arXiv:0907.0513 [math.CO], 2009.
Wikipedia, Simplex category
FORMULA
a(n) = binomial(2*n+1, n+1)-(n+1) = A001700(n)-n-1.
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
G.f.: (1/(2*x))*(1/sqrt(1-4*x)-1) - 1/(1-x)^2. - N. J. A. Sloane, Feb 02 2009
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
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
a(n) = (1/2) * Sum_{k=1..n} Sum_{i=1..n} C(k+i,i). - Wesley Ivan Hurt, Sep 19 2017
E.g.f.: exp(2*x)*(BesselI(0,2*x) + BesselI(1,2*x)) - exp(x)*(1 + x). - Ilya Gutkovskiy, Sep 19 2017
EXAMPLE
a(2) = 7 because there are two maps with domain {1}, two with domain {2} and three maps with domain {1,2}.
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
MAPLE
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
MATHEMATICA
Table[Binomial[2n+1, n+1]-(n+1), {n, 30}] (* Harvey P. Dale, Feb 08 2013 *)
From Stefano Spezia, Oct 09 2018: (Start)
a[n_]:=(1/2)*Sum[Sum[(i+j) !/(i !*j !), {i, 1, n}], {j, 1, n}]; Array[a, 50] (* or *)
CoefficientList[Series[((1/(2*x))*(1/Sqrt[1-4*x]-1) - 1/(1-x)^2)/x, {x, 0, 50}], x] (* or *)
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}]
(End)
PROG
(PARI) Vec((1/(2*x))*(1/sqrt(1-4*x)-1) - 1/(1-x)^2 + O(x^15)) \\ Stefano Spezia, Oct 09 2018
(GAP) List([1..26], n->Binomial(2*n+1, n+1)-(n+1)); # Muniru A Asiru, Oct 09 2018
(Magma) [Binomial(2*n+1, n+1)-(n+1): n in [1..30]]; // Vincenzo Librandi, Oct 10 2018
CROSSREFS
Sequence in context: A032197 A114289 A147597 * A181951 A218963 A125193
KEYWORD
easy,nonn,nice
AUTHOR
Stephen C. Power (s.power(AT)lancaster.ac.uk)
EXTENSIONS
More terms from N. J. A. Sloane, Dec 15 2008
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 23 09:22 EDT 2024. Contains 371905 sequences. (Running on oeis4.)