|
| |
|
|
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.
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
|
|
|
|
FORMULA
|
a(n) = binomial(2*n+1, n+1)-(n+1) = A001700(n)-n-1.
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 *)
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
|
|
|
|
KEYWORD
|
easy,nonn,nice
|
|
|
AUTHOR
|
Stephen C. Power (s.power(AT)lancaster.ac.uk)
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
