|
|
A001286
|
|
Lah numbers: a(n) = (n-1)*n!/2.
(Formerly M4225 N1766)
|
|
70
|
|
|
1, 6, 36, 240, 1800, 15120, 141120, 1451520, 16329600, 199584000, 2634508800, 37362124800, 566658892800, 9153720576000, 156920924160000, 2845499424768000, 54420176498688000, 1094805903679488000, 23112569077678080000, 510909421717094400000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,2
|
|
COMMENTS
|
Number of surjections from {1,...,n} to {1,...,n-1}. - Benoit Cloitre, Dec 05 2003
First Eulerian transform of 0,1,2,3,4,... . - Ross La Haye, Mar 05 2005
With offset 0 : determinant of the n X n matrix m(i,j)=(i+j+1)!/i!/j!. - Benoit Cloitre, Apr 11 2005
These numbers arise when expressing n(n+1)(n+2)...(n+k)[n+(n+1)+(n+2)+...+(n+k)] as sums of squares: n(n+1)[n+(n+1)] = 6(1+4+9+16+ ... + n^2), n(n+1)(n+2)(n+(n+1)+(n+2)) = 36(1+(1+4)+(1+4+9)+...+(1+4+9+16+ ... + n^2)), n(n+1)(n+2)(n+3)(n+(n+1)+(n+2)+(n+3)) = 240(...), ... . - Alexander R. Povolotsky, Oct 16 2006
a(n) is the number of edges in the Hasse diagram for the weak Bruhat order on the symmetric group S_n. For permutations p,q in S_n, q covers p in the weak Bruhat order if p,q differ by an adjacent transposition and q has one more inversion than p. Thus 23514 covers 23154 due to the transposition that interchanges the third and fourth entries. Cf. A002538 for the strong Bruhat order. - David Callan, Nov 29 2007
a(n) is also the number of excedances in all permutations of {1,2,...,n} (an excedance of a permutation p is a value j such p(j)>j). Proof: j is exceeded (n-1)! times by each of the numbers j+1, j+2, ..., n; now, Sum_{j=1..n} (n-j)(n-1)! = n!(n-1)/2. Example: a(3)=6 because the number of excedances of the permutations 123, 132, 312, 213, 231, 321 are 0, 1, 1, 1, 2, 1, respectively. - Emeric Deutsch, Dec 15 2008
(-1)^(n+1)*a(n) is the determinant of the n X n matrix whose (i,j)-th element is 0 for i = j, is j-1 for j>i, and j for j < i. - Michel Lagneau, May 04 2010
a(n) is the total number of ascents (descents) over all n-permutations. a(n) = Sum_{k=1..n} A008292(n,k)*k. - Geoffrey Critzer, Jan 06 2013
For m>=4, a(m-2) is the number of Hamiltonian cycles in a simple graph with m vertices which is complete, except for one edge. Proof: think of distinct round-table seatings of m persons such that persons "1" and "2" may not be neighbors; the count is (m-3)(m-2)!/2. See also A001710. - Stanislav Sykora, Jun 17 2014
Popularity of left (right) children in treeshelves. Treeshelves are ordered binary (0-1-2) increasing trees where every child is connected to its parent by a left or a right link. Popularity is the sum of a certain statistic (number of left children, in this case) over all objects of size n. See A278677, A278678 or A278679 for more definitions and examples. See A008292 for the distribution of the left (right) children in treeshelves. - Sergey Kirgizov, Dec 24 2016
|
|
REFERENCES
|
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 90, ex. 4.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 156.
A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 44.
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).
|
|
LINKS
|
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Edge Count.
|
|
FORMULA
|
a(n) = Sum_{i=0..n-1} (-1)^(n-i-1) * i^n * binomial(n-1,i). - Yong Kong (ykong(AT)curagen.com), Dec 26 2000 [corrected by Amiram Eldar, May 02 2022]
a(n+1) = (-1)^(n+1)*det(M_n) where M_n is the n X n matrix M_(i,j)=max(i*(i+1)/2,j*(j+1)/2). - Benoit Cloitre, Apr 03 2004
If we define f(n,i,x) = Sum_{k=i..n} Sum_{j=i..k} binomial(k,j)*Stirling1(n,k)*Stirling2(j,i)*x^(k-j) then a(n)=(-1)^n*f(n,2,-2), (n>=2). - Milan Janjic, Mar 01 2009
a(n) = (n+1)!*Sum_{k=1..n-1} 1/(k^2+3*k+2). - Gary Detlefs, Sep 14 2011
a(n+1) = a(n)*n*(n+1)/(n-1). - Chai Wah Wu, Apr 11 2018
|
|
EXAMPLE
|
G.f. = x^2 + 6*x^3 + 36*x^4 + 240*x^5 + 1800*x^6 + 15120*x^7 + 141120*x^8 + ...
a(10) = (1+2+3+4+5+6+7+8+9)*(1*2*3*4*5*6*7*8*9) = 16329600. - Reinhard Zumkeller, May 15 2010
|
|
MAPLE
|
|
|
MATHEMATICA
|
nn=20; With[{a=Accumulate[Range[nn]], t=Range[nn]!}, Times@@@Thread[{a, t}]] (* Harvey P. Dale, Jan 26 2013 *)
|
|
PROG
|
(Sage) [(n-1)*factorial(n)/2 for n in range(2, 21)] # Zerinvary Lajos, May 16 2009
(Haskell)
a001286 n = sum[1..n-1] * product [1..n-1]
(Python)
from __future__ import division
for n in range(2, 100):
|
|
CROSSREFS
|
Cf. A001710, A052609, A062119, A075181, A060638, A060608, A060570, A060612, A135218, A019538, A053495, A051683, A213168, A278677, A278678, A278679, A008292.
A002868 is an essentially identical sequence.
Third column (m=2) of triangle |A111596(n, m)|: matrix product of |S1|.S2 Stirling number matrices.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|