|
| |
|
|
A048775
|
|
Number of (partially defined) monotone maps from intervals of 1..n to 1..n.
|
|
8
| |
|
|
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; 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 (njas(AT)research.att.com), Feb 02 2009
Arises in the classification of endomorphisms of certain finite-dimensional operator algebras.
Equals binomial transform of A163765: (1, 6, 18, 48, 131, 363, 1017,...). [From Gary W. adamson (qntmpkt(AT)yahoo.com), Aug 03 2009]
|
|
|
LINKS
| David Applegate and N. J. A. Sloane, The Gift Exchange Problem (arXiv:0907.0513, 2009)
|
|
|
FORMULA
| a(n) = binomial(2*n+1, n+1)-(n+1).
a(n) = (1/2)*Sum[Sum[(i+j)!/(i!*j!),{i,1,n}],{j,1,n}]. - Alexander Adamchuk (alex(AT)kolmogorov.com), Jul 04 2006. Corrected by N. J. A. Sloane (njas(AT)research.att.com), Jan 30 2009.
G.f.: (1/(2*x))*(1/sqrt(1-4*x)-1) - 1/(1-x)^2. - N. J. A. Sloane (njas(AT)research.att.com), 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)). [From Paul Barry (pbarry(AT)wit.ie), Oct 01 2010]
|
|
|
EXAMPLE
| a(2) = 7 because there are two maps with domain {1}, two with domain {2} and three maps with domain {1,2}.
|
|
|
MATHEMATICA
| Table[Sum[Sum[(i+j)!/i!/j!/2, {i, 1, n}], {j, 1, n}], {n, 1, 20}] - Alexander Adamchuk (alex(AT)kolmogorov.com), Jul 04 2006. Corrected by N. J. A. Sloane (njas(AT)research.att.com), Jan 30 2009.
|
|
|
CROSSREFS
| Cf. A001700, A144657.
A163765 [From Gary W. adamson (qntmpkt(AT)yahoo.com), Aug 03 2009]
Sequence in context: A032197 A114289 A147597 * A125193 A002184 A002588
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 (njas(AT)research.att.com), Dec 15 2008
|
| |
|
|
