login
a(n) = Sum_{k=0..n} (k+1)! binomial(n,k).
(Formerly M2901 N1164)
64

%I M2901 N1164 #205 Jul 17 2024 16:57:08

%S 1,3,11,49,261,1631,11743,95901,876809,8877691,98641011,1193556233,

%T 15624736141,220048367319,3317652307271,53319412081141,

%U 909984632851473,16436597430879731,313262209859119579,6282647653285676001,132266266384961600021,2916471173788403280463

%N a(n) = Sum_{k=0..n} (k+1)! binomial(n,k).

%C Number of arrangements of {1, 2, ..., n, n + 1} containing the element 1. - _Emeric Deutsch_, Oct 11 2001

%C From _Thomas Wieder_, Oct 21 2004: (Start)

%C "Also the number of hierarchies with unlabeled elements and labeled levels where the levels are permuted.

%C "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.

%C "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)

%C Polynomials in A010027 evaluated at 2.

%C 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

%C 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

%C Row sums of triangle A137594. - _Gary W. Adamson_, Jan 28 2008

%C From _Peter Bala_, Jul 10 2008: (Start)

%C 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.

%C 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).

%C 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).

%C 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.

%C Limit_{n->oo} a(n)/b(n) = e = 3 - 1/(4 - 2/(5 - 3/(6 - ... - n/((n + 3) - ...)))).

%C 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).

%C 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)

%C Binomial transform of n! Offset 1. a(3) = 11. - Al Hakanson (hawkuu(AT)gmail.com), May 18 2009

%C 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

%C Number of nonnegative integers which use each digit at most once in base n+1. - _Franklin T. Adams-Watters_, Oct 02 2011.

%C 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

%D A. Hordijk, Markov Decision Chains, pp. 97-103 in Images of SMC Research, 1996, Stichting Mathematisch Centrum, Amsterdam, Netherlands, 1996. See p. 103.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D W. A. Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 56, ex. 232.

%H Vincenzo Librandi, <a href="/A001339/b001339.txt">Table of n, a(n) for n = 0..200</a>

%H J. L. Adams, <a href="/A000522/a000522_1.pdf">Conceptual Blockbusting: A Guide to Better Ideas</a>, Freeman, San Francisco, 1974. [Annotated scans of pages 69 and 70 only]

%H Roland Bacher, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p7">Counting Packings of Generic Subsets in Finite Groups</a>, Electr. J. Combinatorics, 19 (2012), #P7.

%H Paul Barry, <a href="https://arxiv.org/abs/1804.06801">A note on number triangles that are almost their own production matrix</a>, arXiv:1804.06801 [math.CO], 2018.

%H E. Biondi, L. Divieti and G. Guardabassi, <a href="http://dx.doi.org/10.4153/CJM-1970-003-9">Counting paths, circuits, chains and cycles in graphs: A unified approach</a>, Canad. J. Math. 22 1970 22-35.

%H Philip Feinsilver and John McSorley, <a href="http://dx.doi.org/10.1155/2011/539030">Zeons, Permanents, the Johnson Scheme, and Generalized Derangements</a>, International Journal of Combinatorics, Volume 2011, Article ID 539030, 29 pages.

%H Loïc Foissy and Frédéric Patras, <a href="http://arxiv.org/abs/1205.2986">Natural endomorphisms of shuffle algebras</a>, arXiv preprint arXiv:1205.2986 [math.RA], 2012.

%H Hannah Golab, <a href="http://danaernst.com/scholarship/GolabThesis.pdf">Pattern avoidance in Cayley permutations</a>, Master's Thesis, Northern Arizona Univ. (2024). See p. 36.

%H M. Hassani, <a href="https://arxiv.org/abs/math/0606613">Counting and computing by e</a>, arXiv:math/0606613 [math.CO], 2006.

%H F. Hivert, J.-C. Novelli and J.-Y. Thibon, <a href="https://arxiv.org/abs/math/0605262">Commutative combinatorial Hopf algebras</a>, arXiv:math/0605262 [math.CO], 2006.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr==400">Encyclopedia of Combinatorial Structures 400</a>

%H M. J. Knight and W. O. Egerland, <a href="http://www.jstor.org/stable/2319238">Solution to Problem 5911</a>, Amer. Math. Monthly 81 (1974) 675-676.

