Displaying 1-10 of 124 results found.
page
1
2
3
4
5
6
7
8
9
10
... 13
Numerator of ratio (the denominator being (n-1)!^2 = A001044(n-1)) giving the probability that the last of n persons drawing names randomly from a set of names draws their own, given that each person previously has drawn in succession and did not keep their own name. (Probability of derangements when allocated / rejected sequentially.)
+20
4
1, 0, 1, 5, 76, 1624, 52116, 2298708, 133929216, 9961180416, 921248743680, 103715841415680, 13967643016085760, 2217449301162071040, 409861043056032503040, 87262626872384643052800, 21202798521768886355558400, 5831660090586059239329792000, 1802587564536011525042697830400
COMMENTS
In "Secret Santa", if a person picks their own name, they pick another name and they throw their own name back in. If the last person draws their own name, there's a problem. What is that probability as a function of the number of people participating?
FORMULA
Sum of H(i, N-2) * X(i, N-2) for i=0..2^(N-3), N is the number of people and H(r,c) = sum of H(T(r),L(r)+j) * M(c-T(r)-1,j) for j = 0..c-L(r)-1 and X(r,c) = product of (3 + k - b(r,k)) for k = 0..(c-2) and M(y,z) = binomial distribution (y,z) when y - 1 > z and (y,z)-1 when (y-1)<=z and b(r,k) = bit k of r in base 2 and T(r) = A053645 and L(r) = A000523.
EXAMPLE
If there is one person, the chance of the last person getting their own name is 100%, or 1 over 0!^2. For 2 people, it is 0 / 1!^2. For 3 people, it is 1 / 2!^2, creating a more interesting case. The possible drawings are {2,1,3}, {2,3,1} and {3,1,2}. All other drawings can't happen because the name is rejected and redrawn. But these 3 outcomes don't have equal probability, rather, they are 25%, 25% and 50% respectively. The first outcome is the only one in which the last person draws their own name. The first person has a 50% chance of drawing a 2 or 3. If 2, the second person has a 50% chance of drawing 1 or 3, for a total outcome probability of 1/4. Similarly with 4 people, the chance is 5/36, followed by 76/576 for 5 people, etc. For the case of 5 people, the above equations boil down to this end calculation: {1,5,2,1} * {12,8,9,6} summed, or 12 + 40 + 18 + 6 = 76.
MATHEMATICA
maxP = 22;
rows = Range[1, 2^(nP = maxP - 3)];
pasc = Table[
Binomial[p + 1, i] - If[i >= p, 1, 0], {p, nP}, {i, 0, p}];
sFreq = Table[0, {maxP - 1}, {2^nP}]; sFreq[[2 ;; maxP - 1, 1]] = 1;
For[p = 1, p <= nP, p++,
For[s = 1, s <= p, s++, rS = Range[2^(s - 1) + 1, 2^s];
sFreq[[p + 2, rS]] = pasc[[p + 1 - s, 1 ;; p + 2 - s]] .
sFreq[[s ;; p + 1, 1 ;; 2^(s - 1)]]]];
sProb = Table[p + 2 - BitGet[rows - 1, p - 1], {p, nP}];
sProb = Table[Product[sProb[[i]], {i, p}], {p, nP}]*
Table[If[r <= 2^p, 1, 0],
{p, nP}, {r, rows}];
rslt = Flatten[
Prepend[Table[sProb[[p]] . sFreq[[p + 2]], {p, nP}], {1, 0, 1}]]
prob = N[rslt/Array[(#1 - 1)!^2 & , maxP]] (* Brian Parsonnet, Feb 22 2011 *)
CROSSREFS
The sequence frequency table (sFreq) is A136301.
First series of Hankel determinants based on A001044(n)=(n!)^2 : a(n)=det( A001044(i+j-2))=det(((i+j-2)!)^2), i,j=1,2...n. Hankel transform of A001044.
+20
2
1, 3, 656, 58910976, 7213311014731776, 3024546589156405495726080000, 9172616430046109813423337553212211200000000
COMMENTS
It would be highly desirable to obtain a closed form for a(n).
MATHEMATICA
nmax = 15; Table[Det[Table[((i+j-2)!)^2, {i, 1, k}, {j, 1, k}]], {k, 1, nmax}] (* Vaclav Kotesovec, Feb 24 2019 *)
Second series of Hankel determinants based on A001044(n+1)=((n+1)!)^2 : a(n)=det( A001044(i+j-1))=det(((i+j-1)!)^2), i,j=1,2...n. Hankel transform of A001044(n+1).
+20
2
1, 20, 75456, 222049714176, 1446859308630697574400, 47680530046593302430474043392000000, 15747911603441625571224989926437024694272000000000000
COMMENTS
It would be highly desirable to obtain a closed form for a(n).
MATHEMATICA
nmax = 10; Table[Det[Table[((i+j-1)!)^2, {i, 1, k}, {j, 1, k}]], {k, 1, nmax}] (* Vaclav Kotesovec, Feb 24 2019 *)
Self-convolution of squares of factorial numbers ( A001044).
+20
1
1, 2, 9, 80, 1240, 30240, 1071504, 51996672, 3307723776, 266872320000, 26615381760000, 3214252921651200, 462189467175321600, 78024380924038348800, 15279632043682406400000, 3435553774431004262400000, 879010223384483132866560000, 253916900613208108255150080000
COMMENTS
a(n) = (n!)^2 * Sum_{i=0..n} (binomial(n,i)^(-2)).
Consider a triangle ABC with area p. Let points X, Y, Z be randomly and uniformly chosen on sides BC, CA, BA. Let r = area of XYZ. Then the average or expected value of (r/p)^n = a(n)/(n!^2 * (n+1)^3).
a(n) = (3*(n+1)^4 *(n!)^4 /(2n+3)!) * Sum_{i=1..n+1} ((1/i)* binomial(2i, i)), see Sprugnoli Formula 5.2 as noted by Markus Scheuer.
FORMULA
a(n) = Sum_{i=0..n} (i! * (n-i)!)^2.
MATHEMATICA
Table[Sum[(k!*(n-k)!)^2, {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Dec 05 2016 *)
0, 0, 2, 23, 471, 14189, 597257, 33501237, 2415131467, 217579283654, 23953174092058, 3163948015772640, 493855720249671680, 89925233867931779072, 18892189483975198113792, 4535777807395775857033216
MATHEMATICA
Table[Round[N[(n!)^2 - 2*Pi*n*E^(-2*n)*n^(2*n)]], {n, 1, 100}]
Factorial numbers: n! = 1*2*3*4*...*n (order of symmetric group S_n, number of permutations of n letters).
(Formerly M1675 N0659)
+10
2886
1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000, 51090942171709440000, 1124000727777607680000
COMMENTS
The earliest publication that discusses this sequence appears to be the Sepher Yezirah [Book of Creation], circa AD 300. (See Knuth, also the Zeilberger link.) - N. J. A. Sloane, Apr 07 2014 For n >= 1, a(n) is the number of n X n (0,1) matrices with each row and column containing exactly one entry equal to 1.
This sequence is the BinomialMean transform of A000354. (See A075271 for definition.) - John W. Layman, Sep 12 2002 [This is easily verified from the Paul Barry formula for A000354, by interchanging summations and using the formula: Sum_k (-1)^k C(n-i, k) = KroneckerDelta(i,n). - David Callan, Aug 31 2003] Number of distinct subsets of T(n-1) elements with 1 element A, 2 elements B, ..., n - 1 elements X (e.g., at n = 5, we consider the distinct subsets of ABBCCCDDDD and there are 5! = 120). - Jon Perry, Jun 12 2003 n! is the smallest number with that prime signature. E.g., 720 = 2^4 * 3^2 * 5. - Amarnath Murthy, Jul 01 2003 a(n) is the permanent of the n X n matrix M with M(i, j) = 1. - Philippe Deléham, Dec 15 2003 Given n objects of distinct sizes (e.g., areas, volumes) such that each object is sufficiently large to simultaneously contain all previous objects, then n! is the total number of essentially different arrangements using all n objects. Arbitrary levels of nesting of objects are permitted within arrangements. (This application of the sequence was inspired by considering leftover moving boxes.) If the restriction exists that each object is able or permitted to contain at most one smaller (but possibly nested) object at a time, the resulting sequence begins 1,2,5,15,52 (Bell Numbers?). Sets of nested wooden boxes or traditional nested Russian dolls come to mind here. - Rick L. Shepherd, Jan 14 2004 Stirling transform of [2, 2, 6, 24, 120, ...] is A052856 = [2, 2, 4, 14, 76, ...]. Stirling transform of [1, 2, 6, 24, 120, ...] is A000670 = [1, 3, 13, 75, ...]. Stirling transform of [0, 2, 6, 24, 120, ...] is A052875 = [0, 2, 12, 74, ...]. Stirling transform of [1, 1, 2, 6, 24, 120, ...] is A000629 = [1, 2, 6, 26, ...]. Stirling transform of [0, 1, 2, 6, 24, 120, ...] is A002050 = [0, 1, 5, 25, 140, ...]. Stirling transform of ( A165326* A089064)(1...) = [1, 0, 1, -1, 8, -26, 194, ...] is [1, 1, 2, 6, 24, 120, ...] (this sequence). (End) First Eulerian transform of 1, 1, 1, 1, 1, 1... The first Eulerian transform transforms a sequence s to a sequence t by the formula t(n) = Sum_{k=0..n} e(n, k)s(k), where e(n, k) is a first-order Eulerian number [ A008292]. - Ross La Haye, Feb 13 2005 Conjecturally, 1, 6, and 120 are the only numbers which are both triangular and factorial. - Christopher M. Tomaszewski (cmt1288(AT)comcast.net), Mar 30 2005
n! is the n-th finite difference of consecutive n-th powers. E.g., for n = 3, [0, 1, 8, 27, 64, ...] -> [1, 7, 19, 37, ...] -> [6, 12, 18, ...] -> [6, 6, ...]. - Bryan Jacobs (bryanjj(AT)gmail.com), Mar 31 2005
a(n+1) = (n+1)! = 1, 2, 6, ... has e.g.f. 1/(1-x)^2. - Paul Barry, Apr 22 2005 Write numbers 1 to n on a circle. Then a(n) = sum of the products of all n - 2 adjacent numbers. E.g., a(5) = 1*2*3 + 2*3*4 + 3*4*5 + 4*5*1 +5*1*2 = 120. - Amarnath Murthy, Jul 10 2005 The number of chains of maximal length in the power set of {1, 2, ..., n} ordered by the subset relation. - Rick L. Shepherd, Feb 05 2006 The number of circular permutations of n letters for n >= 0 is 1, 1, 1, 2, 6, 24, 120, 720, 5040, 40320, ... - Xavier Noria (fxn(AT)hashref.com), Jun 04 2006
a(n) is the number of deco polyominoes of height n (n >= 1; see definitions in the Barcucci et al. references). - Emeric Deutsch, Aug 07 2006 a(n) is the number of partition tableaux of size n. See Steingrimsson/Williams link for the definition. - David Callan, Oct 06 2006 Consider the n! permutations of the integer sequence [n] = 1, 2, ..., n. The i-th permutation consists of ncycle(i) permutation cycles. Then, if the Sum_{i=1..n!} 2^ncycle(i) runs from 1 to n!, we have Sum_{i=1..n!} 2^ncycle(i) = (n+1)!. E.g., for n = 3 we have ncycle(1) = 3, ncycle(2) = 2, ncycle(3) = 1, ncycle(4) = 2, ncycle(5) = 1, ncycle(6) = 2 and 2^3 + 2^2 + 2^1 + 2^2 + 2^1 + 2^2 = 8 + 4 + 2 + 4 + 2 + 4 = 24 = (n+1)!. - Thomas Wieder, Oct 11 2006 a(n) is the number of set partitions of {1, 2, ..., 2n - 1, 2n} into blocks of size 2 (perfect matchings) in which each block consists of one even and one odd integer. For example, a(3) = 6 counts 12-34-56, 12-36-45, 14-23-56, 14-25-36, 16-23-45, 16-25-34. - David Callan, Mar 30 2007 Consider the multiset M = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...] = [1, 2, 2, ..., n x 'n'] and form the set U (where U is a set in the strict sense) of all subsets N (where N may be a multiset again) of M. Then the number of elements |U| of U is equal to (n+1)!. E.g. for M = [1, 2, 2] we get U = [[], [2], [2, 2], [1], [1, 2], [1, 2, 2]] and |U| = 3! = 6. This observation is a more formal version of the comment given already by Rick L. Shepherd, Jan 14 2004. - Thomas Wieder, Nov 27 2007 For n >= 1, a(n) = 1, 2, 6, 24, ... are the positions corresponding to the 1's in decimal expansion of Liouville's constant ( A012245). - Paul Muljadi, Apr 15 2008 Triangle A144107 has n! for row sums (given n > 0) with right border n! and left border A003319, the INVERTi transform of (1, 2, 6, 24, ...). - Gary W. Adamson, Sep 11 2008 a(n) is also the number of order-decreasing full transformations (of an n-chain).
a(n-1) is also the number of nilpotent order-decreasing full transformations (of an n-chain). (End)
n! is also the number of optimal broadcast schemes in the complete graph K_{n}, equivalent to the number of binomial trees embedded in K_{n} (see Calin D. Morosan, Information Processing Letters, 100 (2006), 188-193). - Calin D. Morosan (cd_moros(AT)alumni.concordia.ca), Nov 28 2008
Let S_{n} denote the n-star graph. The S_{n} structure consists of n S_{n-1} structures. This sequence gives the number of edges between the vertices of any two specified S_{n+1} structures in S_{n+2} (n >= 1). - K.V.Iyer, Mar 18 2009 Chromatic invariant of the sun graph S_{n-2}.
It appears that a(n+1) is the inverse binomial transform of A000255. - Timothy Hopper (timothyhopper(AT)hotmail.co.uk), Aug 20 2009 a(n) is also the determinant of a square matrix, An, whose coefficients are the reciprocals of beta function: a{i, j} = 1/beta(i, j), det(An) = n!. - Enrique Pérez Herrero, Sep 21 2009 The asymptotic expansions of the exponential integrals E(x, m = 1, n = 1) ~ exp(-x)/x*(1 - 1/x + 2/x^2 - 6/x^3 + 24/x^4 + ...) and E(x, m = 1, n = 2) ~ exp(-x)/x*(1 - 2/x + 6/x^2 - 24/x^3 + ...) lead to the factorial numbers. See A163931 and A130534 for more information. - Johannes W. Meijer, Oct 20 2009 a(n) = G^n where G is the geometric mean of the first n positive integers. - Jaroslav Krizek, May 28 2010 Increasing colored 1-2 trees with choice of two colors for the rightmost branch of nonleaves. - Wenjin Woan, May 23 2011 The sequence 1!, (2!)!, ((3!)!)!, (((4!)!)!)!, ..., ((...(n!)!)...)! (n times) grows too rapidly to have its own entry. See Hofstadter.
The e.g.f. of 1/a(n) = 1/n! is BesselI(0, 2*sqrt(x)). See Abramowitz-Stegun, p. 375, 9.3.10. - Wolfdieter Lang, Jan 09 2012 Number of permutations of elements 1, 2, ..., n + 1 with a fixed element belonging to a cycle of length r does not depend on r and equals a(n). - Vladimir Shevelev, May 12 2012 a(n) is the number of fixed points in all permutations of 1, ..., n: in all n! permutations, 1 is first exactly (n-1)! times, 2 is second exactly (n-1)! times, etc., giving (n-1)!*n = n!. - Jon Perry, Dec 20 2012 For m >= 3, a(m-2) is the number hp(m) of acyclic Hamiltonian paths in a simple graph with m vertices, which is complete except for one missing edge. For m < 3, hp(m)=0. - Stanislav Sykora, Jun 17 2014 a(n) is the number of increasing forests with n nodes. - Brad R. Jones, Dec 01 2014 The factorial numbers can be calculated by means of the recurrence n! = (floor(n/2)!)^2 * sf(n) where sf(n) are the swinging factorials A056040. This leads to an efficient algorithm if sf(n) is computed via prime factorization. For an exposition of this algorithm see the link below. - Peter Luschny, Nov 05 2016 Treeshelves are ordered (plane) binary (0-1-2) increasing trees where the nodes of outdegree 1 come in 2 colors. There are n! treeshelves of size n, and classical Françon's bijection maps bijectively treeshelves into permutations. - Sergey Kirgizov, Dec 26 2016 Satisfies Benford's law [Diaconis, 1977; Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017 a(n) = Sum((d_p)^2), where d_p is the number of standard tableaux in the Ferrers board of the integer partition p and summation is over all integer partitions p of n. Example: a(3) = 6. Indeed, the partitions of 3 are [3], [2,1], and [1,1,1], having 1, 2, and 1 standard tableaux, respectively; we have 1^2 + 2^2 + 1^2 = 6. - Emeric Deutsch, Aug 07 2017 a(n) is the n-th derivative of x^n. - Iain Fox, Nov 19 2017 a(n) is the number of maximum chains in the n-dimensional Boolean cube {0,1}^n in respect to the relation "precedes". It is defined as follows: for arbitrary vectors u, v of {0,1}^n, such that u = (u_1, u_2, ..., u_n) and v = (v_1, v_2, ..., v_n), "u precedes v" if u_i <= v_i, for i=1, 2, ..., n. - Valentin Bakoev, Nov 20 2017 a(n) is the number of shortest paths (for example, obtained by Breadth First Search) between the nodes (0,0,...,0) (i.e., the all-zeros vector) and (1,1,...,1) (i.e., the all-ones vector) in the graph H_n, corresponding to the n-dimensional Boolean cube {0,1}^n. The graph is defined as H_n = (V_n, E_n), where V_n is the set of all vectors of {0,1}^n, and E_n contains edges formed by each pair adjacent vectors. - Valentin Bakoev, Nov 20 2017 a(n) is also the determinant of the symmetric n X n matrix M defined by M(i,j) = sigma(gcd(i,j)) for 1 <= i,j <= n. - Bernard Schott, Dec 05 2018 a(n) is also the number of inversion sequences of length n. A length n inversion sequence e_1, e_2, ..., e_n is a sequence of n integers such that 0 <= e_i < i. - Juan S. Auli, Oct 14 2019 The term "factorial" ("factorielle" in French) was coined by the French mathematician Louis François Antoine Arbogast (1759-1803) in 1800. The notation "!" was first used by the French mathematician Christian Kramp (1760-1826) in 1808. - Amiram Eldar, Apr 16 2021 Also the number of signotopes of rank 2, i.e., mappings X:{{1..n} choose 2}->{+,-} such that for any three indices a < b < c, the sequence X(a,b), X(a,c), X(b,c) changes its sign at most once (see Felsner-Weil reference). - Manfred Scheucher, Feb 09 2022 a(n) is also the number of labeled commutative semisimple rings with n elements. As an example the only commutative semisimple rings with 4 elements are F_4 and F_2 X F_2. They both have exactly 2 automorphisms, hence a(4)=24/2+24/2=24. - Paul Laubie, Mar 05 2024 a(n) is the number of extremely unlucky Stirling permutations of order n+1; i.e., the number of Stirling permutations of order n+1 that have exactly one lucky car. - Bridget Tenner, Apr 09 2024
REFERENCES
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 833.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 125; also p. 90, ex. 3.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §4.1 Symbols Galore, p. 106.
Douglas R. Hofstadter, Fluid concepts & creative analogies: computer models of the fundamental mechanisms of thought, Basic Books, 1995, pages 44-46.
A. N. Khovanskii. The Application of Continued Fractions and Their Generalizations to Problem in Approximation Theory. Groningen: Noordhoff, Netherlands, 1963. See p. 141 (10.19).
D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 5.1.2, p. 23. [From N. J. A. Sloane, Apr 07 2014] J.-M. De Koninck and A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Problème 693 pp. 90, 297, Ellipses Paris 2004.
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.
R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976).
Sepher Yezirah [Book of Creation], circa AD 300. See verse 52.
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).
Jerome Spanier and Keith B. Oldham, "Atlas of Functions", Hemisphere Publishing Corp., 1987, chapter 2, pages 19-24.
D. Stanton and D. White, Constructive Combinatorics, Springer, 1986; see p. 91.
Carlo Suares, Sepher Yetsira, Shambhala Publications, 1976. See verse 52.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1987, pp. 102.
LINKS
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]. Laura Colmenarejo, Aleyah Dawkins, Jennifer Elder, Pamela E. Harris, Kimberly J. Harry, Selvi Kara, Dorian Smith, and Bridget Eileen Tenner, On the lucky and displacement statistics of Stirling permutations, arXiv:2403.03280 [math.CO], 2024.
FORMULA
Sum_{i=0..n} (-1)^i * i^n * binomial(n, i) = (-1)^n * n!. - Yong Kong (ykong(AT)curagen.com), Dec 26 2000
Sum_{i=0..n} (-1)^i * (n-i)^n * binomial(n, i) = n!. - Peter C. Heinig (algorithms(AT)gmx.de), Apr 10 2007
The sequence trivially satisfies the recurrence a(n+1) = Sum_{k=0..n} binomial(n,k) * a(k)*a(n-k). - Robert FERREOL, Dec 05 2009 D-finite with recurrence: a(n) = n*a(n-1), n >= 1. n! ~ sqrt(2*Pi) * n^(n+1/2) / e^n (Stirling's approximation).
a(0) = 1, a(n) = subs(x = 1, (d^n/dx^n)(1/(2-x))), n = 1, 2, ... - Karol A. Penson, Nov 12 2001 a(n) = Sum_{k=0..n} (-1)^(n-k)* A000522(k)*binomial(n, k) = Sum_{k=0..n} (-1)^(n-k)*(x+k)^n*binomial(n, k). - Philippe Deléham, Jul 08 2004 a(n) = Sum_{i=1..n} ((-1)^(i-1) * sum of 1..n taken n - i at a time) - e.g., 4! = (1*2*3 + 1*2*4 + 1*3*4 + 2*3*4) - (1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4) + (1 + 2 + 3 + 4) - 1 = (6 + 8 + 12 + 24) - (2 + 3 + 4 + 6 + 8 + 12) + 10 - 1 = 50 - 35 + 10 - 1 = 24. - Jon Perry, Nov 14 2005 a(n) = (n-1)*(a(n-1) + a(n-2)), n >= 2. - Matthew J. White, Feb 21 2006
1 / a(n) = determinant of matrix whose (i,j) entry is (i+j)!/(i!(j+1)!) for n > 0. This is a matrix with Catalan numbers on the diagonal. - Alexander Adamchuk, Jul 04 2006 For n >= 2, a(n-2) = (-1)^n*Sum_{j=0..n-1} (j+1)*Stirling1(n,j+1). - Milan Janjic, Dec 14 2008 G.f.: 1/(1-x-x^2/(1-3x-4x^2/(1-5x-9x^2/(1-7x-16x^2/(1-9x-25x^2... (continued fraction), hence Hankel transform is A055209. G.f. of (n+1)! is 1/(1-2x-2x^2/(1-4x-6x^2/(1-6x-12x^2/(1-8x-20x^2... (continued fraction), hence Hankel transform is A059332. (End) a(n) = Product_{p prime} p^(Sum_{k > 0} floor(n/p^k)) by Legendre's formula for the highest power of a prime dividing n!. - Jonathan Sondow, Jul 24 2009 It appears that a(n) = (1/0!) + (1/1!)*n + (3/2!)*n*(n-1) + (11/3!)*n*(n-1)*(n-2) + ... + (b(n)/n!)*n*(n-1)*...*2*1, where a(n) = (n+1)! and b(n) = A000255. - Timothy Hopper, Aug 12 2009 a(n) = A_{n}(1) where A_{n}(x) are the Eulerian polynomials. - Peter Luschny, Aug 03 2010 a(n) = n*(2*a(n-1) - (n-1)*a(n-2)), n > 1. - Gary Detlefs, Sep 16 2010 1/a(n) = -Sum_{k=1..n+1} (-2)^k*(n+k+2)*a(k)/(a(2*k+1)*a(n+1-k)). - Groux Roland, Dec 08 2010 a(n) = Product_{p prime, p <= n} p^(Sum_{i >= 1} floor(n/p^i)).
The infinitary analog of this formula is: a(n) = Product_{q terms of A050376 <= n} q^((n)_q), where (n)_q denotes the number of those numbers <= n for which q is an infinitary divisor (for the definition see comment in A037445). (End) The terms are the denominators of the expansion of sinh(x) + cosh(x). - Arkadiusz Wesolowski, Feb 03 2012 G.f.: 1 / (1 - x / (1 - x / (1 - 2*x / (1 - 2*x / (1 - 3*x / (1 - 3*x / ... )))))). - Michael Somos, May 12 2012 G.f. 1 + x/(G(0)-x) where G(k) = 1 - (k+1)*x/(1 - x*(k+2)/G(k+1)); (continued fraction, 2-step). - Sergei N. Gladkovskii, Aug 14 2012 G.f.: W(1,1;-x)/(W(1,1;-x) - x*W(1,2;-x)), where W(a,b,x) = 1 - a*b*x/1! + a*(a+1)*b*(b+1)*x^2/2! - ... + a*(a+1)*...*(a+n-1)*b*(b+1)*...*(b+n-1)*x^n/n! + ...; see [A. N. Khovanskii, p. 141 (10.19)]. - Sergei N. Gladkovskii, Aug 15 2012 G.f.: A(x) = 1 + x/(G(0) - x) where G(k) = 1 + (k+1)*x - x*(k+2)/G(k+1); (continued fraction).
Let B(x) be the g.f. for A051296, then A(x) = 2 - 1/B(x). (End) G.f.: 1 + x*(G(0) - 1)/(x-1) where G(k) = 1 - (2*k+1)/(1-x/(x - 1/(1 - (2*k+2)/(1-x/(x - 1/G(k+1) ))))); (continued fraction). - Sergei N. Gladkovskii, Jan 15 2013 G.f.: 1 + x*(1 - G(0))/(sqrt(x)-x) where G(k) = 1 - (k+1)*sqrt(x)/(1-sqrt(x)/(sqrt(x)-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 25 2013 G.f.: 1 + x/G(0) where G(k) = 1 - x*(k+2)/( 1 - x*(k+1)/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 23 2013 a(n) = det(S(i+1, j), 1 <= i, j <=n ), where S(n,k) are Stirling numbers of the second kind. - Mircea Merca, Apr 04 2013 G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 24 2013 G.f.: 2/G(0), where G(k) = 1 + 1/(1 - 1/(1 - 1/(2*x*(k+1)) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 29 2013 G.f.: G(0), where G(k) = 1 + x*(2*k+1)/(1 - x*(2*k+2)/(x*(2*k+2) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 07 2013 a(n) = P(n-1, floor(n/2)) * floor(n/2)! * (n - (n-2)*((n+1) mod 2)), where P(n, k) are the k-permutations of n objects, n > 0. - Wesley Ivan Hurt, Jun 07 2013 G.f.: 1 + x/Q(0), m=+2, where Q(k) = 1 - 2*x*(2*k+1) - m*x^2*(k+1)*(2*k+1)/( 1 - 2*x*(2*k+2) - m*x^2*(k+1)*(2*k+3)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Sep 24 2013 a(n) = round(Sum_{k>=1} log(k)^n/k^2), for n>=1, which is related to the n-th derivative of the Riemann zeta function at x=2 as follows: round((-1)^n * zeta^(n)(2)). Also see A073002. - Richard R. Forberg, Dec 30 2014 a(n) ~ Sum_{j>=0} j^n/e^j, where e = A001113. When substituting a generic variable for "e" this infinite sum is related to Eulerian polynomials. See A008292. This approximation of n! is within 0.4% at n = 2. See A255169. Accuracy, as a percentage, improves rapidly for larger n. - Richard R. Forberg, Mar 07 2015 a(n) = Product_{k=1..n} (C(n+1, 2)-C(k, 2))/(2*k-1); see Masanori Ando link. - Michel Marcus, Apr 17 2015 Sum_{n>=0} a(n)/(a(n + 1)*a(n + 2)) = Sum_{n>=0} 1/((n + 2)*(n + 1)^2*a(n)) = 2 - exp(1) - gamma + Ei(1) = 0.5996203229953..., where gamma = A001620, Ei(1) = A091725. - Ilya Gutkovskiy, Nov 01 2016 a(2^n) = 2^(2^n - 1) * 1!! * 3!! * 7!! * ... * (2^n - 1)!!. For example, 16! = 2^15*(1*3)*(1*3*5*7)*(1*3*5*7*9*11*13*15) = 20922789888000. - Peter Bala, Nov 01 2016 a(n) = sum(prod(B)), where the sum is over all subsets B of {1,2,...,n-1} and where prod(B) denotes the product of all the elements of set B. If B is a singleton set with element b, then we define prod(B)=b, and, if B is the empty set, we define prod(B) to be 1. For example, a(4)=(1*2*3)+(1*2)+(1*3)+(2*3)+(1)+(2)+(3)+1=24. - Dennis P. Walsh, Oct 23 2017 Sum_{n >= 0} 1/(a(n)*(n+2)) = 1. - Multiplying the denominator by (n+2) in Jaume Oliver Lafont's entry above creates a telescoping sum. - Fred Daniel Kline, Nov 08 2020 O.g.f.: Sum_{k >= 0} k!*x^k = Sum_{k >= 0} (k+y)^k*x^k/(1 + (k+y)*x)^(k+1) for arbitrary y. - Peter Bala, Mar 21 2022 E.g.f.: 1/(1 + LambertW(-x*exp(-x))) = 1/(1-x), see A258773. -(1/x)*substitute(z = x*exp(-x), z*(d/dz)LambertW(-z)) = 1/(1 - x). See A075513. Proof: Use the compositional inverse (x*exp(-x))^[-1] = -LambertW(-z). See A000169 or A152917, and Richard P. Stanley: Enumerative Combinatorics, vol. 2, p. 37, eq. (5.52). - Wolfdieter Lang, Oct 17 2022 1/a(n) = (e/(2*Pi*n)*Integral_{x=-oo..oo} cos(x-n*arctan(x))/(1+x^2)^(n/2) dx). Proof: take the real component of Laplace's integral for 1/Gamma(x).
a(n) = Integral_{x=0..1} e^(-t)*LerchPhi(1/e, -n, t) dt. Proof: use the relationship Gamma(x+1) = Sum_{n >= 0} Integral_{t=n..n+1} e^(-t)t^x dt = Sum_{n >= 0} Integral_{t=0..1} e^(-(t+n))(t+n)^x dt and interchange the order of summation and integration.
Conjecture: a(n) = 1/(2*Pi)*Integral_{x=-oo..oo}(n+i*x+1)!/(i*x+1)-(n+i*x-1)!/(i*x-1)dx. (End)
a(n) = e^(Integral_{x=1..n+1} Psi(x) dx) where Psi(x) is the digamma function. - Andrea Pinos, Jan 10 2024 a(n) = Integral_{x=0..oo} e^(-x^(1/n)) dx, for n > 0. - Ridouane Oudra, Apr 20 2024
EXAMPLE
There are 3! = 1*2*3 = 6 ways to arrange 3 letters {a, b, c}, namely abc, acb, bac, bca, cab, cba.
Let n = 2. Consider permutations of {1, 2, 3}. Fix element 3. There are a(2) = 2 permutations in each of the following cases: (a) 3 belongs to a cycle of length 1 (permutations (1, 2, 3) and (2, 1, 3)); (b) 3 belongs to a cycle of length 2 (permutations (3, 2, 1) and (1, 3, 2)); (c) 3 belongs to a cycle of length 3 (permutations (2, 3, 1) and (3, 1, 2)). - Vladimir Shevelev, May 13 2012 G.f. = 1 + x + 2*x^2 + 6*x^3 + 24*x^4 + 120*x^5 + 720*x^6 + 5040*x^7 + ...
MAPLE
A000142 := n -> n!; seq(n!, n=0..20);
spec := [ S, {S=Sequence(Z) }, labeled ]; seq(combstruct[count](spec, size=n), n=0..20);
# Maple program for computing cycle indices of symmetric groups
M:=6: f:=array(0..M): f[0]:=1: print(`n= `, 0); print(f[0]); f[1]:=x[1]: print(`n= `, 1); print(f[1]); for n from 2 to M do f[n]:=expand((1/n)*add( x[l]*f[n-l], l=1..n)); print(`n= `, n); print(f[n]); od:
with(combstruct):ZL0:=[S, {S=Set(Cycle(Z, card>0))}, labeled]: seq(count(ZL0, size=n), n=0..20); # Zerinvary Lajos, Sep 26 2007
MATHEMATICA
RecurrenceTable[{a[n] == n*a[n - 1], a[0] == 1}, a, {n, 0, 22}] (* Ray Chandler, Jul 30 2015 *)
PROG
(Axiom) [factorial(n) for n in 0..10]
(Magma) a:= func< n | Factorial(n) >; [ a(n) : n in [0..10]];
(Haskell)
a000142 :: (Enum a, Num a, Integral t) => t -> a
a000142 n = product [1 .. fromIntegral n]
a000142_list = 1 : zipWith (*) [1..] a000142_list
(Python)
for i in range(1, 1000):
y = i
for j in range(1, i):
y *= i - j
print(y, "\n")
(Python)
import math
for i in range(1, 1000):
math.factorial(i)
print("")
(Scala) (1: BigInt).to(24: BigInt).scanLeft(1: BigInt)(_ * _) // Alonso del Arte, Mar 02 2019 (Julia) print([factorial(big(n)) for n in 0:28]) # Paul Muljadi, May 01 2024
CROSSREFS
Cf. A000165, A001044, A001563, A003422, A009445, A010050, A012245, A033312, A034886, A038507, A047920, A048631. Factorial base representation: A007623. Cf. A001013 (multiplicative closure). For factorials with initial digit d (1 <= d <= 9) see A045509, A045510, A045511, A045516, A045517, A045518, A282021, A045519; A045520, A045521, A045522, A045523, A045524, A045525, A045526, A045527, A045528, A045529.
KEYWORD
core,easy,nonn,nice,changed
Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.
(Formerly M1645 N0643)
+10
1083
1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156, 10400600, 40116600, 155117520, 601080390, 2333606220, 9075135300, 35345263800, 137846528820, 538257874440, 2104098963720, 8233430727600, 32247603683100, 126410606437752, 495918532948104, 1946939425648112
COMMENTS
Devadoss refers to these numbers as type B Catalan numbers (cf. A000108). Equal to the binomial coefficient sum Sum_{k=0..n} binomial(n,k)^2.
Number of possible interleavings of a program with n atomic instructions when executed by two processes. - Manuel Carro (mcarro(AT)fi.upm.es), Sep 22 2001
Convolving a(n) with itself yields A000302, the powers of 4. - T. D. Noe, Jun 11 2002 Number of ordered trees with 2n+1 edges, having root of odd degree and nonroot nodes of outdegree 0 or 2. - Emeric Deutsch, Aug 02 2002 Also number of directed, convex polyominoes having semiperimeter n+2.
Also number of diagonally symmetric, directed, convex polyominoes having semiperimeter 2n+2. - Emeric Deutsch, Aug 03 2002 The second inverse binomial transform of this sequence is this sequence with interpolated zeros. Its g.f. is (1 - 4*x^2)^(-1/2), with n-th term C(n,n/2)(1+(-1)^n)/2. - Paul Barry, Jul 01 2003 Number of possible values of a 2n-bit binary number for which half the bits are on and half are off. - Gavin Scott (gavin(AT)allegro.com), Aug 09 2003
Ordered partitions of n with zeros to n+1, e.g., for n=4 we consider the ordered partitions of 11110 (5), 11200 (30), 13000 (20), 40000 (5) and 22000 (10), total 70 and a(4)=70. See A001700 (esp. Mambetov Bektur's comment). - Jon Perry, Aug 10 2003 Number of nondecreasing sequences of n integers from 0 to n: a(n) = Sum_{i_1=0..n} Sum_{i_2=i_1..n}...Sum_{i_n=i_{n-1}..n}(1). - J. N. Bearden (jnb(AT)eller.arizona.edu), Sep 16 2003
Number of peaks at odd level in all Dyck paths of semilength n+1. Example: a(2)=6 because we have U*DU*DU*D, U*DUUDD, UUDDU*D, UUDUDD, UUU*DDD, where U=(1,1), D=(1,-1) and * indicates a peak at odd level. Number of ascents of length 1 in all Dyck paths of semilength n+1 (an ascent in a Dyck path is a maximal string of up steps). Example: a(2)=6 because we have uDuDuD, uDUUDD, UUDDuD, UUDuDD, UUUDDD, where an ascent of length 1 is indicated by a lower case letter. - Emeric Deutsch, Dec 05 2003 a(n-1) = number of subsets of 2n-1 distinct elements taken n at a time that contain a given element. E.g., n=4 -> a(3)=20 and if we consider the subsets of 7 taken 4 at a time with a 1 we get (1234, 1235, 1236, 1237, 1245, 1246, 1247, 1256, 1257, 1267, 1345, 1346, 1347, 1356, 1357, 1367, 1456, 1457, 1467, 1567) and there are 20 of them. - Jon Perry, Jan 20 2004 The dimension of a particular (necessarily existent) absolutely universal embedding of the unitary dual polar space DSU(2n,q^2) where q>2. - J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004.
Number of standard tableaux of shape (n+1, 1^n). - Emeric Deutsch, May 13 2004 Erdős, Graham et al. conjectured that a(n) is never squarefree for sufficiently large n (cf. Graham, Knuth, Patashnik, Concrete Math., 2nd ed., Exercise 112). Sárközy showed that if s(n) is the square part of a(n), then s(n) is asymptotically (sqrt(2)-2)*(sqrt(n))*(Riemann Zeta Function(1/2)). Granville and Ramare proved that the only squarefree values are a(1)=2, a(2)=6 and a(4)=70. - Jonathan Vos Post, Dec 04 2004 [For more about this conjecture, see A261009. - N. J. A. Sloane, Oct 25 2015] The MathOverflow link contains the following comment (slightly edited): The Erdős squarefree conjecture (that a(n) is never squarefree for n>4) was proved in 1980 by Sárközy, A. (On divisors of binomial coefficients. I. J. Number Theory 20 (1985), no. 1, 70-80.) who showed that the conjecture holds for all sufficiently large values of n, and by A. Granville and O. Ramaré (Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients. Mathematika 43 (1996), no. 1, 73-107) who showed that it holds for all n>4. - Fedor Petrov, Nov 13 2010. [From N. J. A. Sloane, Oct 29 2015] p divides a((p-1)/2)-1= A030662(n) for prime p=5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, ... = A002144(n) Pythagorean primes: primes of form 4n+1. - Alexander Adamchuk, Jul 04 2006 The number of direct routes from my home to Granny's when Granny lives n blocks south and n blocks east of my home in Grid City. To obtain a direct route, from the 2n blocks, choose n blocks on which one travels south. For example, a(2)=6 because there are 6 direct routes: SSEE, SESE, SEES, EESS, ESES and ESSE. - Dennis P. Walsh, Oct 27 2006 Inverse: With q = -log(log(16)/(pi a(n)^2)), ceiling((q + log(q))/log(16)) = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 26 2007
Number of partitions with Ferrers diagrams that fit in an n X n box (including the empty partition of 0). Example: a(2) = 6 because we have: empty, 1, 2, 11, 21 and 22. - Emeric Deutsch, Oct 02 2007 The number of walks of length 2n on an infinite linear lattice that begins and ends at the origin. - Stefan Hollos (stefan(AT)exstrom.com), Dec 10 2007
The number of lattice paths from (0,0) to (n,n) using steps (1,0) and (0,1). - Joerg Arndt, Jul 01 2011 Integral representation: C(2n,n)=1/Pi Integral [(2x)^(2n)/sqrt(1 - x^2),{x,-1, 1}], i.e., C(2n,n)/4^n is the moment of order 2n of the arcsin distribution on the interval (-1,1). - N-E. Fahssi, Jan 02 2008 Straub, Amdeberhan and Moll: "... it is conjectured that there are only finitely many indices n such that C_n is not divisible by any of 3, 5, 7 and 11." - Jonathan Vos Post, Nov 14 2008 Also, in sports, the number of ordered ways for a "Best of 2n-1 Series" to progress. For example, a(2) = 6 means there are six ordered ways for a "best of 3" series to progress. If we write A for a win by "team A" and B for a win by "team B" and if we list the played games chronologically from left to right then the six ways are AA, ABA, BAA, BB, BAB, and ABB. (Proof: To generate the a(n) ordered ways: Write down all a(n) ways to designate n of 2n games as won by team A. Remove the maximal suffix of identical letters from each of these.) - Lee A. Newberg, Jun 02 2009 Number of n X n binary arrays with rows, considered as binary numbers, in nondecreasing order, and columns, considered as binary numbers, in nonincreasing order. - R. H. Hardin, Jun 27 2009 Hankel transform is 2^n. - Paul Barry, Aug 05 2009 It appears that a(n) is also the number of quivers in the mutation class of twisted type BC_n for n>=2.
Number of words on {a,b} of length 2n such that no prefix of the word contains more b's than a's. - Jonathan Nilsson, Apr 18 2012 From Pascal's triangle take row(n) with terms in order a1,a2,..a(n) and row(n+1) with terms b1,b2,..b(n), then 2*(a1*b1 + a2*b2 + ... + a(n)*b(n)) to get the terms in this sequence. - J. M. Bergot, Oct 07 2012. For example using rows 4 and 5: 2*(1*(1) + 4*(5) + 6*(10) + 4*(10) + 1*(5)) = 252, the sixth term in this sequence. Take from Pascal's triangle row(n) with terms b1, b2, ..., b(n+1) and row(n+2) with terms c1, c2, ..., c(n+3) and find the sum b1*c2 + b2*c3 + ... + b(n+1)*c(n+2) to get A000984(n+1). Example using row(3) and row(5) gives sum 1*(5)+3*(10)+3*(10)+1*(5) = 70 = A000984(4). - J. M. Bergot, Oct 31 2012 a(n) == 2 mod n^3 iff n is a prime > 3. (See Mestrovic link, p. 4.) - Gary Detlefs, Feb 16 2013 Conjecture: For any positive integer n, the polynomial sum_{k=0}^n a(k)x^k is irreducible over the field of rational numbers. In general, for any integer m>1 and n>0, the polynomial f_{m,n}(x) = Sum_{k=0..n} (m*k)!/(k!)^m*x^k is irreducible over the field of rational numbers. - Zhi-Wei Sun, Mar 23 2013 This comment generalizes the comment dated Oct 31 2012 and the second of the sequence's original comments. For j = 1 to n, a(n) = Sum_{k=0..j} C(j,k)* C(2n-j, n-k) = 2*Sum_{k=0..j-1} C(j-1,k)*C(2n-j, n-k). - Charlie Marion, Jun 07 2013 The differences between consecutive terms of the sequence of the quotients between consecutive terms of this sequence form a sequence containing the reciprocals of the triangular numbers. In other words, a(n+1)/a(n)-a(n)/a(n-1) = 2/(n*(n+1)). - Christian Schulz, Jun 08 2013 Number of distinct strings of length 2n using n letters A and n letters B. - Hans Havermann, May 07 2014 Expansion of G.f. A(x) = 1/(1+q*x*c(x)), where parameter q is positive or negative (except q=-1), and c(x) is the g.f. of A000108 for Catalan numbers. The case of q=-1 recovers the g.f. of A000108 as xA^2-A+1=0. The present sequence A000984 refers to q=-2. Recurrence: (1+q)*(n+2)*a(n+2) + ((q*q-4*q-4)*n + 2*(q*q-q-1))*a(n+1) - 2*q*q*(2*n+1)*a(n) = 0, a(0)=1, a(1)=-q. Asymptotics: a(n) ~ ((q+2)/(q+1))*(q^2/(-q-1))^n, q<=-3, a(n) ~ (-1)^n*((q+2)/(q+1))*(q^2/(q+1))^n, q>=5, and a(n) ~ -Kq*2^(2*n)/sqrt(Pi*n^3), where the multiplicative constant Kq is given by K1=1/9 (q=1), K2=1/8 (q=2), K3=3/25 (q=3), K4=1/9 (q=4). These formulas apply to existing sequences A126983 (q=1), A126984 (q=2), A126982 (q=3), A126986 (q=4), A126987 (q=5), A127017 (q=6), A127016 (q=7), A126985 (q=8), A127053 (q=9), and to A007854 (q=-3), A076035 (q=-4), A076036 (q=-5), A127628 (q=-6), A126694 (q=-7), A115970 (q=-8). (End) a(n)*(2^n)^(j-2) equals S(n), where S(n) is the n-th number in the self-convolved sequence which yields the powers of 2^j for all integers j, n>=0. For example, when n=5 and j=4, a(5)=252; 252*(2^5)^(4-2) = 252*1024 = 258048. The self-convolved sequence which yields powers of 16 is {1, 8, 96, 1280, 17920, 258048, ...}; i.e., S(5) = 258048. Note that the convolved sequences will be composed of numbers decreasing from 1 to 0, when j<2 (exception being j=1, where the first two numbers in the sequence are 1 and all others decreasing). - Bob Selcoe, Jul 16 2014 The variance of the n-th difference of a sequence of pairwise uncorrelated random variables each with variance 1. - Liam Patrick Roche, Jun 04 2015 Number of ordered trees with n edges where vertices at level 1 can be of 2 colors. Indeed, the standard decomposition of ordered trees leading to the equation C = 1 + zC^2 (C is the Catalan function), yields this time G = 1 + 2zCG, from where G = 1/sqrt(1-4z). - Emeric Deutsch, Jun 17 2015 Number of monomials of degree at most n in n variables. - Ran Pan, Sep 26 2015 Let V(n, r) denote the volume of an n-dimensional sphere with radius r, then V(n, 2^n) / Pi = V(n-1, 2^n) * a(n/2) for all even n. - Peter Luschny, Oct 12 2015 a(n) is the number of sets {i1,...,in} of length n such that n >= i1 >= i2 >= ... >= in >= 0. For instance, a(2) = 6 as there are only 6 such sets: (2,2) (2,1) (2,0) (1,1) (1,0) (0,0). - Anton Zakharov, Jul 04 2016 By analytic continuation to the entire complex plane there exist regularized values for divergent sums such as:
Sum_{k>=0} a(k)/(-2)^k = 1/sqrt(3).
Sum_{k>=0} a(k)/(-1)^k = 1/sqrt(5).
Sum_{k>=0} a(k)/(-1/2)^k = 1/3.
Sum_{k>=0} a(k)/(1/2)^k = -1/sqrt(7)i.
Sum_{k>=0} a(k)/(1)^k = -1/sqrt(3)i.
Sum_{k>=0} a(k)/2^k = -i. (End)
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) > e(j). [Martinez and Savage, 2.18] - Eric M. Schmidt, Jul 17 2017 The o.g.f. for the sequence equals the diagonal of any of the following the rational functions: 1/(1 - (x + y)), 1/(1 - (x + y*z)), 1/(1 - (x + x*y + y*z)) or 1/(1 - (x + y + y*z)). - Peter Bala, Jan 30 2018 Let s denote West's stack-sorting map. a(n) is the number of permutations pi of [n+1] such that s(pi) avoids the patterns 132, 231, and 321. a(n) is also the number of permutations pi of [n+1] such that s(pi) avoids the patterns 132, 312, and 321.
a(n) is the number of permutations of [n+1] that avoid the patterns 1342, 3142, 3412, and 3421. (End)
All binary self-dual codes of length 4n, for n>0, must contain at least a(n) codewords of weight 2n. More to the point, there will always be at least one, perhaps unique, binary self-dual code of length 4n that will contain exactly a(n) codewords that have a hamming weight equal to half the length of the code (2n). This code can be constructed by direct summing the unique binary self-dual code of length 2 (up to permutation equivalence) to itself an even number of times. A permutation equivalent code can be constructed by augmenting two identity matrices of length 2n together. - Nathan J. Russell, Nov 25 2018 Let [b/p] denote the Legendre symbol and 1/b denote the inverse of b mod p. Then, for m and n, where n is not divisible by p,
[(m+n)/p] == [n/p]*Sum_{k=0..(p-1)/2} (-m/(4*n))^k * a(k) (mod p).
Evaluating this identity for m = -1 and n = 1 demonstrates that, for all odd primes p, Sum_{k=0..(p-1)/2} (1/4)^k * a(k) is divisible by p. (End)
Number of vertices of the subgraph of the (2n-1)-dimensional hypercube induced by all bitstrings with n-1 or n many 1s. The middle levels conjecture asserts that this graph has a Hamilton cycle. - Torsten Muetze, Feb 11 2019 a(n) is the number of walks of length 2n from the origin with steps (1,1) and (1,-1) that stay on or above the x-axis. Equivalently, a(n) is the number of walks of length 2n from the origin with steps (1,0) and (0,1) that stay in the first octant. - Alexander Burstein, Dec 24 2019 Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {3>1, 1>2} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second element but smaller than the third elements. - Sergey Kitaev, Dec 08 2020 Also the number of integer compositions of 2n+1 with alternating sum 1, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(0) = 1 through a(2) = 6 compositions are:
(1) (2,1) (3,2)
(1,1,1) (1,2,2)
(2,2,1)
(1,1,2,1)
(2,1,1,1)
(1,1,1,1,1)
The following relate to these compositions:
- The unordered version is A000070. - The alternating sum 0 version is counted by A088218, ranked by A344619. - Including even indices gives A126869. - The complement is counted by A202736. Equivalently, a(n) counts binary numbers with 2n+1 digits and one more 1 than 0's. For example, the a(2) = 6 binary numbers are: 10011, 10101, 10110, 11001, 11010, 11100.
(End)
a(n) is the number of nx2 Young tableaux with a single horizontal wall between the first and second column. If there is a wall between two cells, the entries may be decreasing; see [Banderier, Wallner 2021].
Example for a(2)=6:
3 4 2 4 3 4 3|4 4|3 2|4
1|2, 1|3, 2|1, 1 2, 1 2, 1 3
a(n) is also the number of nx2 Young tableaux with n "walls" between the first and second column.
Example for a(2)=6:
3|4 2|4 4|3 3|4 4|3 4|2
1|2, 1|3, 1|2, 2|1, 2|1, 3|1 (End)
a(n)/4^n is the probability that a fair coin tossed 2n times will come up heads exactly n times and tails exactly n times, or that a random walk with steps of +-1 will return to the starting point after 2n steps (not necessarily for the first time). As n becomes large, this number asymptotically approaches 1/sqrt(n*Pi), using Stirling's approximation for n!.
a(n)/(4^n*(2n-1)) is the probability that a random walk with steps of +-1 will return to the starting point for the first time after 2n steps. The absolute value of the n-th term of A144704 is denominator of this fraction. Considering all possible random walks of exactly 2n steps with steps of +-1, a(n)/(2n-1) is the number of such walks that return to the starting point for the first time after 2n steps. See the absolute values of A002420 or A284016 for these numbers. For comparison, as mentioned by Stefan Hollos, Dec 10 2007, a(n) is the number of such walks that return to the starting point after 2n steps, but not necessarily for the first time. (End) Also the size of the shuffle product of two words of length n, such that the union of the two words consist of 2n distinct elements. - Robert C. Lyons, Mar 15 2023
REFERENCES
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 160.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 575, line -3, with a=b=n.
E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bulletin of the Institute of Combinatorics and its Applications, 31, 31-38, 2001.
H. W. Gould, Combinatorial Identities, Morgantown, 1972, (3.66), page 30.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, Second Ed., see Exercise 112.
M. Griffiths, The Backbone of Pascal's Triangle, United Kingdom Mathematics Trust (2008), 3-124.
Leonard Lipshitz and A. van der Poorten. "Rational functions, diagonals, automata and arithmetic." In Number Theory, Richard A. Mollin, ed., Walter de Gruyter, Berlin (1990): 339-358.
J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.
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
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]. Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8. L. W. Shapiro, S. Getu, Wen-Jin Woan and L. C. Woodson, The Riordan Group, Discrete Appl. Maths. 34 (1991) 229-239. M. Wallner, Lattice Path Combinatorics, Diplomarbeit, Institut für Diskrete Mathematik und Geometrie der Technischen Universität Wien, 2013.
FORMULA
a(n)/(n+1) = A000108(n), the Catalan numbers. G.f.: A(x) = (1 - 4*x)^(-1/2) = 1F0(1/2;;4x).
D-finite with recurrence: n*a(n) + 2*(1-2*n)*a(n-1)=0.
a(n) = 2^n/n! * Product_{k=0..n-1} (2*k+1).
Using Stirling's formula in A000142 it is easy to get the asymptotic expression a(n) ~ 4^n / sqrt(Pi * n). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 07 2001 Integral representation as n-th moment of a positive function on the interval [0, 4]: a(n) = Integral_{x=0..4}(x^n*((x*(4-x))^(-1/2))/Pi), n=0, 1, ... This representation is unique. - Karol A. Penson, Sep 17 2001 a(n) = Max_{ (i+j)!/(i!j!) | 0<=i,j<=n }. - Benoit Cloitre, May 30 2002 E.g.f.: exp(2*x)*I_0(2x), where I_0 is Bessel function. - Michael Somos, Sep 08 2002 E.g.f.: I_0(2*x) = Sum a(n)*x^(2*n)/(2*n)!, where I_0 is Bessel function. - Michael Somos, Sep 09 2002 Determinant of n X n matrix M(i, j) = binomial(n+i, j). - Benoit Cloitre, Aug 28 2003 Given m = C(2*n, n), let f be the inverse function, so that f(m) = n. Letting q denote -log(log(16)/(m^2*Pi)), we have f(m) = ceiling( (q + log(q)) / log(16) ). - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Oct 30 2003
a(n+1) = Sum_{j=n..n*2+1} binomial(j, n). E.g., a(4) = C(7,3) + C(6,3) + C(5,3) + C(4,3) + C(3,3) = 35 + 20 + 10 + 4 + 1 = 70. - Jon Perry, Jan 20 2004 a(n) = (-1)^(n)*Sum_{j=0..(2*n)} (-1)^j*binomial(2*n, j)^2. - Helena Verrill (verrill(AT)math.lsu.edu), Jul 12 2004
a(n) = Sum_{k=0..n} binomial(2n+1, k)*sin((2n-2k+1)*Pi/2). - Paul Barry, Nov 02 2004 a(n-1) = (1/2)*(-1)^n*Sum_{0<=i, j<=n}(-1)^(i+j)*binomial(2n, i+j). - Benoit Cloitre, Jun 18 2005 G.f.: c(x)^2/(2*c(x)-c(x)^2) where c(x) is the g.f. of A000108. - Paul Barry, Feb 03 2006 G.f.: 1/(1-2x-2x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-... (continued fraction);
G.f.: 1/(1-2x/(1-x/(1-x/(1-x/(1-... (continued fraction). (End)
Let A(x) be the g.f. and B(x) = A(-x), then B(x) = sqrt(1-4*x*B(x)^2). - Vladimir Kruchinin, Jan 16 2011 a(n) = (-4)^n*sqrt(Pi)/(gamma((1/2-n))*gamma(1+n)). - Gerry Martens, May 03 2011 a(n) = upper left term in M^n, M = the infinite square production matrix:
2, 2, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, 1, ....
a(n) = Hypergeometric([-n,-n],[1],1). - Peter Luschny, Nov 01 2011 G.f.: 1 + 2*x/(U(0)-2*x) where U(k) = 2*(2*k+1)*x + (k+1) - 2*(k+1)*(2*k+3)*x/U(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Jun 28 2012 a(n) = Sum_{k=0..n} binomial(n,k)^2*H(k)/(2*H(n)-H(2*n)), n>0, where H(n) is the n-th harmonic number. - Gary Detlefs, Mar 19 2013 G.f.: Q(0)*(1-4*x), where Q(k) = 1 + 4*(2*k+1)*x/( 1 - 1/(1 + 2*(k+1)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 11 2013 G.f.: G(0)/2, where G(k) = 1 + 1/(1 - 2*x*(2*k+1)/(2*x*(2*k+1) + (k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 24 2013 E.g.f.: E(0)/2, where E(k) = 1 + 1/(1 - 2*x/(2*x + (k+1)^2/(2*k+1)/E(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013 Special values of Jacobi polynomials, in Maple notation: a(n) = 4^n*JacobiP(n,0,-1/2-n,-1). - Karol A. Penson, Jul 27 2013 a(n) = 2^(4*n)/((2*n+1)*Sum_{k=0..n} (-1)^k*C(2*n+1,n-k)/(2*k+1)). - Mircea Merca, Nov 12 2013 a(n) = C(2*n-1,n-1)*C(4*n^2,2)/(3*n*C(2*n+1,3)), n>0. - Gary Detlefs, Jan 02 2014 0 = a(n)*(16*a(n+1) - 6*a(n+2)) + a(n+1)*(-2*a(n+1) + a(n+2)) for all n in Z. - Michael Somos, Sep 17 2014 G.f.: Sum_{n>=0} x^n/(1-x)^(2*n+1) * Sum_{k=0..n} C(n,k)^2 * x^k. - Paul D. Hanna, Nov 08 2014 a(n) = 4^n*hypergeom([-n,1/2],[1],1). - Peter Luschny, May 19 2015 a(n) = Sum_{k=0..floor(n/2)} C(n,k)*C(n-k,k)*2^(n-2*k). - Robert FERREOL, Aug 29 2015 a(n) ~ 4^n*(2-2/(8*n+2)^2+21/(8*n+2)^4-671/(8*n+2)^6+45081/(8*n+2)^8)/sqrt((4*n+1) *Pi). - Peter Luschny, Oct 14 2015 A(-x) = 1/x * series reversion( x*(2*x + sqrt(1 + 4*x^2)) ). Compare with the o.g.f. B(x) of A098616, which satisfies B(-x) = 1/x * series reversion( x*(2*x + sqrt(1 - 4*x^2)) ). See also A214377. - Peter Bala, Oct 19 2015 Sum_{n>=0} (-1)^n/a(n) = 4*(5 - sqrt(5)*log(phi))/25 = 0.6278364236143983844442267..., where phi is the golden ratio. - Ilya Gutkovskiy, Jul 04 2016 This sequence occurs as the closed-form expression for several binomial sums:
a(n) = Sum_{k = 0..2*n} (-1)^(n+k)*binomial(2*n,k)*binomial(2*n + 1,k).
a(n) = 2*Sum_{k = 0..2*n-1} (-1)^(n+k)*binomial(2*n - 1,k)*binomial(2*n,k) for n >= 1.
a(n) = 2*Sum_{k = 0..n-1} binomial(n - 1,k)*binomial(n,k) for n >= 1.
a(n) = Sum_{k = 0..2*n} (-1)^k*binomial(2*n,k)*binomial(x + k,n)*binomial(y + k,n) = Sum_{k = 0..2*n} (-1)^k*binomial(2*n,k)*binomial(x - k,n)*binomial(y - k,n) for arbitrary x and y.
For m = 3,4,5,... both Sum_{k = 0..m*n} (-1)^k*binomial(m*n,k)*binomial(x + k,n)*binomial(y + k,n) and Sum_{k = 0..m*n} (-1)^k*binomial(m*n,k)*binomial(x - k,n)*binomial(y - k,n) appear to equal Kronecker's delta(n,0).
a(n) = (-1)^n*Sum_{k = 0..2*n} (-1)^k*binomial(2*n,k)*binomial(x + k,n)*binomial(y - k,n) for arbitrary x and y.
For m = 3,4,5,... Sum_{k = 0..m*n} (-1)^k*binomial(m*n,k)*binomial(x + k,n)*binomial(y - k,n) appears to equal Kronecker's delta(n,0).
a(n) = Sum_{k = 0..2n} (-1)^k*binomial(2*n,k)*binomial(3*n - k,n)^2 = Sum_{k = 0..2*n} (-1)^k*binomial(2*n,k)* binomial(n + k,n)^2. (Gould, Vol. 7, 5.23).
a(n) = Sum_{k = 0..n} (-1)^(n+k)*binomial(2*n,n + k)*binomial(n + k,n)^2. (End)
Sum_{k>=0} a(k)/(p/q)^k = sqrt(p/(p-4q)) for q in N, p in Z/{-4q< (some p) <-2}.
...
Sum_{k>=0} a(k)/(-4)^k = 1/sqrt(2).
Sum_{k>=0} a(k)/(17/4)^k = sqrt(17).
Sum_{k>=0} a(k)/(18/4)^k = 3.
Sum_{k>=0} a(k)/5^k = sqrt(5).
Sum_{k>=0} a(k)/6^k = sqrt(3).
Sum_{k>=0} a(k)/8^k = sqrt(2).
...
Sum_{k>=0} a(k)/(p/q)^k = sqrt(p/(p-4q)) for p>4q.(End)
Boas-Buck recurrence: a(n) = (2/n)*Sum_{k=0..n-1} 4^(n-k-1)*a(k), n >= 1, a(0) = 1. Proof from a(n) = A046521(n, 0). See a comment there. - Wolfdieter Lang, Aug 10 2017 a(n) = Sum_{k = 0..n} (-1)^(n-k) * binomial(2*n+1, k) for n in N. - Rene Adad, Sep 30 2017 G.f. for {1/a(n)}: 4*(sqrt(4-x) + sqrt(x)*arcsin(sqrt(x)/2)) / (4-x)^(3/2).
E.g.f. for {1/a(n)}: 1 + exp(x/4)*sqrt(Pi*x)*erf(sqrt(x)/2)/2.
Sum_{n>=0} (-1)^n/a(n) = 4*(1/5 - arcsinh(1/2)/(5*sqrt(5))). (End)
a(n) = 2^(2*n)*Product_{k=1..2*n} k^((-1)^(k+1)) = A056040(2*n). a(n) = 4^n*binomial(n-1/2,-1/2) = 4^n*GegenbauerC(n,1/4,1). - Gerry Martens, Oct 19 2022 Occurs on the right-hand side of the binomial sum identities Sum_{k = -n..n} (-1)^k * (n + x - k) * binomial(2*n, n+k)^2 = (x + n)*a(n) and Sum_{k = -n..n} (-1)^k * (n + x - k)^2 * binomial(2*n, n+k)^3 = x*(x + 2*n)*a(n) (x arbitrary). Compare with the identity: Sum_{k = -n..n} (-1)^k * binomial(2*n, n+k)^2 = a(n). - Peter Bala, Jul 31 2023 4^n*a(n) = Sum_{k = 0..2*n} (-1)^k*a(k)*a(2*n-k).
16^n = Sum_{k = 0..2*n} a(k)*a(2*n-k). (End)
a(n) = Sum_{k=0..floor(n/2)} binomial(n,2k)*binomial(2*k,k)*2^(n-2*k). (H. W. Gould) - Gary Detlefs, May 28 2024 a(n) = Sum_{k=0..2*n} (-1)^k*binomial(2n,k)*binomial(2*n+2*k,n+k)*3^(2*n-k). (H. W. Gould) (End)
EXAMPLE
G.f.: 1 + 2*x + 6*x^2 + 20*x^3 + 70*x^4 + 252*x^5 + 924*x^6 + ...
For n=2, a(2) = 4!/(2!)^2 = 24/4 = 6, and this is the middle coefficient of the binomial expansion (a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4. - Michael B. Porter, Jul 06 2016
MAPLE
with(combstruct); [seq(count([S, {S=Prod(Set(Z, card=i), Set(Z, card=i))}, labeled], size=(2*i)), i=0..20)];
with(combstruct); [seq(count([S, {S=Sequence(Union(Arch, Arch)), Arch=Prod(Epsilon, Sequence(Arch), Z)}, unlabeled], size=i), i=0..25)];
with(combstruct):bin := {B=Union(Z, Prod(B, B))}: seq (count([B, bin, unlabeled], size=n)*n, n=1..25); # Zerinvary Lajos, Dec 05 2007 A000984List := proc(m) local A, P, n; A := [1, 2]; P := [1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), 2*P[-1]]);
A := [op(A), 2*P[-1]] od; A end: A000984List(28); # Peter Luschny, Mar 24 2022
MATHEMATICA
CoefficientList[Series[1/Sqrt[1-4x], {x, 0, 25}], x] (* Harvey P. Dale, Mar 14 2011 *)
PROG
(Magma) a:= func< n | Binomial(2*n, n) >; [ a(n) : n in [0..10]];
(PARI) A000984(n)=binomial(2*n, n) \\ much more efficient than (2n)!/n!^2. \\ M. F. Hasler, Feb 26 2014 (PARI) fv(n, p)=my(s); while(n\=p, s+=n); s
(PARI) fv(n, p)=my(s); while(n\=p, s+=n); s
(Haskell)
(Python)
from __future__ import division
for n in range(10**3):
b = b*(4*n+2)//(n+1)
(GAP) List([1..1000], n -> Binomial(2*n, n)); # Muniru A Asiru, Jan 30 2018
CROSSREFS
Bisection of A001405 and of A226302. See also A025565, the same ordered partitions but without all in which are two successive zeros: 11110 (5), 11200 (18), 13000 (2), 40000 (0) and 22000 (1), total 26 and A025565(4)=26. See A261009 for a conjecture about this sequence. The Apéry-like numbers [or Apéry-like sequences, Apery-like numbers, Apery-like sequences] include A000172, A000984, A002893, A002895, A005258, A005259, A005260, A006077, A036917, A063007, A081085, A093388, A125143 (apart from signs), A143003, A143007, A143413, A143414, A143415, A143583, A183204, A214262, A219692, A226535, A227216, A227454, A229111 (apart from signs), A260667, A260832, A262177, A264541, A264542, A279619, A290575, A290576. (The term "Apery-like" is not well-defined.) Sum_{k = 0..n} C(n,k)^m for m = 1..12: A000079, A000984, A000172, A005260, A005261, A069865, A182421, A182422, A182446, A182447, A342294, A342295.
KEYWORD
nonn,easy,core,nice,walk,frac,changed
Tetrahedral (or triangular pyramidal) numbers: a(n) = C(n+2,3) = n*(n+1)*(n+2)/6.
(Formerly M3382 N1363)
+10
851
0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 1140, 1330, 1540, 1771, 2024, 2300, 2600, 2925, 3276, 3654, 4060, 4495, 4960, 5456, 5984, 6545, 7140, 7770, 8436, 9139, 9880, 10660, 11480, 12341, 13244, 14190, 15180
COMMENTS
a(n) is the number of balls in a triangular pyramid in which each edge contains n balls.
One of the 5 Platonic polyhedral (tetrahedral, cube, octahedral, dodecahedral and icosahedral) numbers (cf. A053012). Also (1/6)*(n^3 + 3*n^2 + 2*n) is the number of ways to color the vertices of a triangle using <= n colors, allowing rotations and reflections. Group is the dihedral group D_6 with cycle index (x1^3 + 2*x3 + 3*x1*x2)/6.
Also the convolution of the natural numbers with themselves. - Felix Goldberg (felixg(AT)tx.technion.ac.il), Feb 01 2001
Connected with the Eulerian numbers (1, 4, 1) via 1*a(n-2) + 4*a(n-1) + 1*a(n) = n^3. - Gottfried Helms, Apr 15 2002 a(n) is sum of all the possible products p*q where (p,q) are ordered pairs and p + q = n + 1. E.g., a(5) = 5 + 8 + 9 + 8 + 5 = 35. - Amarnath Murthy, May 29 2003 Number of labeled graphs on n+3 nodes that are triangles. - Jon Perry, Jun 14 2003 Number of permutations of n+3 which have exactly 1 descent and avoid the pattern 1324. - Mike Zabrocki, Nov 05 2004 Schlaefli symbol for this polyhedron: {3,3}.
Transform of n^2 under the Riordan array (1/(1-x^2), x). - Paul Barry, Apr 16 2005 a(n) is a perfect square only for n = {1, 2, 48}. E.g., a(48) = 19600 = 140^2. - Alexander Adamchuk, Nov 24 2006 a(n+1) is the number of terms in the expansion of (a_1 + a_2 + a_3 + a_4)^n. - Sergio Falcon, Feb 12 2007 [Corrected by Graeme McRae, Aug 28 2007] a(n+1) is the number of terms in the complete homogeneous symmetric polynomial of degree n in 3 variables. - Richard Barnes, Sep 06 2017 This is also the average "permutation entropy", sum((pi(n)-n)^2)/n!, over the set of all possible n! permutations pi. - Jeff Boscole (jazzerciser(AT)hotmail.com), Mar 20 2007
a(n) = (d/dx)(S(n, x), x)|_{x = 2}. First derivative of Chebyshev S-polynomials evaluated at x = 2. See A049310. - Wolfdieter Lang, Apr 04 2007 If X is an n-set and Y a fixed (n-1)-subset of X then a(n-2) is equal to the number of 3-subsets of X intersecting Y. - Milan Janjic, Aug 15 2007 a(n) is the number of gifts received from the lyricist's true love up to and including day n in the song "The Twelve Days of Christmas". a(12) = 364, almost the number of days in the year. - Bernard Hill (bernard(AT)braeburn.co.uk), Dec 05 2008
Sequence of the absolute values of the z^1 coefficients of the polynomials in the GF2 denominators of A156925. See A157703 for background information. - Johannes W. Meijer, Mar 07 2009 This is a 'Matryoshka doll' sequence with alpha=0, the multiplicative counterpart is A000178: seq(add(add(i,i=alpha..k),k=alpha..n),n=alpha..50). - Peter Luschny, Jul 14 2009 a(n) is the number of nondecreasing triples of numbers from a set of size n, and it is the number of strictly increasing triples of numbers from a set of size n+2. - Samuel Savitz, Sep 12 2009 [Corrected and enhanced by Markus Sigg, Sep 24 2023] a(n) is the number of ordered sequences of 4 nonnegative integers that sum to n. E.g., a(2) = 10 because 2 = 2 + 0 + 0 + 0 = 1 + 1 + 0 + 0 = 0 + 2 + 0 + 0 = 1 + 0 + 1 + 0 = 0 + 1 + 1 + 0 = 0 + 0 + 2 + 0 = 1 + 0 + 0 + 1 = 0 + 1 + 0 + 1 = 0 + 0 + 1 + 1 = 0 + 0 + 0 + 2. - Artur Jasinski, Nov 30 2009 a(n) corresponds to the total number of steps to memorize n verses by the technique described in A173964. - Ibrahima Faye (ifaye2001(AT)yahoo.fr), Feb 22 2010 The number of (n+2)-bit numbers which contain two runs of 1's in their binary expansion. - Vladimir Shevelev, Jul 30 2010 a(n) is also, starting at the second term, the number of triangles formed in n-gons by intersecting diagonals with three diagonal endpoints (see the first column of the table in Sommars link). - Alexandre Wajnberg, Aug 21 2010 Column sums of:
1 4 9 16 25...
1 4 9...
1...
..............
--------------
1 4 10 20 35...
The Ca3, Ca4, Gi3 and Gi4 triangle sums (see A180662 for their definitions) of the Connell-Pol triangle A159797 are linear sums of shifted versions of the duplicated tetrahedral numbers, e.g., Gi3(n) = 17*a(n) + 19*a(n-1) and Gi4(n) = 5*a(n) + a(n-1). Furthermore the Kn3, Kn4, Ca3, Ca4, Gi3 and Gi4 triangle sums of the Connell sequence A001614 as a triangle are also linear sums of shifted versions of the sequence given above. (End) a(n-2)=N_0(n), n >= 1, with a(-1):=0, is the number of vertices of n planes in generic position in three-dimensional space. See a comment under A000125 for general arrangement. Comment to Arnold's problem 1990-11, see the Arnold reference, p. 506. - Wolfdieter Lang, May 27 2011 We consider optimal proper vertex colorings of a graph G. Assume that the labeling, i.e., coloring starts with 1. By optimality we mean that the maximum label used is the minimum of the maximum integer label used across all possible labelings of G. Let S=Sum of the differences |l(v) - l(u)|, the sum being over all edges uv of G and l(w) is the label associated with a vertex w of G. We say G admits unique labeling if all possible labelings of G is S-invariant and yields the same integer partition of S. With an offset this sequence gives the S-values for the complete graph on n vertices, n = 2, 3, ... . - K.V.Iyer, Jul 08 2011 Central term of commutator of transverse Virasoro operators in 4-D case for relativistic quantum open strings (ref. Zwiebach). - Tom Copeland, Sep 13 2011 Appears as a coefficient of a Sturm-Liouville operator in the Ovsienko reference on page 43. - Tom Copeland, Sep 13 2011 Regarding the second comment above by Amarnath Murthy (May 29 2003), see A181118 which gives the sequence of ordered pairs. - L. Edson Jeffery, Dec 17 2011 The dimension of the space spanned by the 3-form v[ijk] that couples to M2-brane worldsheets wrapping 3-cycles inside tori (ref. Green, Miller, Vanhove eq. 3.9). - Stephen Crowley, Jan 05 2012 a(n+1) is the number of 2 X 2 matrices with all terms in {0, 1, ..., n} and (sum of terms) = n. Also, a(n+1) is the number of 2 X 2 matrices with all terms in {0, 1, ..., n} and (sum of terms) = 3n. - Clark Kimberling, Mar 19 2012 Using n + 4 consecutive triangular numbers t(1), t(2), ..., t(n+4), where n is the n-th term of this sequence, create a polygon by connecting points (t(1), t(2)) to (t(2), t(3)), (t(2), t(3)) to (t(3), t(4)), ..., (t(1), t(2)) to (t(n+3), t(n+4)). The area of this polygon will be one-half of each term in this sequence. - J. M. Bergot, May 05 2012 Pisano period lengths: 1, 4, 9, 8, 5, 36, 7, 16, 27, 20, 11, 72, 13, 28, 45, 32, 17,108, 19, 40, ... . (The Pisano sequence modulo m is the auxiliary sequence p(n) = a(n) mod m, n >= 1, for some m. p(n) is periodic for all sequences with rational g.f., like this one, and others. The lengths of the period of p(n) are quoted here for m>=1.) - R. J. Mathar, Aug 10 2012 a(n) is the maximum possible number of rooted triples consistent with any phylogenetic tree (level-0 phylogenetic network) containing exactly n+2 leaves. - Jesper Jansson, Sep 10 2012 For n > 0, the digital roots of this sequence A010888(a(n)) form the purely periodic 27-cycle {1, 4, 1, 2, 8, 2, 3, 3, 3, 4, 7, 4, 5, 2, 5, 6, 6, 6, 7, 1, 7, 8, 5, 8, 9, 9, 9}, which just rephrases the Pisano period length above. - Ant King, Oct 18 2012 a(n) is the number of functions f from {1, 2, 3} to {1, 2, ..., n + 4} such that f(1) + 1 < f(2) and f(2) + 1 < f(3). - Dennis P. Walsh, Nov 27 2012 a(n) is the Szeged index of the path graph with n+1 vertices; see the Diudea et al. reference, p. 155, Eq. (5.8). - Emeric Deutsch, Aug 01 2013 Also the number of permutations of length n that can be sorted by a single block transposition. - Vincent Vatter, Aug 21 2013 a(n) is the 3 X 3 matrix determinant
| C(n,1) C(n,2) C(n,3) |
| C(n+1,1) C(n+1,2) C(n+1,3) |
| C(n+2,1) C(n+2,2) C(n+2,3) |
(End)
In physics, a(n)/2 is the trace of the spin operator S_z^2 for a particle with spin S=n/2. For example, when S=3/2, the S_z eigenvalues are -3/2, -1/2, +1/2, +3/2 and the sum of their squares is 10/2 = a(3)/2. - Stanislav Sykora, Nov 06 2013 a(n+1) = (n+1)*(n+2)*(n+3)/6 is also the dimension of the Hilbert space of homogeneous polynomials of degree n. - L. Edson Jeffery, Dec 12 2013 For n >= 4, a(n-3) is the number of permutations of 1,2...,n with the distribution of up (1) - down (0) elements 0...0111 (n-4 zeros), or, equivalently, a(n-3) is up-down coefficient {n,7} (see comment in A060351). - Vladimir Shevelev, Feb 15 2014 a(n) is one-half the area of the region created by plotting the points (n^2,(n+1)^2). A line connects points (n^2,(n+1)^2) and ((n+1)^2, (n+2)^2) and a line is drawn from (0,1) to each increasing point. From (0,1) to (4,9) the area is 2; from (0,1) to (9,16) the area is 8; further areas are 20,40,70,...,2*a(n). - J. M. Bergot, May 29 2014 Beukers and Top prove that no tetrahedral number > 1 equals a square pyramidal number A000330. - Jonathan Sondow, Jun 21 2014 a(n+1) is for n >= 1 the number of nondecreasing n-letter words over the alphabet [4] = {1, 2, 3, 4} (or any other four distinct numbers). a(2+1) = 10 from the words 11, 22, 33, 44, 12, 13, 14, 23, 24, 34; which is also the maximal number of distinct elements in a symmetric 4 X 4 matrix. Inspired by the Jul 20 2014 comment by R. J. Cano on A000582. - Wolfdieter Lang, Jul 29 2014 Degree of the q-polynomial counting the orbits of plane partitions under the action of the symmetric group S3. Orbit-counting generating function is product_{i <= j <= k <= n} ( (1 - q^(i + j + k - 1))/(1 - q^(i + j + k - 2)) ). See q-TSPP reference. - Olivier Gérard, Feb 25 2015 If n is even then a(n) = Sum_{k=1..n/2} (2k)^2. If n is odd then a(n) = Sum_{k=0..(n-1)/2} (1+2k)^2. This can be illustrated as stacking boxes inside a square pyramid on plateaus of edge lengths 2k or 2k+1, respectively. The largest k are the 2k X 2k or (2k+1) X (2k+1) base. - R. K. Guy, Feb 26 2015 Draw n lines in general position in the plane. Any three define a triangle, so in all we see C(n,3) = a(n-2) triangles (6 lines produce 4 triangles, and so on). - Terry Stickels, Jul 21 2015
a(n-2) = fallfac(n,3)/3!, n >= 3, is also the number of independent components of an antisymmetric tensor of rank 3 and dimension n. Here fallfac is the falling factorial. - Wolfdieter Lang, Dec 10 2015 Number of compositions (ordered partitions) of n+3 into exactly 4 parts. - Juergen Will, Jan 02 2016 Number of weak compositions (ordered weak partitions) of n-1 into exactly 4 parts. - Juergen Will, Jan 02 2016 For n >= 2 gives the number of multiplications of two nonzero matrix elements in calculating the product of two upper n X n triangular matrices. - John M. Coffey, Jun 23 2016 Terms a(4n+1), n >= 0, are odd, all others are even. The 2-adic valuation of the subsequence of every other term, a(2n+1), n >= 0, yields the ruler sequence A007814. Sequence A275019 gives the 2-adic valuation of a(n). - M. F. Hasler, Dec 05 2016 Does not satisfy Benford's law [Ross, 2012]. - N. J. A. Sloane, Feb 12 2017 C(n+2,3) is the number of ways to select 1 triple among n+2 objects, thus a(n) is the coefficient of x1^(n-1)*x3 in exponential Bell polynomial B_{n+2}(x1,x2,...), hence its link with A050534 and A001296 (see formula). - Cyril Damamme, Feb 26 2018 a(n) is also the number of 3-cycles in the (n+4)-path complement graph. - Eric W. Weisstein, Apr 11 2018 a(n) is the general number of all geodetic graphs of diameter n homeomorphic to a complete graph K4. - Carlos Enrique Frasser, May 24 2018 a(n) + 4*a(n-1) + a(n-2) = n^3 = A000578(n), for n >= 0 (extending the a(n) formula given in the name). This is the Worpitzky identity for cubes. (Number of components of the decomposition of a rank 3 tensor in dimension n >= 1 into symmetric, mixed and antisymmetric parts). For a(n-2) see my Dec 10 2015 comment. - Wolfdieter Lang, Jul 16 2019 a(n) also gives the total number of regular triangles of length k (in some length unit), with k from {1, 2, ..., n}, in the matchstick arrangement with enclosing triangle of length n, but only triangles with the orientation of the enclosing triangle are counted. Row sums of unsigned A122432(n-1, k-1), for n >= 1. See the Andrew Howroyd comment in A085691. - Wolfdieter Lang, Apr 06 2020 a(n) is the number of bigrassmannian permutations on n+1 elements, i.e., permutations which have a unique left descent, and a unique right descent. - Rafael Mrden, Aug 21 2020 a(n-2) is the number of chiral pairs of colorings of the edges or vertices of a triangle using n or fewer colors. - Robert A. Russell, Oct 20 2020 a(n-2) is the number of subsets of {1,2,...,n} whose diameters are their size. For example, for n=4, a(2)=4 and the sets are {1,3}, {2,4}, {1,2,4}, {1,3,4}. - Enrique Navarrete, Dec 26 2020 For n>1, a(n-2) is the number of subsets of {1,2,...,n} in which the second largest element is the size of the subset. For example, for n=4, a(2)=4 and the sets are {2,3}, {2,4}, {1,3,4}, {2,3,4}. - Enrique Navarrete, Jan 02 2021 a(n) is the number of binary strings of length n+2 with exactly three 0's. - Enrique Navarrete, Jan 15 2021 Aside from the zero, this sequence is the fourth diagonal of the Pascal matrix A007318 and the only nonvanishing diagonal (fourth) of the matrix representation IM = ( A132440)^3/3! of the differential operator D^3/3!, when acting on the row vector of coefficients of an o.g.f., or power series. M = e^{IM} is the lower triangular matrix of coefficients of the Appell polynomial sequence p_n(x) = e^{D^3/3!} x^n = e^{b. D} x^n = (b. + x)^n = Sum_{k=0..n} binomial(n,k) b_n x^{n-k}, where the (b.)^n = b_n have the e.g.f. e^{b.t} = e^{t^3/3!}, which is that for A025035 aerated with double zeros, the first column of M. See A099174 and A000332 for analogous relationships for the third and fifth diagonals of the Pascal matrix. (End) a(n) is the number of circles with a radius of integer length >= 1 and center at a grid point in an n X n grid. - Albert Swafford, Jun 11 2021 Maximum Wiener index over all connected graphs with n+1 vertices. - Allan Bickle, Jul 09 2022 The third Euler row (1,4,1) has an additional connection with the tetrahedral numbers besides the n^3 identity stated above: a^2(n) + 4*a^2(n+1) + a^2(n+2) = a(n^2+4n+4), which can be shown with algebra. E.g., a^2(2) + 4*a^2(3) + a^2(4) = 16 + 400 + 400 = a(16). Although an analogous thing happens with the (1,1) row of Euler's triangle and triangular numbers C(n+1,2) = A000217(n) = T(n), namely both T(n-1) + T(n) = n^2 and T^2(n-1) + T^2(n) = T(n^2) are true, only one (the usual identity) still holds for the Euler row (1,11,11,1) and the C(n,4) numbers in A000332. That is, the dot product of (1,11,11,1) with the squares of 4 consecutive terms of A000332 is not generally a term of A000332. - Richard Peterson, Aug 21 2022 For n > 1, a(n-2) is the number of solutions of the Diophantine equation x1 + x2 + x3 + x4 + x5 = n, subject to the constraints 0 <= x1, 1 <= x2, 2 <= x3, 0 <= x4 <= 1, 0 <= x5 and x5 is even. - Daniel Checa, Nov 03 2022 a(n+1) is also the number of vertices of the generalized Pitman-Stanley polytope with parameters 2, n, and vector (1,1, ... ,1), which is integrally equivalent to a flow polytope over the grid graph having 2 rows and n columns. - William T. Dugan, Sep 18 2023 a(n) is the number of binary words of length (n+1) containing exactly one substring 01. a(2) = 4: 001, 010, 011, 101. - Nordine Fahssi, Dec 09 2024
REFERENCES
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
V. I. Arnold (ed.), Arnold's Problems, Springer, 2004, comments on Problem 1990-11 (p. 75), pp. 503-510. Numbers N_0.
A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 194.
J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 83.
H. S. M. Coxeter, Polyhedral numbers, pp. 25-35 of R. S. Cohen, J. J. Stachel and M. W. Wartofsky, eds., For Dirk Struik: Scientific, historical and political essays in honor of Dirk J. Struik, Reidel, Dordrecht, 1974.
E. Deza and M. M. Deza, Figurate numbers, World Scientific Publishing (2012), page 93.
L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 2, p. 4.
M. V. Diudea, I. Gutman, and J. Lorentz, Molecular Topology, Nova Science, 2001, Huntington, N.Y. pp. 152-156.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §8.6 Figurate Numbers, pp. 292-293.
J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.
V. Ovsienko and S. Tabachnikov, Projective Differential Geometry Old and New, Cambridge Tracts in Mathematics (no. 165), Cambridge Univ. Press, 2005.
Kenneth A Ross, First Digits of Squares and Cubes, Math. Mag. 85 (2012) 36-42. doi:10.4169/math.mag.85.1.36.
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).
A. Szenes, The combinatorics of the Verlinde formulas (N.J. Hitchin et al., ed.), in Vector bundles in algebraic geometry, Cambridge, 1995.
D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1987, pp. 126-127.
B. Zwiebach, A First Course in String Theory, Cambridge, 2004; see p. 226.
LINKS
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]. T. P. Martin, Shells of atoms, Phys. Reports, 273 (1996), 199-241, eq. (1).
FORMULA
a(n) = C(n+2,3) = n*(n+1)*(n+2)/6 (see the name).
G.f.: x / (1 - x)^4.
a(n) = -a(-4 - n) for all in Z.
a(n) = Sum_{k=0..n} A000217(k) = Sum_{k=1..n} Sum_{j=0..k} j, partial sums of the triangular numbers. Determinant of the n X n symmetric Pascal matrix M_(i, j) = C(i+j+2, i). - Benoit Cloitre, Aug 19 2003 The sum of a series constructed by the products of the index and the length of the series (n) minus the index (i): a(n) = sum[i(n-i)]. - Martin Steven McCormick (mathseq(AT)wazer.net), Apr 06 2005
a(n) = Sum_{k=0..floor((n-1)/2)} (n-2k)^2 [offset 0]; a(n+1) = Sum_{k=0..n} k^2*(1-(-1)^(n+k-1))/2 [offset 0]. - Paul Barry, Apr 16 2005 Values of the Verlinde formula for SL_2, with g = 2: a(n) = Sum_{j=1..n-1} n/(2*sin^2(j*Pi/n)). - Simone Severini, Sep 25 2006 a(n-1) = (1/(1!*2!))*Sum_{1 <= x_1, x_2 <= n} |det V(x_1, x_2)| = (1/2)*Sum_{1 <= i,j <= n} |i-j|, where V(x_1, x_2) is the Vandermonde matrix of order 2. Column 2 of A133112. - Peter Bala, Sep 13 2007 Starting with 1 = binomial transform of [1, 3, 3, 1, ...]; e.g., a(4) = 20 = (1, 3, 3, 1) dot (1, 3, 3, 1) = (1 + 9 + 9 + 1). - Gary W. Adamson, Nov 04 2007 Sum_{n>=1} 1/a(n) = 3/2, case x = 1 in Gradstein-Ryshik 1.513.7. - R. J. Mathar, Jan 27 2009 With offset 1, a(n) = (1/6)*floor(n^5/(n^2 + 1)). - Gary Detlefs, Feb 14 2010 a(n) = (3*n^2 + 6*n + 2)/(6*(h(n+2) - h(n-1))), n > 0, where h(n) is the n-th harmonic number. - Gary Detlefs, Jul 01 2011 a(n) = coefficient of x^2 in the Maclaurin expansion of 1 + 1/(x+1) + 1/(x+1)^2 + 1/(x+1)^3 + ... + 1/(x+1)^n. - Francesco Daddi, Aug 02 2011 a(n) = coefficient of x^4 in the Maclaurin expansion of sin(x)*exp((n+1)*x). - Francesco Daddi, Aug 04 2011 a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) + 1. - Ant King, Oct 18 2012 G.f.: x*U(0) where U(k) = 1 + 2*x*(k+2)/( 2*k+1 - x*(2*k+1)*(2*k+5)/(x*(2*k+5)+(2*k+2)/U(k+1) )); (continued fraction, 3rd kind, 3-step). - Sergei N. Gladkovskii, Dec 01 2012 a(n^2 - 1) = (1/2)*(a(n^2 - n - 2) + a(n^2 + n - 2)) and
G.f.: x + 4*x^2/(Q(0)-4*x) where Q(k) = 1 + k*(x+1) + 4*x - x*(k+1)*(k+5)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Mar 14 2013 a(n+1) = det(C(i+3,j+2), 1 <= i,j <= n), where C(n,k) are binomial coefficients. - Mircea Merca, Apr 06 2013 G.f.: x*G(0)/2, where G(k) = 1 + 1/(1 - x/(x + (k+1)/(k+4)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 02 2013 a(n)*(m+1)^3 + a(m)*(n+1) = a(n*m + n + m), for any nonnegative integers m and n. This is a 3D analog of Euler's theorem about triangular numbers, namely t(n)*(2m+1)^2 + t(m) = t(2nm + n + m), where t(n) is the n-th triangular number. - Ivan N. Ianakiev, Aug 20 2013 Sum_{n>=0} a(n)/(n+1)! = 2*e/3 = 1.8121878856393... . Sum_{n>=1} a(n)/n! = 13*e/6 = 5.88961062832... . - Richard R. Forberg, Dec 25 2013 a(k*n) = a(k)*a(n) + 4*a(k-1)*a(n-1) + a(k-2)*a(n-2). - Robert Israel, Apr 20 2015 Dirichlet g.f.: (zeta(s-3) + 3*zeta(s-2) + 2*zeta(s-1))/6. - Ilya Gutkovskiy, Jul 01 2016 G.f.: x/(1 - x)^4 = (x * r(x) * r(x^2) * r(x^4) * r(x^8) * ...), where r(x) = (1 + x)^4 = (1 + 4x + 6x^2 + 4x^3 + x^4); and x/(1 - x)^4 = (x * r(x) * r(x^3) * r(x^9) * r(x^27) * ...) where r(x) = (1 + x + x^2)^4. - Gary W. Adamson, Jan 23 2017 a(n) = 1*C(n,1) + 2*C(n,2) + 1*C(n,3), where the coefficient of C(n,k) is the number of unoriented triangle colorings using exactly k colors.
a(n-2) = 1*C(n,3), where the coefficient of C(n,k) is the number of chiral pairs of triangle colorings using exactly k colors.
Product_{n>=1} (1 + 1/a(n)) = sinh(sqrt(2)*Pi)/(3*sqrt(2)*Pi).
Product_{n>=2} (1 - 1/a(n)) = sqrt(2)*sinh(sqrt(2)*Pi)/(33*Pi). (End)
EXAMPLE
a(2) = 3*4*5/6 = 10, the number of balls in a pyramid of 3 layers of balls, 6 in a triangle at the bottom, 3 in the middle layer and 1 on top.
Consider the square array
1 2 3 4 5 6 ...
2 4 6 8 10 12 ...
3 6 9 12 16 20 ...
4 8 12 16 20 24 ...
5 10 15 20 25 30 ...
...
G.f. = x + 4*x^2 + 10*x^3 + 20*x^4 + 35*x^5 + 56*x^6 + 84*x^7 + 120*x^8 + 165*x^9 + ...
Example for a(3+1) = 20 nondecreasing 3-letter words over {1,2,3,4}: 111, 222, 333; 444, 112, 113, 114, 223, 224, 122, 224, 133, 233, 144, 244, 344; 123, 124, 134, 234. 4 + 4*3 + 4 = 20. - Wolfdieter Lang, Jul 29 2014 Example for a(4-2) = 4 independent components of a rank 3 antisymmetric tensor A of dimension 4: A(1,2,3), A(1,2,4), A(1,3,4) and A(2,3,4). - Wolfdieter Lang, Dec 10 2015
MAPLE
a:=n->n*(n+1)*(n+2)/6; seq(a(n), n=0..50);
isA000292 := proc(n)
option remember;
local a, i ;
for i from iroot(6*n, 3)-1 do
if a > n then
return false;
elif a = n then
return true;
end if;
end do:
MATHEMATICA
Accumulate[Accumulate[Range[0, 50]]] (* Harvey P. Dale, Dec 10 2011 *) LinearRecurrence[{4, -6, 4, -1}, {0, 1, 4, 10}, 20] (* Eric W. Weisstein, Sep 08 2017 *) CoefficientList[Series[x/(-1 + x)^4, {x, 0, 20}], x] (* Eric W. Weisstein, Sep 08 2017 *) Table[Range[n].Range[n, 1, -1], {n, 0, 50}] (* Harvey P. Dale, Mar 02 2024 *)
PROG
(PARI) a(n) = (n) * (n+1) * (n+2) / 6 \\ corrected by Harry J. Smith, Dec 22 2008 (PARI) a=vector(10000); a[2]=1; for(i=3, #a, a[i]=a[i-2]+i*i); \\ Stanislav Sykora, Nov 07 2013 (Haskell)
a000292 n = n * (n + 1) * (n + 2) `div` 6
a000292_list = scanl1 (+) a000217_list
x, y, z = 1, 1, 1
yield 0
while True:
yield x
x, y, z = x + y + z + 1, y + z + 1, z + 1
CROSSREFS
Sums of 2 consecutive terms give A000330. Cf. A000217 (first differences), A001044, (see above example), A061552, A040977, A133111, A133112, A152205, A158823, A156925, A157703, A173964, A058187, A190717, A190718, A100440, A181118, A222716. Cf. A216499 (the analogous sequence for level-1 phylogenetic networks). Cf. similar sequences listed in A237616. Cf. A104712 (second column, if offset is 2). Cf. A002817 (4-cycle count of \bar P_{n+4}), A060446 (5-cycle count of \bar P_{n+3}), A302695 (6-cycle count of \bar P_{n+5}) Row 2 of A325000 (simplex facets and vertices) and A327084 (simplex edges and ridges). Cf. (triangle colorings) A006527 (oriented), A000290 (achiral), A327085 (chiral simplex edges and ridges). Row 3 of A321791 (cycles of n colors using k or fewer colors).
KEYWORD
nonn,core,easy,nice,changed
Double factorial of even numbers: (2n)!! = 2^n*n!.
(Formerly M1878 N0742)
+10
232
1, 2, 8, 48, 384, 3840, 46080, 645120, 10321920, 185794560, 3715891200, 81749606400, 1961990553600, 51011754393600, 1428329123020800, 42849873690624000, 1371195958099968000, 46620662575398912000, 1678343852714360832000, 63777066403145711616000
COMMENTS
a(n) is also the size of the automorphism group of the graph (edge graph) of the n-dimensional hypercube and also of the geometric automorphism group of the hypercube (the two groups are isomorphic). This group is an extension of an elementary Abelian group (C_2)^n by S_n. (C_2 is the cyclic group with two elements and S_n is the symmetric group.) - Avi Peretz (njk(AT)netvision.net.il), Feb 21 2001
Then a(n) appears in the power series: sqrt(1+sin(y)) = Sum_{n>=0} (-1)^floor(n/2)*y^(n)/a(n) and sqrt((1+cos(y))/2) = Sum_{n>=0} (-1)^n*y^(2n)/a(2n). - Benoit Cloitre, Feb 02 2002 Number of n X n monomial matrices with entries 0, +-1.
Also number of linear signed orders.
Define a "downgrade" to be the permutation d which places the items of a permutation p in descending order. This note concerns those permutations that are equal to their double-downgrades. The number of permutations of order 2n having this property are equinumerous with those of order 2n+1. a(n) = number of double-downgrading permutations of order 2n and 2n+1. - Eugene McDonnell (eemcd(AT)mac.com), Oct 27 2003
a(n) = (Integral_{x=0..Pi/2} cos(x)^(2*n+1) dx) where the denominators are b(n) = (2*n)!/(n!*2^n). - Al Hakanson (hawkuu(AT)excite.com), Mar 02 2004
1 + (1/2)x - (1/8)x^2 - (1/48)x^3 + (1/384)x^4 + ... = sqrt(1+sin(x)).
a(n)*(-1)^n = coefficient of the leading term of the (n+1)-th derivative of arctan(x), see Hildebrand link. - Reinhard Zumkeller, Jan 14 2006 a(n) is the Pfaffian of the skew-symmetric 2n X 2n matrix whose (i,j) entry is j for i<j. - David Callan, Sep 25 2006 a(n) is the number of increasing plane trees with n+1 edges. (In a plane tree, each subtree of the root is an ordered tree but the subtrees of the root may be cyclically rotated.) Increasing means the vertices are labeled 0,1,2,...,n+1 and each child has a greater label than its parent. Cf. A001147 for increasing ordered trees, A000142 for increasing unordered trees and A000111 for increasing 0-1-2 trees. - David Callan, Dec 22 2006 Hamed Hatami and Pooya Hatami prove that this is an upper bound on the cardinality of any minimal dominating set in C_{2n+1}^n, the Cartesian product of n copies of the cycle of size 2n+1, where 2n+1 is a prime. - Jonathan Vos Post, Jan 03 2007 This sequence and (1,-2,0,0,0,0,...) form a reciprocal pair under the list partition transform and associated operations described in A133314. - Tom Copeland, Oct 29 2007 a(n) = number of permutations of the multiset {1,1,2,2,...,n,n,n+1,n+1} such that between the two occurrences of i, there is exactly one entry >i, for i=1,2,...,n. Example: a(2) = 8 counts 121323, 131232, 213123, 231213, 232131, 312132, 321312, 323121. Proof: There is always exactly one entry between the two 1s (when n>=1). Given a permutation p in A(n) (counted by a(n)), record the position i of the first 1, then delete both 1s and subtract 1 from every entry to get a permutation q in A(n-1). The mapping p -> (i,q) is a bijection from A(n) to the Cartesian product [1,2n] X A(n-1). - David Callan, Nov 29 2007 a(n) is the number of ways to seat n married couples in a row so that everyone is next to their spouse. Compare A007060. - Geoffrey Critzer, Mar 29 2009 Equals (-1)^n * (1, 1, 2, 8, 48, ...) dot (1, -3, 5, -7, 9, ...).
Example: a(4) = 384 = (1, 1, 2, 8, 48) dot (1, -3, 5, -7, 9) = (1, -3, 10, -56, 432). (End)
Assuming n starts at 0, a(n) appears to be the number of Gray codes on n bits. It certainly is the number of Gray codes on n bits isomorphic to the canonical one. Proof: There are 2^n different starting positions for each code. Also, each code has a particular pattern of bit positions that are flipped (for instance, 1 2 1 3 1 2 1 for n=3), and these bit position patterns can be permuted in n! ways. - D. J. Schreffler (ds1404(AT)txstate.edu), Jul 18 2010
E.g.f. of 0,1,2,8,... is x/(1-2x/(2-2x/(3-8x/(4-8x/(5-18x/(6-18x/(7-... (continued fraction). - Paul Barry, Jan 17 2011 Number of increasing 2-colored trees with choice of two colors for each edge. In general, if we replace 2 with k we get the number of increasing k-colored trees. For example, for k=3 we get the triple factorial numbers. - Wenjin Woan, May 31 2011 Also the number of permutations of 2n (or of 2n+1) that are equal to their reverse-complements. (See the Egge reference.) Note that the double-downgrade described in the preceding comment (McDonnell) is equivalent to the reverse-complement. - Justin M. Troyka, Aug 11 2011 The e.g.f. can be used to form a generator, [1/(1-2x)] d/dx, for A000108, so a(n) can be applied to A145271 to generate the Catalan numbers. - Tom Copeland, Oct 01 2011 The e.g.f. of 1/a(n) is BesselI(0,sqrt(2*x)). See Abramowitz-Stegun (reference and link under A008277), p. 375, 9.6.10. - Wolfdieter Lang, Jan 09 2012 a(n) = order of the largest imprimitive group of degree 2n with n systems of imprimitivity (see [Miller], p. 203). - L. Edson Jeffery, Feb 05 2012 For n>1, a(n) is the order of the Coxeter groups (also called Weyl groups) of types B_n and C_n. - Tom Edgar, Nov 05 2013 For m>0, k*a(m-1) is the m-th cumulant of the chi-squared probability distribution for k degrees of freedom. - Stanislav Sykora, Jun 27 2014 Also the order of the automorphism group of the n-ladder rung graph. - Eric W. Weisstein, Jul 22 2017 a(n) is the order of the group O_n(Z) = {A in M_n(Z): A*A^T = I_n}, the group of n X n orthogonal matrices over the integers. - Jianing Song, Mar 29 2021 a(n) is the number of ways to tile a (3n,3n)-benzel or a (3n+1,3n+2)-benzel using left stones and two kinds of bones; see Defant et al., below. - James Propp, Jul 22 2023 a(n) is the number of labeled histories for a labeled topology with the modified lodgepole shape and n+1 cherry nodes. - Noah A Rosenberg, Jan 16 2025
REFERENCES
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).
FORMULA
E.g.f.: 1/(1-2*x).
a(n) = A001044(n)/ A000142(n)* A000079(n) = Product_{i=0..n-1} (2*i+2) = 2^n*Pochhammer(1,n). - Daniel Dockery (peritus(AT)gmail.com), Jun 13 2003 D-finite with recurrence a(n) = 2*n * a(n-1), n>0, a(0)=1. - Paul Barry, Aug 26 2004 This is the binomial mean transform of A001907. See Spivey and Steil (2006). - Michael Z. Spivey (mspivey(AT)ups.edu), Feb 26 2006 a(n) = Integral_{x>=0} x^n*exp(-x/2)/2 dx. - Paul Barry, Jan 28 2008 G.f.: 1/(1-2x/(1-2x/(1-4x/(1-4x/(1-6x/(1-6x/(1-.... (continued fraction). - Paul Barry, Feb 07 2009 a(n) = upper left term in M^n, M = a production matrix (twice Pascal's triangle deleting the first "2", with the rest zeros; cf. A028326): 2, 2, 0, 0, 0, 0, ...
2, 4, 2, 0, 0, 0, ...
2, 6, 6, 2, 0, 0, ...
2, 8, 12, 8, 2, 0, ...
2, 10, 20, 20, 10, 2, ...
... (End)
Continued fractions:
G.f.: 1 + x*(Q(0) - 1)/(x+1) where Q(k) = 1 + (2*k+2)/(1-x/(x+1/Q(k+1))).
G.f.: 1/Q(0) where Q(k) = 1 + 2*k*x - 2*x*(k+1)/Q(k+1).
G.f.: G(0)/2 where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+2) + 1/G(k+1))).
G.f.: 1/Q(0) where Q(k) = 1 - x*(4*k+2) - 4*x^2*(k+1)^2/Q(k+1).
G.f.: R(0) where R(k) = 1 - x*(2*k+2)/(x*(2*k+2)-1/(1-x*(2*k+2)/(x*(2*k+2) -1/R(k+1)))). (End)
Recurrence equation: a(n) = (3*n - 1)*a(n-1) - 2*(n - 1)^2*a(n-2) with a(1) = 2 and a(2) = 8.
The sequence b(n) = A068102(n) also satisfies this second-order recurrence. This leads to the generalized continued fraction expansion lim_{n -> oo} b(n)/a(n) = log(2) = 1/(2 - 2/(5 - 8/(8 - 18/(11 - ... - 2*(n - 1)^2/((3*n - 1) - ... ))))). (End) Sum_{n>=0} 1/a(n) = sqrt(e) ( A019774). Sum_{n>=0} (-1)^n/a(n) = 1/sqrt(e) ( A092605). (End) a(n) = 1/([x^n] hypergeom([1], [1], x/2)). - Peter Luschny, Sep 13 2024
EXAMPLE
The following permutations and their reversals are all of the permutations of order 5 having the double-downgrade property:
0 1 2 3 4
0 3 2 1 4
1 0 2 4 3
1 4 2 0 3
G.f. = 1 + 2*x + 8*x^2 + 48*x^3 + 384*x^4 + 3840*x^5 + 46080*x^6 + 645120*x^7 + ...
MAPLE
A000165 := proc(n) option remember; if n <= 1 then 1 else n* A000165(n-2); fi; end;
ZL:=[S, {a = Atom, b = Atom, S = Prod(X, Sequence(Prod(X, b))), X = Sequence(b, card >= 0)}, labelled]: seq(combstruct[count](ZL, size=n), n=0..17); # Zerinvary Lajos, Mar 26 2008 G(x):=(1-2*x)^(-1): f[0]:=G(x): for n from 1 to 29 do f[n]:=diff(f[n-1], x) od: x:=0: seq(f[n], n=0..17); # Zerinvary Lajos, Apr 03 2009
MATHEMATICA
RecurrenceTable[{a[n] == 2 n*a[n-1], a[0] == 1}, a, {n, 0, 30}] (* Ray Chandler, Jul 30 2015 *)
PROG
(PARI) {a(n) = prod( k=1, n, 2*k)}; /* Michael Somos, Jan 04 2013 */ (Magma) I:=[2, 8]; [1] cat [n le 2 select I[n] else (3*n-1)*Self(n-1)-2*(n-1)^2*Self(n-2): n in [1..35] ]; // Vincenzo Librandi, Feb 19 2015 (Haskell)
(Python)
from math import factorial
(SageMath) [2^n*factorial(n) for n in range(31)] # G. C. Greubel, Jul 21 2024
CROSSREFS
This sequence gives the row sums in A060187, and (-1)^n*a(n) the alternating row sums in A039757.
a(n) = n!*(n-1)!/2^(n-1).
(Formerly M3052)
+10
56
1, 1, 3, 18, 180, 2700, 56700, 1587600, 57153600, 2571912000, 141455160000, 9336040560000, 728211163680000, 66267215894880000, 6958057668962400000, 834966920275488000000, 113555501157466368000000, 17373991677092354304000000, 2970952576782792585984000000
COMMENTS
Number of ways of transforming n distinguishable objects into n singletons via a sequence of n-1 refinements. Example: a(3)=3 because we have XYZ->X|YZ->X|Y|Z, XYZ->Y|XZ->X|Y|Z and XYZ->Z|XY->X|Y|Z. - Emeric Deutsch, Jan 23 2005 In other words, a(n) is the number of maximal chains in the lattice of set partitions of {1, ..., n} ordered by refinement. - Gus Wiseman, Jul 22 2018 With offset 0, a(n) = number of unordered increasing full binary trees of 2n edges with leaf set {n,n+1,...,2n}, where full binary means each nonleaf vertex has two children, increasing means the vertices are labeled 0,1,2,...,2n and each child is greater than its parent, unordered might as well mean ordered and each pair of sibling vertices is increasing left to right. For example, a(2)=3 counts the trees with edge lists {01,02,13,14}, {01,03,12,14}, {01,04,12,13}.
PROOF. Given such a tree of size n, to produce a tree of size n+1, two new leaves must be added to the leaf n. Choose any two of the leaf set {n+1,...,2n,2n+1,2n+2} for the new leaves and use the rest to replace the old leaves n+1,...,2n, maintaining relative order. Thus each tree of size n yields (n+2)-choose-2 trees of the next size up. Since the ratio a(n+1)/a(n)=(n+2)-choose-2, the result follows by induction.
Without the condition on the leaves, these trees are counted by the reduced tangent numbers A002105. (End) a(n) = Sum(M(t)N(t)), where summation is over all rooted trees t with n vertices, M(t) is the number of ways to take apart t by sequentially removing terminal edges (see A206494) and N(t) is the number of ways to build up t from the one-vertex tree by adding successively edges to the existing vertices (the Connes-Moscovici weight; see A206496). See Remark on p. 3801 of the Hoffman reference. Example: a(3) = 3; indeed, there are two rooted trees with 3 vertices: t' = the path r-a-b and t" = V; we have M(t')=N(t')=1 and M(t") =1, N(t")=2, leading to M(t')N(t') + M(t")N(t")=3. - Emeric Deutsch, Jul 20 2012 Number of coalescence sequences or labeled histories for n lineages: the number of sequences by which n distinguishable leaves can coalesce to a single sequence. The coalescence process merges pairs of lineages into new lineages, labeling each newly formed lineage l by a subset of the n initial lineages corresponding to the union of all initial lineages that feed into lineage l. - Noah A Rosenberg, Jan 28 2019 Conjecture: For n > 1, n divides 2*a(n-1) + 4 if and only if n is prime. - Werner Schulte, Oct 04 2020 For a proof of the above conjecture see Himane. The list of primes p such that p^2 divides (2*a(p-1) + 4) (analog of A007540 - Wilson primes) begins [239, 24049, ...]. - Peter Bala, Nov 06 2024
REFERENCES
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 148.
László Lovász, Combinatorial Problems and Exercises, North-Holland, 1979, p. 165.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Mike Steel, Phylogeny: Discrete and Random Processes in Evolution, SIAM, 2016, p. 47.
FORMULA
a(n) = polygorial(n, 3) = ( A000142(n)/ A000079(n))* A000142(n+1) = (n!/2^n)*Product_{i=0..n-1} (i+2) = (n!/2^n)*Pochhammer(2, n) = (n!^2/2^n)*(n+1) = polygorial(n, 4)/2^n*(n+1). - Daniel Dockery (peritus(AT)gmail.com), Jun 13 2003 a(n-1) = (-1)^(n+1)/(n^2*det(M_n)) where M_n is the matrix M_(i, j) = abs(1/i - 1/j). - Benoit Cloitre, Aug 21 2003 a(n) ~ 4*Pi*n^(2*n)/(2^n*exp(2*n)).
Sum_{n>=1} 1/a(n) = BesselI(1,2*sqrt(2))/sqrt(2) = 2.3948330992734... (End)
D-finite with recurrence 2*a(n) -n*(n-1)*a(n-1)=0. - R. J. Mathar, May 02 2022 Sum_{n>=1} (-1)^(n+1)/a(n) = BesselJ(1,2*sqrt(2))/sqrt(2). - Amiram Eldar, Jun 25 2022
EXAMPLE
The (3) = 3 maximal chains in the lattice of set partitions of {1,2,3}:
{{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}
{{1},{2},{3}} < {{2},{1,3}} < {{1,2,3}}
{{1},{2},{3}} < {{3},{1,2}} < {{1,2,3}}
(End)
MATHEMATICA
FoldList[Times, 1, Accumulate[Range[20]]] (* Harvey P. Dale, Jan 10 2013 *)
PROG
(Magma) [Factorial(n)*Factorial(n-1)/2^(n-1): n in [1..20]]; // Vincenzo Librandi, Aug 23 2018 (Python)
from math import factorial
Search completed in 0.091 seconds
|