0,2

Number of arrangements of {1,2,...,n,n+1} containing the element 1. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 11 2001

Comments from Thomas Wieder (wieder.thomas(AT)t-online.de), Oct 21 2004: "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."

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 (callan(AT)stat.wisc.edu), Sep 20 2007

Row sums of triangle A137594. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 28 2008

Comments from Peter Bala (pbala@toucansurf.com), Jul 10 2008 (Start): 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.

Lim n -> infinity 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 remark by Deutsch above) since the rhs satisfies the above recurrence with the same initial conditions. Hence e = 3 - sum {k = 2..inf} 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)

J. L. Adams, Conceptual Blockbusting: A Guide to Better Ideas. Freeman, San Francisco, 1974.

Biondi, E.; Divieti, L.; Guardabassi, G.; Counting paths, circuits, chains, and cycles in graphs: A unified approach. Canad. J. Math. 22 1970 22-35.

M. J. Knight and W. O. Egerland, Solution to Problem 5911, Amer. Math. Monthly 81 (1974) 675-676.

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

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 400

Thomas Wieder, Home Page.

Thomas Wieder, (Old) Home Page.

F. Hivert, J.-C. Novelli and J.-Y. Thibon, Commutative combinatorial Hopf algebras

M. Hassani, Counting and computing by e

Weisstein, Eric W., Poisson-Charlier polynomial

E.g.f.: exp(x)*(1-x)^(-2). a(n) = round(evalf(exp(1)*(n-1)*(n-1)!)) (n>1).

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

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 5-th term of the 4-th binomial transform is 5^5: [1, 7, 51, 389, 3125, ..]. - Paul D. Hanna (pauldhanna(AT)juno.com), Nov 14 2003

G.f.: Sum_{k>=0} k!*(x/(1-x))^k. - Michael Somos Mar 04 2004

a(n) = Sum_{k = 0..n} A046716(n, k)*2^(n-k) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Jun 12 2004

(n-1)*a(n) = n^2*a(n-1)-1. - Vladeta Jovovic (vladeta(AT)Eunet.yu), Sep 04 2004

a(n) = Sum[P(n, k)*(k+1), {k, 0, n}]. - Ross La Haye (rlahaye(AT)new.rr.com), Aug 28 2005

a(n)=n!*n*[3 - Sum(1/(j(j-1)j!,j=2..n)] for n>=1. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Apr 12 2008

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

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 (deutsch(AT)duke.poly.edu), Apr 12 2008

(PARI) a(n)=if(n<0, 0, n!*polcoeff(exp(x+x*O(x^n))/(1-x)^2, n))

Cf. A001563. a(n)=A000522(n+1)-A000522(n).

Cf. A089900.

Cf. A064618.

First differences of A000522, A007526, A026243, A073591. Equals (1/2) A006183(n-2).

Equals A036918(n+1) + 1.

Cf. A137594.

Sequence in context: A025539 A074528 A004211 this_sequence A012316 A058733 A024333

Adjacent sequences: A001336 A001337 A001338 this_sequence A001340 A001341 A001342

nonn,new

njas

Typo in description in 1995 Encyc. Int. Seqs. corrected Mar 15, 1997.