A048775 Number of (partially defined) monotone maps from intervals of 1..n to 1..n.

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

Offset: 1

Author

Stephen C. Power (s.power(AT)lancaster.ac.uk)

Keywords

• easy
• nonn
• nice

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

Examples

			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
		

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

Crossrefs

Cf. A001700, A144657, A305161.

Programs

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

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)

PARI

Vec((1/(2*x))*(1/sqrt(1-4*x)-1) - 1/(1-x)^2 + O(x^15)) \\ Stefano Spezia, Oct 09 2018

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

Extensions

More terms from N. J. A. Sloane, Dec 15 2008