login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 13
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

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

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

Cf. A001700, A144657, A305161.

Sequence in context: A032197 A114289 A147597 * A181951 A218963 A125193

Adjacent sequences:  A048772 A048773 A048774 * A048776 A048777 A048778

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 3 20:08 EDT 2020. Contains 336201 sequences. (Running on oeis4.)