%H Zhentao Lu, <a href="https://arxiv.org/abs/1907.05563">Elementary proofs of generalized continued fraction formulae for e</a>, arXiv:1907.05563 [math.NT], 2019.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Poisson-CharlierPolynomial.html">Poisson-Charlier polynomial</a>

%H Jun Yan, <a href="https://arxiv.org/abs/2404.07958">Results on pattern avoidance in parking functions</a>, arXiv:2404.07958 [math.CO], 2024. See p. 7.

%F E.g.f.: exp(x)/(1-x)^2.

%F a(n) = round(evalf(exp(1)*(n-1)*(n-1)!)) (n>1).

%F a(n) = floor(n*n!*e) + 1. - Melvin J. Knight (knightmj(AT)juno.com), May 30 2001

%F a(n) = {e*n*n!} for n > 0, where {x} denotes the nearest integer part. Proposed by _Simon Plouffe_, March 1993.

%F 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

%F G.f.: Sum_{k>=0} k! * (x / (1 - x))^k. - _Michael Somos_, Mar 04 2004

%F a(n) = Sum_{k = 0..n} A046716(n, k)*2^(n-k). - _Philippe Deléham_, Jun 12 2004

%F (n-1)*a(n) = n^2*a(n-1)-1. - _Vladeta Jovovic_, Sep 04 2004

%F a(n) = Sum_{k=0..n} P(n, k)*(k+1). - _Ross La Haye_, Aug 28 2005

%F a(n) = n!*n*(3 - Sum_{j=2..n} 1/(j*(j-1)*j!) for n>=1. - _Emeric Deutsch_, Apr 12 2008

%F 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

%F 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

%F 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

%F 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

%F 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

%F 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

%F 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

%F a(n) = hypergeometric([2, -n], [], -1). - _Peter Luschny_, Sep 20 2014

%F 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

%F 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

%F a(n) = (n + 1)!*hypergeom([-n], [-n-1], 1). - _Peter Luschny_, Nov 02 2018

%F a(n) = Integral_{x=0..1} (-LambertW(-1,-x/e))^n dx. - _Gleb Koloskov_, Jul 25 2021

%F a(n) = KummerU(-n, -n-1, 1). - _Peter Luschny_, May 10 2022

%e G.f. = 1 + 3*x + 11*x^2 + 49*x^3 + 261*x^4 + 1631*x^5 + 11743*x^6 + 95901*x^7 + ...

%e a(2) = 11: {1, 12, 21, 13, 31, 123, 132, 213, 231, 312, 321}.

%e 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

%p 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

%p a := n -> hypergeom([2, -n], [], -1); seq(simplify(a(n)), n=0..18); # _Peter Luschny_, Sep 20 2014

%t a[n_] := n!*Sum[(k+1)/(n-k)!, {k, 0, n}]; a /@ Range[0, 20] (* _Jean-François Alcover_, Jul 13 2011 *)

%t a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[x] / (1 - x)^2, {x, 0, n}]] (* _Michael Somos_, Oct 20 2011 *)

%o (PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp(x + x * O(x^n)) / (1 - x)^2, n))} /* _Michael Somos_, Mar 04 2004 */

%o (PARI) vector(20, n, n--; n!*sum(k=0,n,(n-k+1)/k!)) \\ _G. C. Greubel_, Jul 15 2019

%o (GAP) A001339:=List([0..20],n-> Sum([0..n], k-> Factorial(k+1)*Binomial(n,k))); # _Muniru A Asiru_, Feb 17 2018

%o (Magma) [Factorial(n)*(&+[(n-k+1)/Factorial(k): k in [0..n]]): n in [0..20]]; // _G. C. Greubel_, Jul 15 2019

%o (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

%Y Cf. A001563, A064618, A089900, A137594.

%Y a(n) = A000522(n+1) - A000522(n).

%Y First differences of A000522, A007526, A026243, A073591.

%Y Equals (1/2)*A006183(n-2).

%Y Equals A036918(n+1) + 1.

%Y Leftmost column of A276588.

%Y Cf. also A136104.

%K nonn

%O 0,2

%A _N. J. A. Sloane_

%E Typo in description in 1995 Encyclopedia of Integer Sequences corrected Mar 15 1997

%E Link updated by _Susanne Wienand_, Nov 19 2011