|
|
A001339
|
|
a(n) = Sum_{k=0..n} (k+1)! binomial(n,k).
(Formerly M2901 N1164)
|
|
64
|
|
|
1, 3, 11, 49, 261, 1631, 11743, 95901, 876809, 8877691, 98641011, 1193556233, 15624736141, 220048367319, 3317652307271, 53319412081141, 909984632851473, 16436597430879731, 313262209859119579, 6282647653285676001, 132266266384961600021, 2916471173788403280463
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Number of arrangements of {1, 2, ..., n, n + 1} containing the element 1. - Emeric Deutsch, Oct 11 2001
"Also the number of hierarchies with unlabeled elements and labeled levels where the levels are permuted.
"Let l_x denote level x, e.g. l_2 is level 2. Let * denote an element. Then l_1*l_2***l_3** denotes a hierarchy of n = 6 unlabeled elements with one element on level 1, three elements on level 2 and 2 elements on level 3.
"E.g. for n=3 one has a(3) = 11 possible hierarchies: l_1***, l_1**l_2*, l_1*l_2**, l_2**l_1*, l_2*l_1**, l_1*l_2*l_3*, l_3*l_1*l_2*, l_2*l_3*l_1*, l_1*l_3*l_2*, l_2*l_1*l_3*, l_3*l_2*l_1*. See A064618 for the number of hierarchies with labeled elements and labeled levels." (End)
Polynomials in A010027 evaluated at 2.
Also the permanent of any n X n cofactor of an n+1 X n+1 version of J+I other than an n X n version of J + I (that is, a (1, 2) matrix with n - 1 2s, at most one per row and column). - D. G. Rogers, Aug 27 2006
a(n) = number of partitions of [n+1] into lists of sets that are both non-nesting and non-crossing. Non-nesting means that no set is contained in the span (interval from min to max) of another. For example, a(1) counts 12, 1-2, 2-1 and a(2) counts 123, 1-23, 23-1, 3-12, 12-3, 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1. - David Callan, Sep 20 2007
a(n) is a difference divisibility sequence, that is, the difference a(n) - a(m) is divisible by n - m for all n and m (provided n is not equal to m). See A000522 for further properties of difference divisibility sequences.
a(n) equals the sum of the lengths of the paths between a pair of distinct vertices of the complete graph K_(n + 2) on n + 2 vertices [Hassani]. For example, for the complete graph K_4 with vertex set {A,B,C,D} the 5 paths between A and B are AB of length 1, ACB and ADB, both of length 2 and ACDB and ADCB, both of length 3. The sum of the lengths is 1 + 2 + 2 + 3 + 3 = 11 = a(2).
The number of paths between 2 distinct vertices of K_n is equal to A000522(n - 2); the number of simple cycles through a vertex of K_n equals A038154(n - 1).
Recurrence relation: a(0) = 1, a(1) = 3, a(n) = (n+2)*a(n - 1) - (n - 1)*a(n - 2) for n >= 2. The sequence b(n) := n*n! = A001563(n) satisfies the same recurrence with the initial conditions b(0) = 0, b(1) = 1. This leads to the finite continued fraction expansion a(n)/b(n) = 3 - 1/(4 - 2/(5 - 3/(6 - ... - (n - 1)/(n + 2)))), n >= 1.
Limit_{n->oo} a(n)/b(n) = e = 3 - 1/(4 - 2/(5 - 3/(6 - ... - n/((n + 3) - ...)))).
For n >= 1, a(n) = b(n)*(3 - Sum_{k=2..n} 1/(k!*(k - 1)*k) (see the formula by Deutsch) since the rhs satisfies the above recurrence with the same initial conditions. Hence e = 3 - Sum_{k>=2} 1/(k!*(k - 1)*k).
For sequences satisfying the more general recurrence a(n) = (n + 1 + r)*a(n-1) - (n-1)*a(n-2), which yield series acceleration formulas for e/r! that involve the Poisson-Charlier polynomials c_r(-n; -1), refer to A000522 (r=0), A082030 (r=2), A095000 (r=3) and A095177 (r=4). (End)
Binomial transform of n! Offset 1. a(3) = 11. - Al Hakanson (hawkuu(AT)gmail.com), May 18 2009
Equals eigensequence of a triangle with (1, 2, 3, ...) as the right border and the rest 1's; equivalent to a(n) = [n terms of the sequence (1, 1, 1, ...) followed by (n + 1)] dot [(n + 1) terms of the sequence (1, 1, 3, 11, 245, ...)]. Example: 261 = a(4) = (1, 1, 1, 1, 5) dot (1, 1, 3, 11, 49) = 1 + 1 + 3 + 11 + 245 = 261. - Gary W. Adamson, Jul 24 2010
a(n) is the number of permutations of {1,2,...,n+2} in which there is an increasing contiguous subsequence (ascending run) beginning with 1 and ending with n+2. The number of such permutations with exactly k, 0<=k<=n, elements between the 1 and (n+2) is given by A132159(n,k) whose row sums equal this sequence. See example. - Geoffrey Critzer, Feb 15 2013
|
|
REFERENCES
|
A. Hordijk, Markov Decision Chains, pp. 97-103 in Images of SMC Research, 1996, Stichting Mathematisch Centrum, Amsterdam, Netherlands, 1996. See p. 103.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
W. A. Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 56, ex. 232.
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: exp(x)/(1-x)^2.
a(n) = round(evalf(exp(1)*(n-1)*(n-1)!)) (n>1).
a(n) = floor(n*n!*e) + 1. - Melvin J. Knight (knightmj(AT)juno.com), May 30 2001
a(n) = {e*n*n!} for n > 0, where {x} denotes the nearest integer part. Proposed by Simon Plouffe, March 1993.
The n-th row of array A089900 is the n-th binomial transform of this sequence. The (n+1)-th term of the n-th binomial transform is (n+1)^(n+1), for n >= 0. E.g., the 5th term of the 4th binomial transform is 5^5: [1, 7, 51, 389, 3125, ...]. - Paul D. Hanna, Nov 14 2003
G.f.: Sum_{k>=0} k! * (x / (1 - x))^k. - Michael Somos, Mar 04 2004
a(n) = Sum_{k=0..n} P(n, k)*(k+1). - Ross La Haye, Aug 28 2005
a(n) = n!*n*(3 - Sum_{j=2..n} 1/(j*(j-1)*j!) for n>=1. - Emeric Deutsch, Apr 12 2008
a(n) = (a(n-1)^2 + 2 * a(n-2)^2 + a(n-2) * a(n-3) - 4 * a(n-1) * a(n-3)) / (a(n-2) - a(n-3)) if n>1. - Michael Somos, Oct 20 2011
E.g.f.:1/Q(0); Q(k) = 1 - 2*x/(1+x/(2-x-2/(1-x*(k+1)/Q(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Nov 18 2011
G.f.: 1/Q(0), where Q(k) = 1 - x - x*(k+2)/(1 - x*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, Apr 22 2013
G.f.: Q(0)/x - 1/x, where Q(k) = 1 + (2*k + 1)*x/( 1 - x - 2*x*(1-x)*(k+1)/(2*x*(k+1) + (1-x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 09 2013
G.f.: (2/x)/G(0) - 1/x, where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+3) - 1 + x*(2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 31 2013
G.f.: Q(0)/(2*x) - 1/x, where Q(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + (1-x)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 08 2013
G.f.: W(0)/x - 1/x, where W(k) = 1 - x*(k+1)/( x*(k+2) - 1/(1 - x*(k+1)/( x*(k+1) - 1/W(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 25 2013
a(n) = hypergeometric([2, -n], [], -1). - Peter Luschny, Sep 20 2014
Upper and bottom right terms of the infinite 2 X 2 matrix product_{N=1,2,3,...} [(1,1); (1,N)]. - Gary W. Adamson, Jul 28 2016
a(n) = R(n,n+1,n) where R(x,y,z) is defined to be R(x+1,y,z+1) = R(y,x,x) + R(z,y,z), R(0,y,z+1) = R(z,y,z), R(x+1,y,0) = R(y,x,x), and R(0,y,0) = y. - David M. Cerna, Feb 16 2018
a(n) = (n + 1)!*hypergeom([-n], [-n-1], 1). - Peter Luschny, Nov 02 2018
a(n) = Integral_{x=0..1} (-LambertW(-1,-x/e))^n dx. - Gleb Koloskov, Jul 25 2021
|
|
EXAMPLE
|
G.f. = 1 + 3*x + 11*x^2 + 49*x^3 + 261*x^4 + 1631*x^5 + 11743*x^6 + 95901*x^7 + ...
a(2) = 11: {1, 12, 21, 13, 31, 123, 132, 213, 231, 312, 321}.
a(2) = 11 because we have 11 permutations of {1,2,3,4} (written in one line notation) that have an increasing subsequence beginning with 1 and ending with 4: 1,2,3,4; 1,2,4,3; 1,3,4,2; 1,4,2,3; 1,4,3,2; 2,1,3,4; 2,1,4,3; 2,3,1,4; 3,1,2,4; 3,1,4,2; 3,2,1,4. - Geoffrey Critzer, Feb 15 2013
|
|
MAPLE
|
a:=proc(n) options operator, arrow: factorial(n)*n*(3-(sum(1/(j*(j-1)*factorial(j)), j=2..n))) end proc: 1, seq(a(n), n=1..20); # Emeric Deutsch, Apr 12 2008
a := n -> hypergeom([2, -n], [], -1); seq(simplify(a(n)), n=0..18); # Peter Luschny, Sep 20 2014
|
|
MATHEMATICA
|
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[x] / (1 - x)^2, {x, 0, n}]] (* Michael Somos, Oct 20 2011 *)
|
|
PROG
|
(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp(x + x * O(x^n)) / (1 - x)^2, n))} /* Michael Somos, Mar 04 2004 */
(PARI) vector(20, n, n--; n!*sum(k=0, n, (n-k+1)/k!)) \\ G. C. Greubel, Jul 15 2019
(GAP) A001339:=List([0..20], n-> Sum([0..n], k-> Factorial(k+1)*Binomial(n, k))); # Muniru A Asiru, Feb 17 2018
(Magma) [Factorial(n)*(&+[(n-k+1)/Factorial(k): k in [0..n]]): n in [0..20]]; // G. C. Greubel, Jul 15 2019
(Sage) [factorial(n)*sum((n-k+1)/factorial(k) for k in (0..n)) for n in (0..20)] # G. C. Greubel, Jul 15 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Typo in description in 1995 Encyclopedia of Integer Sequences corrected Mar 15 1997
|
|
STATUS
|
approved
|
|
|
|