0,2

ABA and BAB are equal, so are counted as only one unique word.

R. L. Graham, J. C. Lagarias, C. L. Mallows, A. R. Wilks and C. Yan, Apollonian circle Packings: Geometry and Group Theory III Higher Dimensions. Discrete and Computational Geometry 35: 37-72 (2006).

C. L. Mallows, Growing Apollonian packings, J. Integer Sequences 12, article 09.2.1 (2009)

Comment from Bill Thurston, Nov 22 2009: There's a handy program (or rather, a constellation of programs) kbmag by Derek Holt et al., which can be used as a package within GAP or as a free-standing program, to try to find an automatic structure for a group. I entered this presentation, and it produced an automatic structure, which implies the growth function is rational: (1 + 2*X + 2*X^2 + X^3)/(1 - 3*X - 3*X^2 + 6*X^3), as reported by kbgrowth.

John Cannon also found this g.f.

Recurrence: for n>=1 a(n+3)=3*a(n+2)+3*a(n+1)-6*a(n) with a(0..3)={1,5,20,70}. [From Zak Seidov (zakseidov(AT)yahoo.com), Dec 07 2009]

There are 80 square-free words of length 3, but 20 of these fall into 10 equal pairs (e.g. ABA = BAB). So a(3)=70.

For other sequences relating to the 3-dimensional case, see A154638-A154645.

Sequence in context: A080930 A000343 A005324 this_sequence A054889 A056384 A036683

Adjacent sequences: A154635 A154636 A154637 this_sequence A154639 A154640 A154641

nonn

Colin Mallows (colinm(AT)research.avayalabs.com), Jan 13 2009

Corrected and extended with g.f. by John Cannon (john(AT)maths.usyd.edu.au) and Bill Thurston (wpt4(AT)cornell.edu), Nov 22 2009

Edited by N. J. A. Sloane, Nov 22 2009

0,4

Also called Lam{\'e}'s sequence.

F(n+2) = number of binary sequences of length n that have no consecutive 0's.

F(n+2) = number of subsets of {1,2,...,n} that contain no consecutive integers.

F(n+1) = number of tilings of a 2 X n rectangle by 2 X 1 dominoes.

F(n+1) = number of matchings in a path graph on n vertices: F(5)=5 because the matchings of the path graph on the vertices A, B, C, D are the empty set, {AB}, {BC}, {CD} and {AB, CD}. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 18 2001

F(n) = number of compositions of n+1 with no part equal to 1 [Grimaldi]

Positive terms are the solutions to z = 2xy^4 + (x^2)y^3 - 2(x^3)y^2 - y^5 - (x^4)y + 2y for x,y >= 0 (Ribenboim, page 193). When x=F(n), y=F(n + 1) and z>0 then z=F(n + 1).

For Fibonacci search see Knuth, Vol. 3; Horowitz and Sahni; etc.

F(n) is the diagonal sum of the entries in Pascal's triangle at 45 degrees slope. - Amarnath Murthy (amarnath_murthy(AT)yahoo.com), Dec 29 2001

F(n+1) is the number of perfect matchings in ladder graph L_n = P_2 X P_n, - Sharon Sela (sharonsela(AT)hotmail.com), May 19 2002

F(n+1) = number of (3412,132)-, (3412,213)- and (3412,321)-avoiding involutions in S_n.

This is also the Horadam sequence (0,1,1,1). - Ross La Haye (rlahaye(AT)new.rr.com), Aug 18 2003

An INVERT transform of A019590. INVERT([1,1,2,3,5,8,...]) gives A000129. INVERT([1,2,3,5,8,13,21,...]) gives A028859. - Antti Karttunen, Dec 12, 2003

Number of meaningful differential operations of the k-th order on the space R^3. - Branko Malesevic (malesevic(AT)kiklop.etf.bg.ac.yu), Mar 02 2004

F(n)=number of compositions of n-1 with no part greater than 2. Example: F(4)=3 because we have 3 = 1+1+1=1+2=2+1.

F(n) = number of compositions of n into odd parts; e.g. F(6) counts 1+1+1+1+1+1, 1+1+1+3, 1+1+3+1, 1+3+1+1, 1+5, 3+1+1+1, 3+3, 5+1. - Clark Kimberling (ck6(AT)evansville.edu), Jun 22 2004

F(n) = number of binary words of length n beginning with 0 and having all runlengths odd; e.g. F(6) counts 010101, 010111, 010001, 011101, 011111, 000101, 000111, 000001. - Clark Kimberling (ck6(AT)evansville.edu), Jun 22 2004

F(n) = number of Catalan paths between the lines y = 0 and y = 3 from (0,0) to (n, GCD(n,2)). - Clark Kimberling (ck6(AT)evansville.edu), Jun 22 2004

The number of sequences (s(0),s(1),...s(n)) such that 0<s(i)<5, |s(i)-s(i-1)|=1 and s(0)=1 is F(n+1); e.g. F(5+1) = 8 corresponds to 121212, 121232, 121234, 123212, 123232, 123234, 123432, 123434. - Clark Kimberling (ck6(AT)evansville.edu), Jun 22 2004. [Corrected by Neven Juric, Jan 09 2009]

Likewise F(6+1) = 13 corresponds to these thirteen sequences with seven numbers: 1212121, 1212123, 1212321, 1212323, 1212343, 1232121, 1232123, 1232321, 1232323, 1232343, 1234321, 1234323, 1234343. - Neven Juric, Jan 09, 2008.

A relationship between F(n) and the Mandelbrot set is discussed in the link 'Le nombre d'or dans l'ensemble de Mandelbrot' (in French). - Gerald McGarvey (Gerald.McGarvey(AT)comcast.net), Sep 19 2004

For n>0, the continued fraction for F(2n-1)*Phi = [F(2n);L(2n-1),L(2n-1),L(2n-1),...] and the continued fraction for F(2n)*Phi = [F(2n+1);L(2n)-2,L(2n)-2,L(2n)-2,...] where L(i) is the i-th Lucas number (A000204). - Clark Kimberling (ck6(AT)evansville.edu), Nov 28 2004

F(n) = number of permutations p of 1,2,3,...,n such that |k-p(k)|<=1 for k=1,2,...,n. (For <=2 and <=3, see A002524 and A002526.). - Clark Kimberling (ck6(AT)evansville.edu), Nov 28 2004

The ratios F(n+1)/F(n) for n>0 are the convergents to the simple continued fraction expansion of the golden section. - Jonathan Sondow (jsondow(AT)alumni.princeton.edu), Dec 19 2004

Lengths of successive words (starting with a) under the substitution: {a -> ab, b -> a} - J. F. J. Laros (jlaros(AT)liacs.nl), Jan 22 2005

The Fibonacci sequence, like any additive sequence, naturally tends to be geometric with common ratio not a rational power of 10; consequently, for a sufficiently large number of terms, Benford's law of first significant digit {i.e., first digit 1 =< d =< 9 occurring with probability log_10(d+1) - log_10(d)} holds. - Lekraj Beedassy (blekraj(AT)yahoo.com), Apr 29 2005

a(n) = Sum(abs(A108299(n, k)): 0 <= k <= n). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Jun 01 2005

a(n) = A001222(A000304(n)).

Fib(n+2)=sum(k=0..n, binomial(floor((n+k)/2),k) ), row sums of A04685 4. - Paul Barry (pbarry(AT)wit.ie), Mar 11 2003

Number of order ideals of the "zig-zag" poset. See vol. 1, ch. 3, prob. 23 of Stanley. - Mitch Harris (Harris.Mitchell (AT) mgh.harvard.edu), Dec 27, 2005

F(n+1)/F(n) is also the Farey fraction sequence (see A097545 for explanation) for the golden ratio, which is the only number whose Farey fractions and continued fractions are the same. - Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), May 08 2006

a(n+2) is the number of paths through 2 plates of glass with n reflections (reflections occurring at plate/plate or plate/air interfaces). Cf. A006356-A006359. - Mitch Harris (Harris.Mitchell(AT)mgh.harvard.edu), Jul 06 2006

F(n+1) equals the number of downsets (i.e. decreasing subsets)of an n-element fence, i.e. an ordered set of height 1 on {1,2,...,n} with 1 > 2 < 3 > 4 < ... n and no other comparabilities. Alternatively, F(n+1) equals the number of subsets A of {1,2,...,n} with the property that, if k is in A, then the adjacent elements of {1,2,...,n} belong to A, i.e. both k - 1 and k + 1 are in A (provided they are in {1,2,...,n}). - Brian A. Davey (B.Davey(AT)latrobe.edu.au), Aug 25 2006

Number of Kekule structures in polyphenanthrenes. See the paper by Lukovits and Janezic for details. - Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Aug 22 2006

Inverse: With phi = (sqrt(5) + 1)/2, round(log_phi(sqrt((sqrt(5) a(n) + sqrt(5 a(n)^2 - 4))(sqrt(5) a(n) + sqrt(5 a(n)^2 + 4)))/2)) = n for n >= 3, obtained by rounding the arithmetic mean of the inverses given in A001519 and A001906. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007

Comment from Larry Gerstein (gerstein(AT)math.ucsb.edu), Mar 30 2007: A result of Jacobi from 1848 states that every symmetric matrix over a p.i.d. is congruent to a triple-diagonal matrix. Consider the maximal number T(n) of summands in the determinant of an n X n triple-diagonal matrix. This is the same as the number of summands in such a determinant in which the main-, sub- and super-diagonal elements are all nonzero. By expanding on the first row we see that the sequence of T(n)'s is the Fibonacci sequence without the initial stammer on the 1's.

Suppose psi=ln(phi). We get the representation F(n)=(2/sqrt(5))*sinh(n*psi) if n is even; F(n)=(2/sqrt(5))*cosh(n*psi) if n is odd. There is a similar representation for Lucas numbers (A000032). Many Fibonacci formulas now easily follow from appropriate sinh- and cosh-formulas. For example: the de Moivre theorem (cosh(x)+sinh(x))^m=cosh(mx)+sinh(mx) produces L(n)^2+5F(n)^2=2L(2n) and L(n)F(n)=F(2n) (setting x=n*psi and m=2). - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Apr 18 2007

Inverse: floor(log_phi(sqr(5)*Fib(n))+0.5)=n, for n>1. Also for n>0, floor(1/2*log_phi(5*Fib(n)*Fib(n+1)))=n. Extension valid for integer n, except n=0,-1: floor(1/2*sign(Fib(n)*Fib(n+1))*log_phi|5*Fib(n)*Fib(n+1)|)=n {where sign(x) = sign of x}. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), May 02 2007

F(n+2) = The number of Khalimsky-continuous functions with a two-point codomain. - Shiva Samieinia (shiva(AT)math.su.se), Oct 04 2007

From Kauffman and Lopes, Proposition 8.2, p. 21: "The sequence of the determinants of the Fibonacci sequence of rational knots is the Fibonacci sequence (of numbers)." - Jonathan Vos Post (jvospost3(AT)gmail.com), Oct 26 2007

This is a_1(n) in the Doroslovacki reference.

Let phi = 1.6180339...; then phi^n = (1/phi)*a(n) + a(n+1). Example: phi^4 = 6.8541019...= (.6180339...)*3 + 5. Also phi = 1/1 + 1/2 + 1/(2*5) + 1/(5*13) + 1/(13*34) + 1/(34*89),... - Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 15 2007

The sequence of first differences, fib(n+1)-fib(n), is essentailly the same sequence: 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... - Colm Mulcahy, Mar 03 2008

a(n)= the number of different ways to run up a staircase with n steps, taking steps of odd sizes where the order is relevant and there is no other restriction on the number or the size of each step taken. - Mohammad K. Azarian (azarian(AT)evansville.edu), May 21 2008

Equals row sums of triangle A144152. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 12 2008]

Contribution from Cino Hilliard (hillcino368(AT)gmail.com), Sep 15 2008: (Start)

Except for the initial term, the numerator of the convergents to the recursion x

= 1/(x+1). (End)

Contribution from Ross Drewe (rd(AT)labyrinth.net.au), Oct 05 2008: (Start)

F(n) is the number of possible binary sequences of length n that obey the

sequential construction rule: if last symbol is 0, add the complement (1);

else add 0 or 1. Here 0,1 are metasymbols for any 2-valued symbol set. This

rule has obvious similarities to JFJ Laros's rule, but is based on addition

rather than substitution and creates a tree rather than a single sequence. (End)

F(n) = PRODUCT_{k=1, (n-1)/2} (1 + 4*Cos^2 k*pi/n); where terms = roots to the Fibonacci product polynomials, A152063. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 22 2008]

Fp == 5^((p-1)/2) mod p, p = prime; [Schroeder, p. 90]. [From Gary W. Adamson & Alexander Povolotsky (qntmpkt(AT)yahoo.com), Feb 21 2009]

(Ln)^2 - 5*(Fn)^2 = 4*(-1)^n. Example: 11^2 - 5*5 = -4. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Mar 11 2009]

Output of Kasteleyn's formula for the number of perfect matchings of an m x n grid specializes to the Fibonacci sequence for m=2. [From Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009]

(Fib(n),Fib(n+4)) satisfies the Diophantine equation: X^2 + Y^2 - 7XY = 9*(-1)^n. [From Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 06 2009]

Number of units of a(n) belongs to a periodic sequence: 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1.We conclude that a(n) and a(n+60) have the same number of units. [From Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 05 2009]

(Fib(n),Fib(n+2)) satisfies the Diophantine equation: X^2 + Y^2 - 3XY = (-1)^n. [From Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 08 2009]

a(n+2)=A083662(A131577(n)). [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Sep 26 2009]

Mohammad K. Azarian, The Generating Function for the Fibonacci Sequence, Missouri Journal of Mathematical Sciences, Vol. 2, No. 2, Spring 1990, pp. 78-79. Zentralblatt MATH, Zbl 1097.11516.

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.

P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 70.

R. B. Banks, Slicing Pizzas, Racing Turtles and Further Adventues in Applied Mathematics, Princeton Univ. Press, 1999. See p. 84.

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 4.

Majorie Bicknell and Verner E Hoggatt, Fibonacci's Problem Book, Fibonacci Association, San Jose, Calif., 1974.

S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.

N. D. Cahill and D. A. Narayan. "Fibonacci and Lucas Numbers as Tridiagonal Matrix Determinants". Fibonacci Quarterly, 42(3):216-221, 2004. V.E. Hoggatt and C.T. Long. "Divisibility Properties of Generalized Fibonacci Polynomials"; Fibonacci Quaterly, 12:113-130, 1974 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 22 2008]

Hongwei Chen, Evaluations of Some Variant Euler Sums, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.3.

B. A. Davey and H. A. Priestley, Introduction to Lattices and Order (2nd edition), CUP, 2002. (See Exercise 1.15.)

B. Davis, 'The law of first digits' in 'Science Today'(subsequently renamed '2001')March 1980 pp. 55, Times of India, Mumbai.

Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.

Reinhardt Euler, The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.

G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.

R. P. Grimaldi, Compositions without the summand 1, Proceedings Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001). Congr. Numer. 152 (2001), 33-43.

N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954; see esp. p. 148.

J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.

V. E. Hoggatt, Jr., Fibonacci and Lucas Numbers. Houghton, Boston, MA, 1969.

E. Horowitz and S. Sahni, Fundamentals of Data Structures, Computer Science Press, 1976; p. 338.

C. W. Huegy and D. B. West, A Fibonacci tiling of the plane, Discrete Math., 249 (2002), 111-116.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 78; Vol. 3, Section 6.2.1.

Thomas Koshy, "Fibonacci and Lucas Numbers with Applications", John Wiley and Sons, 2001.

Lukovits et al., Nanotubes: Number of Kekule structures and aromaticity, J. Chem. Inf. Comput. Sci, (2003), vol. 43, 609-614. See eq. 2 on page 610.

I. Lukovits and D. Janezic, "Enumeration of conjugated circuits in nanotubes", J. Chem. Inf. Comput. Sci., vol. 44, 410-414 (2004). See Table 1 second column.

B. Malesevic: Some combinatorial aspects of differential operation composition on the space R^n, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 9 (1998), 29-33.

Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.4.

Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 49.

P. Ribenboim, The New Book of Prime Number Records, Springer, 1996.

J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978.

A. M. Robert, A Course in p-adic Analysis, Springer-Verlag, 2000; p. 213.

J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 288.

A. Sapounakis, I. Tasoulas and P. Tsikouras, On the Dominance Partial Ordering of Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.

Mark A. Shattuck and Carl G. Wagner, Periodicity and Parity Theorems for a Statistic on r-Mino Arrangements, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.6.

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

Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.

S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.

N. N. Vorob'ev, Chisla fibonachchi [Russian], Moscow, 1951. English translation, Fibonacci Numbers, Blaisdell, New York and London, 1961.

N. N. Vorobiev, Fibonacci Numbers, Birkhauser (Basel;Boston) 2002.

D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, pp. 61-7, Penguin Books 1987.

Tianping Zhang and Yuankui Ma, On Generalized Fibonacci Polynomials and Bernoulli Numbers, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.3.

A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405-469.

A. S. Posamentier & I. Lehmann, The Fabulous Fibonacci Numbers, Prometheus Books, Amherst, NY 2007.

Aimei Yu and Xuezheng Lv, "The Merrifield-Simmons indices and Hosoya indices of trees with k pendant vertices.", J. Math. Chem., Vol. 41 (2007), pp. 33-43. See page 35. - from Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Sep 01 2008

Manfred R. Schroeder, "Number Theory in Science and Communication", 5-th ed., Springer-Verlag, 2009 [From Gary W. Adamson & Alexander Povolotsky (qntmpkt(AT)yahoo.com), Feb 21 2009]

Mark A. Shattuck, Tiling proofs of some formulas for the Pell numbers of odd index, Integers, 9 (2009), 53-64.

P. W. Kasteleyn, The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice, Physica, 27(1961), 1209-1225. [From Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009]

S. Happersett, "Mathematical meditations", Journal of Mathematics and the Arts, 1 (2007), 29 - 33. [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Jan 23 2010]

N. J. A. Sloane, The first 2000 Fibonacci numbers: Table of n, F(n) for n = 0..2000

Amazing Mathematical Object Factory, Information on the Fibonacci sequences

M. Anderson et al., The Fibonacci Series

Matt Anderson, Jeffrey Frazier and Kris Popendorf, The Fibonacci series: the successor formula

Matt Anderson, Jeffrey Frazier and Kris Popendorf, The Fibonacci series: the section index

P. G. Anderson, Fibonacci Facts

Joerg Arndt, Fxtbook

Author?, Fibonacci numbers from MathTV [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Aug 02 2009]

H. Bottomley and N. J. A. Sloane, Illustration of initial terms: the Fibonacci tree

M. Boulanger, Rabbit Puzzle [Broken link?]

Brantacan, Fibonacci Numbers

J. Britton & B. V. Eeckhout, Fibonacci Interactive

C. K. Caldwell, Fibonacci Numbers

C. K. Caldwell, The Prime Glossary, Fibonacci number

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

C. Conner, Fibonacci [Broken link]

E. S. Croot, Notes on Linear Recurrence Sequences

C. Dement, Posting to Math Forum.

R. M. Dickau, Fibonacci numbers

R. Doroslovacki, Binary sequences without 011...110 (k-1 1's) for fixed k, Mat. Vesnik 46 (1994), no. 3-4, 93-98.

Enthios LLC, Fibonacci Primer

G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, Integer Sequences and Periodic Points, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3

D. Foata and G.-N. Han, Nombres de Fibonacci et polynomes orthogonaux,

I. Galkin, "Fibonacci Numbers Spelled Out"

L. Goldsmith, The Fibonacci Numbers

A. P. Hillman & G. L. Alexanderson, Algebra Through Problem Solving, Chapter 2 pp. 11-16, The Fibonacci and Lucas Numbers

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 9

Tina Hill Janzen, Fibonacci sequence / Golden scale [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Aug 02 2009]

R. Javonovic, Fibonacci Function Calculator

R. Javonovic, The relations between the Fibonacci and the Lucas numbers

R. Jovanovic, First 70 Fibonacci numbers

S. Kak, The Golden Mean and the Physics of Aesthetics

Louis H. Kauffman and Pedro Lopes, Graded forests and rational knots, Oct 19, 2007.

B. Kelly, Fibonacci and Lucas factorizations

Tanya Khovanova, Recursive Sequences

C. Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.

R. Knott, Fibonacci numbers and the golden section

R. Knott, Mathematics of the Fibonacci Series

R. Knott, Fibonacci numbers with tables of F(0)-F(500).

A. Krowne, PlanetMath.org, Fibonacci sequence

A. F. Labossiere, Sobalian Coefficients.

A. F. Labossiere, Miscellaneous.

Hendrik Lenstra, Profinite Fibonacci Numbers

M. A. Lerma, Recurrence Relations

D. Litchfield, D. Goldenheim and C. H. Dietrich, Euclid, Fibonacci and Sketchpad, Math. Teacher, 90 (1997).

B. Malesevic, Some combinatorial aspects of differential operation composition on the space R^n .

D. Merlini, R. Sprugnoli and M. C. Verri, Strip tiling and regular grammars, Theoret. Computer Sci. 242, 1-2 (2000) 109-124.

D. Merrill, The Fib-Phi Link Page

Jean-Christophe Michel, Le nombre d'or dans l'ensemble de Mandelbrot (in French, 'The golden number in the Mandelbrot set')

H. Mishima, Factorizations of many number sequences

H. Mishima, Factorizations of many number sequences

H. Mishima, Factorizations of many number sequences

H. Mishima, Factorizations of many number sequences

H. Mishima, Factorizations of many number sequences

P. Moree, Convoluted convolved Fibonacci numbers

Newton's Institute, Posters in the London Underground

J. Patterson, The Fibonacci Sequence

Ivars Peterson, Fibonacci's Missing Flowers.

S. Plouffe, Project Gutenberg, The First 1001 Fibonacci Numbers

S. Plouffe, Fibonacci numbers [Contains the first 754965 terms]

S. Rabinowitz, Algorithmic Manipulation of Fibonacci Identities (1996). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 06 2008]

Marc Renault, Properties of the Fibonacci sequence under various moduli, MSc Thesis, Wake Forest U, 1996. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Feb 07 2009]

N. Renton, The fibonacci Series

B. Rittaud, On the Average Growth of Random Fibonacci Sequences, Journal of Integer Sequences, 10 (2007), Article 07.2.4.

E. S. Rowland, Fibonacci Sequence Calculator up to n=1474

Shiva Samieinia, Digital straight line segments and curves. Licentiate Thesis. Stockholm University, Department of Mathematics, Report 2007:6.

D. Schweizer, First 500 Fibonacci Numbers in blocks of 100.

S. Silvia, Fibonacci sequence

Jaap Spies, SAGE program for computing A000045

Z.-H. Sun, Congruences For Fibonacci Numbers

Roberto Tauraso, A New Domino Tiling Sequence, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.3.

Thesaurus.Maths.org, Fibonacci sequence

K. Tognetti, Fibonacci-His Rabbits and His Numbers and Kepler

N. N. Vorob'ev, Fibonacci numbers, Springer's Encyclopaedia of Mathematics. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 06 2008]

Carl G. Wagner, Partition Statistics and q-Bell Numbers (q = -1), J. Integer Seqs., Vol. 7, 2004.

N. P. Watson, First 50 Fibonacci Numbers

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Wikipedia, Fibonacci number

Willem's Fibonacci site, Fibonacci

G. Xiao, Numerical Calculator, To display F(n), for n up to 78365,operate on "fibonacci(n)"

Index entries for "core" sequences

Index entries for related partition-counting sequences

Index entries for two-way infinite sequences

Index entries for sequences related to linear recurrences with constant coefficients

S. Happersett, Mathematical meditations [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Jan 23 2010]

G.f.: x/(1-x-x^2).

F(n)=((1+sqrt(5))^n-(1-sqrt(5))^n)/(2^n*sqrt(5)).

Alternatively, F(n) = ((1/2+sqrt(5)/2)^n-(1/2-sqrt(5)/2)^n)/sqrt(5).

F(n) = F(n-1) + F(n-2) = -(-1)^n F(-n).

F(n) = round(phi^n/sqrt(5)).

F(n+1) = Sum(0 <= j <= [n/2]; binomial(n-j, j))

E.g.f.: (2/sqrt(5))*exp(x/2)*sinh(sqrt(5)*x/2). - Len Smiley (smiley(AT)math.uaa.alaska.edu), Nov 30 2001

[0 1; 1 1]^n [0 1] = [F(n); F(n+1)]

x | F(n) ==> x | F(kn).

A sufficient condition for F(m) to be divisible by a prime p is (p - 1) divides m, if p == 1 or 4 (mod 5); (p + 1) divides m, if p == 2 or 3 (mod 5); or 5 divides m, if p = 5. (This is essentially Theorem 180 in Hardy and Wright.) - Fred W. Helenius (fredh(AT)ix.netcom.com), Jun 29, 2001

a(n)=F(n) has the property: F(n)*F(m) + F(n+1)*F(m+1) = F(n+m+1) - Miklos Kristof (kristmikl(AT)freemail.hu), Nov 13 2003

Kurmang. Aziz. Rashid (Kurmang.Rashid(AT)Btopenworld.com), Feb 21 2004, makes 4 conjectures and gives 3 theorems:

Conjecture 1: for n>=2 sqrt{F(2n+1)+F(2n+2)+F(2n+3)+F(2n+4)+2*(-1)^n}={F(2n+1)+2*(-1)^n}/F(n-1). Conjecture 2: for n>=0, {F(n+2)* F(n+3)}-{F(n+1)* F(n+4)}+ (-1)^n = 0.

Conjecture 3: for n>=0, F(2n+1)^3 - F(2n+1)*[(2*A^2) -1] - [A + A^3]=0, where A= {F(2n+1)+sqrt{5*F(2n+1)^2 +4}}/2

Conjecture 4: for x>=5, if x is a Fibonacci number >= 5 then g*x*[{x+sqrt{5*(x^2) +- 4}}/2]*[2x+{{x+sqrt{5*(x^2) +- 4}}/2}]*[2x+{{3x+3*sqrt {5*(x^2) +- 4}}/2}]^2+[2x+{{x+sqrt{5*(x^2) +- 4}}/2}] +- x*[2x+{{3x+3*sqrt{5*(x^2) +- 4}}/2}]^2 -x*[2x+{{x+sqrt{5*(x^2) +- 4}}/2}]*[x+{{x+sqrt{5*(x^2) +- 4}}/2}]* [2x+ {{3x+3*sqrt{5*(x^2) +- 4}}/2}]^2= 0, where g = {1 + sqrt 5 /2}.

Theorem 1: for n>=0, {F(n+3)^ 2 - F(n+1)^ 2}/F(n+2)={F(n+3)+ F(n+1)}. Theorem 2: for n>=0, F(n+10) = 11* F(n+5) + F(n). Theorem 3: for n>=6, F(n) = 4* F(n-3) + F(n-6).

Conjecture 2 of Rashid is actually a special case of the general law F(n)*F(m) + F(n+1)*F(m+1) = F(n+m+1) (take n <- n+1 and m <- -(n+4) in this law). - Harmel Nestra (harmel.nestra(AT)ut.ee), Apr 22 2005

Conjecture: for all c such that 2-Phi <= c < 2*(2-Phi) we have F(n) = floor(Phi*a(n-1)+c) for n > 2 - Gerald McGarvey (Gerald.McGarvey(AT)comcast.net), Jul 21 2004

|2*Fib(n) - 9*Fib(n+1)| = 4*A000032(n) + A000032(n+1). - Creighton Dement (creighton.k.dement(AT)uni-oldenburg.de), Aug 13 2004

For x > Phi, Sum n=0..inf F(n)/x^n = x/(x^2 - x - 1) - Gerald McGarvey (gerald.mcgarvey(AT)comcast.net), Oct 27 2004

F(n+1) = exponent of the n-th term in the series f(x, 1) determined by the equation f(x, y) = xy + f(xy, x). - Jonathan Sondow (jsondow(AT)alumni.princeton.edu), Dec 19 2004

a(n-1)=sum(k=0, n, (-1)^k*binomial(n-ceil(k/2), floor(k/2))) - Benoit Cloitre (benoit7848c(AT)orange.fr), May 05 2005

F(n+1)=sum{k=0..n, binomial((n+k)/2, (n-k)/2)(1+(-1)^(n-k))/2}; - Paul Barry (pbarry(AT)wit.ie), Aug 28 2005

Fibonacci(n)=Product(1 + 4[cos(j*Pi/n)]^2, j=1..ceil(n/2)-1). [Bicknell and Hoggatt, pp. 47-48] - Emeric Deutsch, Oct 15 2006

F(n)=2^-(n-1)*sum{k=0..floor((n-1)/2), binomial(n,2*k+1)*5^k}; - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Feb 07 2006

a(n)=(b(n+1)+b(n-1))/n where {b(n)} is the sequence A001629 - Sergio Falcon (sfalcon(AT)dma.ulpgc.es), Nov 22 2006

F(n*m) = Sum{k = 0..m, binomial(m,k)*F(n-1)^k*F(n)^(m-k)*F(m-k)}. The generating function of F(n*m) (n fixed, m = 0,1,2...) is G(x) = F(n)*x / ((1-F (n-1)*x)^2-F(n)*x*(1-F(n-1)*x)-( F(n)*x)^2). E.g. F(15) = 610 = F(5*3) = binomial(3,0)* F(4)^0*F(5)^3*F(3) + binomial(3,1)* F(4)^1*F(5)^2*F(2) + binomial(3,2)* F(4)^2*F(5)^1*F(1) + binomial(3,3)* F(4)^3*F(5)^0*F(0) = 1*1*125*2 + 3*3*25*1 + 3*9*5*1 + 1*27*1*0 = 250 + 225 + 135 + 0 = 610 - Miklos Kristof, Feb 12 2007

Comments from Miklos Kristof (kristmikl(AT)freemail.hu), Mar 19 2007 (Start)

Let L(n)=A000032=Lucas numbers. Then:

For a>=b and odd b, F(a+b)+F(a-b)=L(a)*F(b).

For a>=b and even b, F(a+b)+F(a-b)=F(a)*L(b).

For a>=b and odd b, F(a+b)-F(a-b)=F(a)*L(b).

For a>=b and even b, F(a+b)-F(a-b)=L(a)*F(b).

F(n+m)+(-1)^m*F(n-m)=F(n)*L(m);

F(n+m)-(-1)^m*F(n-m)=L(n)*F(m);

F(n+m+k)+(-1)^k*F(n+m-k)+(-1)^m*(F(n-m+k)+(-1)^k*F(n-m-k))=F(n)*L(m)*L(k);

F(n+m+k)-(-1)^k*F(n+m-k)+(-1)^m*(F(n-m+k)-(-1)^k*F(n-m-k))=L(n)*L(m)*F(k);

F(n+m+k)+(-1)^k*F(n+m-k)-(-1)^m*(F(n-m+k)+(-1)^k*F(n-m-k))=L(n)*F(m)*L(k);

F(n+m+k)-(-1)^k*F(n+m-k)-(-1)^m*(F(n-m+k)-(-1)^k*F(n-m-k))=5*F(n)*F(m)*F(k). (End)

Fib(n)=b(n)+(p-1)*sum{1<k<n, floor(b(k)/p)*Fib(n-k+1)} where b(k) is the digital sum analogue of the Fibonacci recurrence, defined by b(k)=ds_p(b(k-1))+ds_p(b(k-2)), b(0)=0, b(1)=1, ds_p=digital sum base p. Example for base p=10: Fib(n)=A010077(n)+9*sum{1<k<n, A059995(A010077(k))*Fib(n-k+1)}. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jul 01 2007

Fib(n)=b(n)+p*sum{1<k<n, floor(b(k)/p)*Fib(n-k+1)} where b(k) is the digital product analogue of the Fibonacci recurrence, defined by b(k)=dp_p(b(k-1))+dp_p(b(k-2)), b(0)=0, b(1)=1, dp_p=digital product base p. Example for base p=10: Fib(n)=A074867(n)+10*sum{1<k<n, A059995(A074867(k))*Fib(n-k+1)}. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jul 01 2007

a(n) = denominator of continued fraction [1,1,1,...], (with n ones); e.g. 2/3 = continued fraction [1,1,1]; where barover[1] = [1,1,1...] = .6180339,... - Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 29 2007

F(n + 3) = 2F(n + 2) - F(n), F(n + 4) = 3F(n + 2) - F(n), F(n + 8) = 7F(n + 4) - F(n), F(n + 12) = 18F(n + 6) - F(n). - Paul Curtz (bpcrtz(AT)free.fr), Feb 01 2008

1 = 1/(1*2) + 1/(1*3) + 1/(2*5) + 1/(3*8) + 1/(5*13) + ... = 1/2 + 1/3 + 1/10 + 1/24 + 1/65 + 1/168 + ...; where A059929 = (0, 2, 3, 10, 24, 65, 168,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Mar 16 2008

a(2^n) = prod{i=0}^{n-2}B(i) where B(i) is A001566. Example 3*7*47 = Fib(16) - Kenneth J Ramsey (Ramsey2879(AT)msn.com), Apr 23 2008

F(n) = (1/(n-1)!) * [ n^(n-1) - { C(n-2,0) +4*C(n-2,1) +3*C(n-2,2) }*n^(n-2) + { 10*C(n-3,0) +49*C(n-3,1) +95*C(n-3,2) +83*C(n-3,3) +27*C(n-3,4) }*n^(n-3) - { 90*C(n-4,0) +740*C(n-4,1) +2415*C(n-4,2) +4110*C(n-4,3) +3890*C(n-4,4) +1950*C(n-4,5) +405*C(n-4,6) }*n^(n-4) + ..... ]. - Andre F. Labossiere (boronali(AT)laposte.net), Nov 24 2004

a(n+1)=Sum_{k, 0<=k<=n} A109466(n,k)*(-1)^(n-k). [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 26 2008]

Formula from Thomas Wieder (wieder.thomas(AT)t-online.de), Feb 25 2009:

a(n) = sum_{l_1=0}^{n+1} sum_{l_2=0}^{n}...sum_{l_i=0}^{n-i}...sum_{l_n=0}^{1}

delta(l_1,l_2,...,l_i,...,l_n)

where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i + l_(i+1) >= 2 for i=1..n-1

and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise.

sage: taylor( mul((x^2)/(1-x^2-x^4) for i in xrange(0,1)),x,0,77)#solution>> x^2 + x^4 + 2*x^6 + 3*x^8 + 5*x^10 + 8*x^12 + 13*x^14 + 21*x^16 + 34*x^18 + 55*x^20 + 89*x^22 + 144*x^24 + 233*x^26 + 377*x^28 +....+ 514229*x^58 + 832040*x^60 + 1346269*x^62 +2178309*x^64 + 3524578*x^66 + 5702887*x^68 + 9227465*x^70 +14930352*x^72 + 24157817*x^74 + 39088169*x^76 etc... [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 01 2009]

2^n (\prod _{k=1}^n \sqrt[4]{\cos^2(k\pi/(n+1))+1/4})^2 (Kasteleyn's formula specialized) [From Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009]

Contribution from Cino Hilliard (hillcino368(AT)gmail.com), Sep 15 2008: (Start)

For x = 0,1,2,3,4 x=1/(x+1) = 1, 1/2, 2/3, 3/5, 5/8, These fractions have

numerators 1,1,2,3,5 the 2nd to 6-th entries in the sequence. (End)

with(combinat): A000045 := proc(n) fibonacci(n); end;

ZL:=[S, {a = Atom, b = Atom, S = Prod(X, Sequence(Prod(X, b))), X = Sequence(b, card >= 1)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=0..38); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 04 2008

spec := [ B, {B=Sequence(Set(Z, card>1))}, unlabeled ]: seq(combstruct[count](spec, size=n), n=1..39); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 04 2008

sage: [lucas_number1(n, 1, -1) for n in xrange(0, 39)] # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 22 2009]

Table[ Fibonacci[ k ], {k, 1, 50} ]

2^(n) Product[((Cos[Pi k/(n + 1)])^2 + (Cos[Pi 1/3])^2)^(1/4), {k, n}] Product[((Cos[Pi k/(n + 1)])^2 + (Cos[Pi 2/3])^2)^(1/4), {k, n}] (Kasteleyn's formula specialized) [From Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009]

(AXIOM) [fibonacci(n) for n in 0..50]

(MAGMA) F := func< n | Fibonacci(n) >;

(PARI) a(n)=fibonacci(n)

(PARI) a(n)=imag(quadgen(5)^n)

(PARI) a(n)=if(n<0, -(-1)^n*a(-n), if(n<2, n, a(n-1)+a(n-2)))

# Python program from Jaap Spies, Jan 05, 2007 (Change leading dots to blanks.)

.def fib():

... """

....... generates an "infinity" of Fibonacci numbers,

....... starting with 1

... """

... x, y = 0, 1

... while 1:

....... x, y = y, x+y

....... yield x

................

.f = fib()

.a = [f.next() for i in range(1000)] # 1000 or more

.a.insert(0, 0)

................

.def A000045(n):

... """ returns Fibonacci number with index n, offset 0, 4 """

... return a[n]

................

.def A000045_list(N):

... """ returns a list of the first n Fibonacci numbers """

... return a[:N]

................

# (SAGE) Demonstration program from Jaap Spies:

# To see which functions are available type: sloane.A[tab]

# All builtin SAGE programs are called the same way:

# a = sloane.A000045; a # This returns the name of the sequence

# a(n) # This returns the n-th number of the sequence:

# a.list(n) # This returns a list of the first n numbers:

# Copy and paste the following into a worksheet or the interpreter:

a = sloane.A000045; print a

print a(0)

print a(1)

print a(2)

print a(38)

print a.list(39)

sage: from sage.combinat.sloane_functions import recur_gen2 sage: it = recur_gen2(0, 1, 1, 1) sage: [it.next() for i in range(30)] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 25 2008

(PARI) x=0; for(j=0, 100, x=1/(x+1); print1(numerator(x)", ")) [From Cino Hilliard (hillcino368(AT)gmail.com), Sep 15 2008]

Contribution from Cino Hilliard (hillcino368(AT)hotmail.com), Apr 29 2009: (Start)

(PARI) /*Generate Fibonnaci Sequence without arrays */

fib(n) =

{

local(a=0, b=1);

print1(a", "b", ");

for(x=3, n, c=a+b;

print1(c", ");

a=b; b=c;

);

}

(Sage) taylor( mul((x^2)/(1-x^2-x^4) for i in xrange(0, 1)), x, 0, 77)# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 01 2009]

Contribution from Gerald McGarvey (gerald.mcgarvey(AT)comcast.net), Sep 29 2009: (Start)

(Haskell) Based on code

-- from http://www.haskell.org/haskellwiki/The_Fibonacci_sequence

-- which also has other versions.

fib :: Int -> Integer

fib n = fibs !! n

.. where

.... fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

{- Example of use: map fib [0..38] -} (End)

Cf. A039834 (signed Fibonacci numbers).

Cf. A000213, A000288, A000322, A000383, A060455, A030186, A039834, A020695, A020701, A071679.

Cf. A099731, A100492, A094216, A094638, A000108, A101399, A101400.

First row of array A103323. Second row of array A099390.

Row 2 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).

a(n) = A094718(4, n). a(n) = A101220(0, j, n).

A000032(n)=F(n+1)+F(n-1). Cf. A060441.

a(k) = A090888(0, k+1) = A118654(0, k+1) = A118654(1, k-1) = A109754(0, k) = A109754(1, k-1), for k > 0.

Cf. A059929.

A144152 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 12 2008]

A152063 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 22 2008]

Sequence in context: A132636 A152163 A039834 this_sequence A020695 A132916 A069041

Adjacent sequences: A000042 A000043 A000044 this_sequence A000046 A000047 A000048

core,nonn,easy,nice,new

N. J. A. Sloane (njas(AT)research.att.com).

Edited by Charles R Greathouse IV (charles.greathouse(AT)case.edu), Oct 30 2009

0,3

The solution to Schroeder's first problem. A very large number of combinatorial interpretations are known - see references, esp. Stanley, Enumerative Combinatorics, Volume 2.

Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g. for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).

Consider all the binomial(2n,n) paths on squared paper that (i) start at (0, 0), (ii) end at (2n, 0) and (iii) at each step, either make a (+1,+1) step or a (+1,-1) step. Then the number of such paths which never go never below the x-axis is C(n) [Chung-Feller]

a(n) is the number of ordered rooted trees with n nodes, not including the root. See the Conway-Guy reference where these rooted ordered trees are called plane bushes. See also the Bergeron et al. reference, Example 4, p. 167. W. Lang Aug 07 2007.

Shifts one place left when convolved with itself.

For n >= 1 a(n) is also the number of rooted bicolored unicellular maps of genus 0 on n edges. - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 15 2001

Ways of joining 2n points on a circle to form n nonintersecting chords. (If no such restriction imposed, then ways of forming n chords is given by (2n-1)!!=(2n)!/n!2^n=A001147(n).)

Arises in Schubert calculus - see Sottile reference.

Inverse Euler transform of sequence is A022553.

With interpolated zeros, the inverse binomial transform of the Motzkin numbers A001006. - Paul Barry (pbarry(AT)wit.ie), Jul 18 2003

The Hankel transforms of this sequence or of this sequence with the first term omitted give A000012 = 1, 1, 1, 1, 1, 1, ...; example : Det([1, 1, 2, 5; 1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132]) = 1 and Det([1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132; 14, 42, 132, 429]) = 1 . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Mar 04 2004

c(n) = C(2*n-2,n-1)/n = (1/n!) * [ n^(n-1) + { C(n-2,1) +C(n-2,2) }*n^(n-2) + { 2*C(n-3,1) +7*C(n-3,2) +8*C(n-3,3) +3*C(n-3,4) }*n^(n-3) + { 6*C(n-4,1) +38*C(n-4,2) +93*C(n-4,3) +111*C(n-4,4) +65*C(n-4,5) +15*C(n-4,6) }*n^(n-4) + ..... ]. - Andre F. Labossiere (boronali(AT)laposte.net), Nov 10 2004

Sum_{n=0..infinity} 1/a(n) = 2 + 4*Pi/3^(5/2) = F(1,2;1/2;1/4) = 2.806133050770763... (see L'Universe de Pi link) - Gerald McGarvey and Benoit Cloitre, Feb 13 2005

a(n) equals sum of squares of terms in row n of triangle A053121, which is formed from successive self-convolutions of the Catalan sequence. - Paul D. Hanna (pauldhanna(AT)juno.com), Apr 23 2005

Comment from Donald D. Cross (cosinekitty(AT)hotmail.com), Feb 04 2005: Also coefficients of the Mandelbrot polynomial M iterated an infinite number of times. Examples: M(0) = 0 = 0*c^0 = [0], M(1) = c = c^1 + 0*c^0 = [1 0], M(2) = c^2 + c = c^2 + c^1 + 0*c^0 = [1 1 0], M(3) = (c^2 + c)^2 + c = [0 1 1 2 1], ... ... M(5) = [0 1 1 2 5 14 26 44 69 94 114 116 94 60 28 8 1], ...

The multiplicity with which a prime p divides C_n can be determined by first expressing n+1 in base p. For p=2, the multiplicity is the number of 1 digits minus 1. For p an odd prime, count all digits greater than (p+1)/2; also count digits equal to (p+1)/2 unless final; and count digits equal to (p-1)/2 if not final and the next digit is counted. For example, n=62, n+1 = 223_5, so C_62 is not divisible by 5. n=63, n+1 = 224_5, so 5^3 | C_63. - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Feb 08 2006

Koshy and Salmassi give an elementary proof that the only prime Catalan numbers are a(2) = 2 and a(3) = 5. Is the only semiprime Catalan number a(4) = 14? - Jonathan Vos Post (jvospost3(AT)gmail.com), Mar 06 2006

Comment from Franklin T. Adams-Watters, Apr 14 2006: The answer is yes. Using the formula C_n = C(2n,n)/(n+1), it is immediately clear that C_n can have no prime factor greater than 2n. For n >= 7, C_n > (2n)^2, so it cannot be a semiprime. Given that the Catalan numbers grow exponentially, the above consideration implies that the number of prime divisors of C_n, counted with multiplicity, must grow without limit. The number of distinct prime divisors must also grow without limit, but this is more difficult. Any prime between n+1 and 2n (exclusive) must divide C_n. That the number of such primes grows without limit follows from the prime number theorem.

The number of ways to place n indistinguishable balls in n numbered boxes B1,...,Bn such that at most a total of k balls are placed in boxes B1,...,Bk for k=1,...,n. For example, a(3)=5 since there are 5 ways to distribute 3 balls among 3 boxes such that (i) box 1 gets at most 1 ball and (ii)box 1 and box 2 together get at most 2 balls:(O)(O)(O), (O)()(OO), ()(OO)(O), ()(O)(OO), ()()(OOO). - Dennis P. Walsh (dwalsh(AT)mtsu.edu), Dec 04 2006

a(n) is also the order of the semigroup of order-decreasing and order-preserving full transformations (of an n-element chain) - now known as the Catalan monoid [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]

a(n) is the number of trivial representations in the direct product of 2n spinor (the smallest) representations of the group SU(2) (A(1)). [From Rutger Boels (boels(AT)nbi.dk), Aug 26 2008]

The invert transform appears to converge to the catalan numbers when applied infinitely many times to any starting sequence. [From Mats O. Granvik, Gary W. Adamson and Roger L. Bagula (mgranvik(AT)abo.fi), Sep 09 2008, Sep 12 2008]

lim(a(n)/a(n-1): n->infinity) = 4 [From Francesco Antoni (francesco_antoni(AT)yahoo.com), Nov 24 2008]

Starting with offset 1 = row sums of triangle A154559 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 11 2009]

Contribution from Benji Fisher (benji(AT)FisherFam.org), Mar 05 2009: (Start)

C(n) is the degree of the Grassmanian G(1,n+1): the set of lines in

(n+1)-dimensional projective space, or the set of planes through the origin in

(n+2)-dimensional affine space. The Grassmanian is considered a subset of

N-dimensional projective space, N = binomial(n+2,2) - 1. If we choose 2n

general (n-1)-planes in projective (n+1)-space, then there are C(n) lines that

meet all of them. (End)

Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), May 01 2009: (Start)

Starting with offset 1 = A068875: (1, 2, 4, 10, 18, 84,...) convolved with

Fine numbers, A000957: (1, 0, 1, 2, 6, 18,...). a(6) = 132 =

(1, 2, 4, 10, 28, 84) dot (18, 6, 2, 1, 0, 1) = (18 + 12 + 8 + 10 + 0 + 84) = 132. (End)

Convolved with A032443: (1, 3, 11, 42, 163,...) = powers of 4, A000302: (1, 4, 16,...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 15 2009]

Sum{k=1...Infinity,c(k-1)/2^(2k-1)}=1. The kth term in the summation is the probability that a random walk on the integers (begining at the origin) will arrive at positive one (for the first time) in exactly (2k-1) steps. [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Sep 12 2009]

C(p+q)-C(p)*C(q)=sum(C(i)*C(j)*C(p+q-i-j-1), i=0..(p-1), j=0..(q-1) ) [From Groux roland (roland.groux(AT)orange.fr), Nov 13 2009]

The large number of references and links demonstrates the ubiquity of the Catalan numbers.

M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.

R. Alter, Some remarks and results on Catalan numbers, pp. 109-132 in Proceedings of the Louisiana Conference on Combinatorics, Graph Theory and Computer Science. Vol. 2, edited R. C. Mullin et al., 1971.

R. Alter and K. K. Kubota, Prime and prime power divisibility of Catalan numbers, J. Combinatorial Theory, Ser. A, 15 (1973), 243-256.

Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906v1, Discrete Math., 308 (2008), 4660-4669.

D. F. Bailey, Counting Arrangements of 1's and -1's, Mathematics Magazine 69(2) 128-131 1996.

I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765-785.

E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Permutations avoiding an increasing number of length-increasing forbidden subsequences, Discrete Mathematics and Theoretical Computer Science 4, 2000, 31-44.

E. Barcucci, A. Frosini and S. Rinaldi, On directed-convex polyominoes in a rectangle, Discr. Math., 298 (2005). 62-78.

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-like Structures, EMA vol.67, Cambridge, 1998, p. 163, 167, 168, 252, 256, 291.

Matthew Bennett, Vyjayanthi Chari, R.J. Dolbin and Nathan Manning, Square Partitions and Catalan Numbers, arXiv: 0912.4983v1.

F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.

A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, Permutations defining convex permutominoes, preprint, 2007.

M. Bona and B. E. Sagan, On Divisibility of Narayana Numbers by Primes, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.4.

W. G. Brown, Historical note on a recurrent combinatorial problem, Amer. Math. Monthly, 72 (1965), 973-977.

D. Callan, A combinatorial interpretation of a Catalan numbers identity, Math. Mag., 72 (1999), 295-298.

D. Callan, The maximum associativeness of division, Problem 11091, Amer. Math. Monthly, 113 (#5, 2006), 462-463.

David Callan, A Combinatorial Interpretation for a Super-Catalan Recurrence, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.8.

David Callan, A Combinatorial Interpretation of the Eigensequence for Composition, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4.

Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.

Chung, Kai Lai; Feller, W., On fluctuations in coin-tossing. Proc. Nat. Acad. Sci. U. S. A. 35, (1949). 605-608.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 53.

J. H. Conway and R. K. Guy, The Book of Numbers, New York: Springer-Verlag, 1995, ch. 4, pp 96-106.

S. J. Cyvin and I. Gutman, Kekule structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see pp. 183, 196, etc.).

E. Deutsch, Dyck path enumeration, Discrete Math., 204, 167-202, 1999.

E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bulletin of the Institute of Combinatorics and its Applications, 31, 31-38, 2001.

S. Dulucq and J.-G. Penaud, Cordes, arbres et permutations. Discrete Math. 117 (1993), no. 1-3, 89-105.

A. Errara, Analysis situs: une probleme d'enumeration, Memoires Acad. Bruxelles, Series 2, Vol. 11, No. 6, 26pp.

K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc., 10 (1997), 139-167.

Philippe Flajolet, Eric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics, arXiv:math.CO/0606370

Dominique Foata and Guo-Niu Han, Dimers and new q-tangent numbers, Preprint, 2008.

Dominique Foata and Guo-Niu Han, The dimer polynomial triangle, Preprint, 2008.

D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb Thy A 80 380-384 1997.

H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45, 1961, 199-201.

J. R. Gaggins, Constructing the Centroid of a Polygon, Math. Gaz., 61 (1988), 211-212.

M. Gardner, Time Travel and Other Mathematical Bewilderments, Chap. 20 pp. 253-266 W. H. Freeman NY 1988.

James Gleick, Faster, Vintage Books, NY, 2000 (see pp. 259-261).

H. W. Gould, Research bibliography of two special number sequences, Mathematica Monongaliae, Vol. 12, 1971.

Alain Goupil and Gilles Schaeffer, Factoring N-Cycles and Counting Maps of Given Genus . Europ. J. Combinatorics (1998) 19 819-834.

M. Griffiths, The Backbone of Pascal's Triangle, United Kingdom Mathematics Trust (2008), 53-63 and 85-93. [From Martin Griffiths (griffm(AT)essex.ac.uk), Mar 28 2009]

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 530.

N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.23).

J. Harris, Algebraic Geometry: A First Course (GTM 133), Springer-Verlag, 1992, pages 245-247. [From Benji Fisher (benji(AT)FisherFam.org), Mar 05 2009]

S. Heubach, N. Y. Li and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math., 308 (2008), 5954-5964.

Higgins, Peter M. Combinatorial results for semigroups of order-preserving mappings. Math. Proc. Camb. Phil. Soc. (1993), 113: 281-296. [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]

B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 513, Eq. (7.282).

R. H. Jeurissen, Raney and Catalan, Discrete Math., 308 (2008), 6298-6307.

M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.6.

Thomas Koshy and Mohammad Salmassi, "Parity and Primality of Catalan Numbers", College Mathematics Journal, Vol. 37, No. 1 (Jan 2006), pp. 52-53.

M. Kosters, A theory of hexaflexagons, Nieuw Archief Wisk., 17 (1999), 349-362.

Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.

Laradji, A. and Umar, A. On certain finite semigroups of order-decreasing transformations I, Semigroup Forum 69 (2004), 184-200 [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]

P. J. Larcombe, On pre-Catalan Catalan numbers: Kotelnikow (1766), Mathematics Today, 35 (1999), p. 25.

P. J. Larcombe, On the history of the Catalan numbers: a first record in China, Mathematics Today, 35 (1999), p. 89.

P. J. Larcombe, The 18th century Chinese discovery of the Catalan numbers, Math. Spectrum, 32 (1999/2000), 5-7.

P. J. Larcombe and P. D. C. Wilson, On the trail of the Catalan sequence, Mathematics Today, 34 (1998), 114-117.

P. J. Larcombe and P. D. C. Wilson, On the generating function of the Catalan sequence: a historical perspective, Congress. Numer., 149 (2001), 97-108.

G. S. Lueker, Some techniques for solving recurrences, Computing Surveys, 12 (1980), 419-436.

J. J. Luo, Antu Ming, the first inventor of Catalan numbers in the world [in Chinese], Neimenggu Daxue Xuebao, 19 (1998), 239-245.

Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.

Toufik Mansour and Simone Severini, Enumeration of (k,2)-noncrossing partitions, Discrete Math., 308 (2008), 4570-4577.

D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344.

A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405-469.

Liviu I. Nicolaescu, Counting Morse functions on the 2-sphere, arXiv:math/0512496.

C. O. Oakley and R. J. Wisner, Flexagons, Amer. Math. Monthly, 64 (1957), 143-154.

A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195 (see Eq. 4).

Robert Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

S. G. Penrice, Stacks, bracketings and CG-arrangements, Math. Mag., 72 (1999), 321-324.

C. A. Pickover, Wonders of Numbers, Chap. 71, Oxford Univ. Press NY 2000.

Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.

R. Read, "Counting Binary Trees" in 'The Mathematical Gardner', D. A. Klarner Ed. pp. 331-334, Wadsworth CA 1989.

J.-L. Remy, Un procede iteratif de denombrement d'arbres binaires et son application a leur generation aleatoire, RAIRO Inform. Theor. 19 (1985), 179-195.

J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.

J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.

T. Santiago Costa Oliveira, "Catalan traffic" and integrals on the Grassmannian of lines, Discr. Math., 308 (2007), 148-152.

A. Sapounakis, I. Tasoulas and P. Tsikouras, On the Dominance Partial Ordering of Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.

J. A. von Segner, Enumeratio modorum, quibus figurae planae rectilineae per diagonales dividuntur in triangula, Novi Comm. Acad. Scient. Imper. Petropolitanae, 7 (1758/1759), 203-209.

L. W. Shapiro, A short proof of an identity of Touchard's concerning Catalan numbers, J. Combin. Theory, A 20 (1976), 375-376.

L. W. Shapiro, W.-J. Woan and S. Getu, The Catalan numbers via the World Series, Math. Mag., 66 (1993), 20-22.

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

Solomon, A. Catalan monoids, monoids of local endomorphisms and their presentations. Semigroup Forum 53 (1996), 351--368 [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]

Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.

R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986, Vol. 2, 1999; see especially Chapter 6.

R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.

Zhi-Wei Sun and Roberto Tauraso, Congruences involving Catalan numbers, arXiv:0709.1665v5.

I. Vun and P. Belcher, Catalan numbers, Mathematical Spectrum, 30 (1997/1998), 3-5.

D. Wells, Penguin Dictionary of Curious and Interesting Numbers, Entry 42 p 121, Penguin Books, 1987.

Wen-jin Woan, A Recursive Relation for Weighted Motzkin Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.6.

Wen-jin Woan, A Relation Between Restricted and Unrestricted Weighted Motzkin Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.7.

Wen-jin Woan, Animals and 2-Motzkin Paths, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.6.

F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.

N. J. A. Sloane, The first 200 Catalan numbers

Joerg Arndt, Fxtbook

M. Azaola and F. Santos, The number of triangulations of the cyclic polytope C(n,n-4), Discrete Comput. Geom., 27 (2002), 29-48. (C(n) = number of triangulations of cyclic polytope C(n,2).)

John Baez, This week's finds in mathematical physics, Week 202

E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Permutations avoiding an increasing number of length-increasing forbidden subsequences

M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.

D. Bill, Durango Bill's Enumeration of Binary Trees

H. Bottomley, Catalan Space Invaders

H. Bottomley, Illustration for A000108, A001147, A002694, A067310 and A067311

T. Bourgeron, Montagnards et polygones

M. Bousquet-Melou and Gilles Schaeffer, Walks on the slit plane, Probability Theory and Related Fields, Vol. 124, no. 3 (2002), 305-344.

K. S. Brown's Mathpages, The Meanings of Catalan Numbers

B. Bukh, PlanetMath.org, Catalan numbers

Alexander Burstein, Sergi Elizalde and Toufik Mansour, Restricted Dumont permutations, Dyck paths and noncrossing partitions, arXiv math.CO/0610234.

N. T. Cameron, Random walks, trees and extensions of Riordan group techniques

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).

Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, Counting Biorders, J. Integer Seqs., Vol. 6, 2003.

T. Davis, Catalan Numbers

E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.

R. M. Dickau, Catalan numbers

R. M. Dickau, Catalan Numbers (another copy)

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 18, 35

D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence

I. Galkin, Enumeration of the Binary Trees(Catalan Numbers)

H. W. Gould, Congr. Numer. 165 (2003) p 33-38.

B. Gourevitch, L'univers de Pi (click Mathematiciens, Gosper)

R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 48

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 52

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 71

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 76

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 284

I. Jensen, Series exapansions for self-avoiding polygons

S. Johnson, The Catalan Numbers

A. Karttunen, Illustration of initial terms up to size n=7

C. Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.

A. F. Labossiere, Sobalian Coefficients.

A. F. Labossiere, Miscellaneous.

W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

Colin L. Mallows and Lou Shapiro, Balls on the Lawn, J. Integer Sequences, Vol. 2, 1999, #5.

Toufik Mansour, Counting Peaks at Height k in a Dyck Path, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.1

R. J. Marsh and P. P. Martin, Pascal arrays: counting Catalan sets

D. Merlini, R. Sprugnoli and M. C. Verri, Waiting patterns for a printer, FUN with algorithm'01, Isola d'Elba, 2001.

A. Panayotopoulos and P. Tsikouras, Meanders and Motzkin Words, J. Integer Seqs., Vol. 7, 2004.

A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195 (see Eq. 4).

P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.

P. Peart and W.-J. Woan, Dyck Paths With No Peaks at Height k, J. Integer Sequences, 4 (2001), #01.1.3.

K. A. Penson and J.-M. Sixdeniers, Integral Representations of Catalan and Related Numbers, J. Integer Sequences, 4 (2001), #01.2.5.

A. Sapounakis and P. Tsikouras, On k-colored Motzkin words, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.5.

N. J. A. Sloane, Illustration of initial terms

Frank Sottile, The Schubert Calculus of Lines (a section of Enumerative Real Algebraic Geometry)

R. P. Stanley, Hipparchus, Plutarch, Schr"oder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.

R. P. Stanley, Exercises on Catalan and Related Numbers

R. P. Stanley, Catalan Addendum

Zhi-Wei Sun, A combinatorial identity with application to Catalan numbers

D. Taylor, Catalan Structures(up to C(7))

G. Villemin's Almanac of Numbers, Nombres De Catalan

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (1).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (3).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (4).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (5).

Eric Weisstein's World of Mathematics, Dyck Path

W.-J. Woan, Hankel Matrices and Lattice Paths, J. Integer Sequences, 4 (2001), #01.1.2.

Index entries for "core" sequences

Index entries for sequences related to rooted trees

Index entries for sequences related to parenthesizing

Index entries for sequences related to necklaces

V.S. Sunder, Catalan numbers [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Dec 19 2009]

a(n) = binomial(2n, n)/(n+1) = (2n)!/(n!(n+1)!).

a(n) = binomial(2n, n)-binomial(2n, n-1)

a(n) = Sum_{k=0..n-1} a(k)a(n-1-k).

G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x). G.f. A(x) satisfies A = 1 + x*A^2.

a(n+1) = Sum_{i} binomial(n, 2*i)*2^(n-2*i)*a(i) - Touchard.

2(2n-1)a(n-1) = (n+1)a(n).

It is known that a(n) is odd if and only if n=2^k-1, k=1, 2, 3, ... - Emeric Deutsch, Aug 04 2002.

Using the Stirling approximation in A000142 we get the asymptotic expansion a(n) ~ 4^n / (sqrt(Pi * n) * (n + 1)). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 13 2001

Integral representation: a(n)=int(x^n*sqrt((4-x)/x), x=0..4)/(2*Pi). - Karol A. Penson (penson(AT)lptl.jussieu.fr), Apr 12 2001

E.g.f.: exp(2x) (I_0(2x)-I_1(2x)), where I_n is Bessel function. - Karol A. Penson (penson(AT)lptl.jussieu.fr), Oct 07 2001

Polygorial(n, 6)/Polygorial(n, 3) - Daniel Dockery (peritus(AT)gmail.com) Jun 24, 2003

G.f. A(x) satisfies ((A(x)+A(-x))/2)^2 = A(4*x^2). - Michael Somos, Jun 27, 2003

G.f. A(x) satisfies Sum_{k>=1} k(A(x)-1)^k = Sum_{n >= 1} 4^{n-1} x^n. - Shapiro, Woan, Getu

a(n+m) = Sum_{k} A039599(n, k)*A039599(m, k). - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Dec 22 2003

a(n+1) = (1/(n+1))*sum_{k=0..n} a(n-k)*binomial(2k+1, k+1) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Jan 24 2004

a(n) = Sum_{k>=0} A008313(n, k)^2 . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Feb 14 2004

a(m+n+1) = Sum_{k>=0} A039598(m, k)*A039598(n, k) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Feb 15 2004

a(n)=sum{k=0..n, (-1)^k*2^(n-k)*binomial(n, k)*binomial(k, floor(k/2))} - Paul Barry (pbarry(AT)wit.ie), Jan 27 2005

a(n) = Sum_{k=0..[n/2]} ((n-2*k+1)*C(n, n-k)/(n-k+1))^2, which is equivalent to: a(n) = Sum_{k=0..n} A053121(n, k)^2, for n>=0. - Paul D. Hanna (pauldhanna(AT)juno.com), Apr 23 2005

a((m+n)/2) = Sum_{k>=0} A053121(m, k)*A053121(n, k) if m+n is even . - Philippe DELEHAM, May 26 2005

E.g.f. Sum_{n>=0} a(n)*x^(2n)/(2n)! = BesselI(1, 2x)/x . - Michael Somos Jun 22 2005

Given g.f. A(x), then B(x)=x*A(x^3) satisfies 0=f(x, B(X)) where f(u, v)=u-v+(uv)^2 or B(x)=x+(x*B(x))^2 which implies B(-B(x))=-x and also (1+B^3)/B^2 = (1-x^3)/x^2 . - Michael Somos Jun 27 2005

a(n) = a(n-1)*(4-6/(n+1)). a(n) = 2a(n-1)*(8a(n-2)+a(n-1))/(10a(n-2)-a(n-1)). - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Feb 08 2006

Sum_{k=1}^{infinity} a(k)/4^k = 1. - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Jun 28 2006

a(n) = A047996(2*n+1,n) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Jul 25 2006

Binomial transform of A005043 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 20 2006

a(n)=Sum_{k, 0<=k<=n}(-1)^k*A116395(n,k) . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 07 2006

a(n)=[1/(s-n)]*sum_{k=0..n} (-1)^k (k+s-n)*binomial(s-n,k)*binomial(s+n-k,s) with s a nonnegative free integer [H. W. Gould].

a(k) = Sum_{i=1..k} |A008276(i,k)| * (k-1)^(k-i) / k! - Andre F. Labossiere (boronali(AT)laposte.net), May 29 2007

a(n)=Sum_{k, 0<=k<=n}A129818(n,k)*A007852(k+1). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jun 20 2007

a(n)=Sum_{k, 0<=k<=n}A109466(n,k)*A127632(k). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jun 20 2007

Row sums of triangle A124926 - Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 22 2007

For G.f. A(x), g(x)= x*A(x) is the compositional inverse of f(x) = x*(1-x) and this relates the Catalan numbers to the row sums of A125181. - Tom Copeland (tcjpn(AT)msn.com), Jan 13 2008

lim(1+Sum(a(k)/A004171(k): 0<=k<=n): n->infinity) = 4/pi. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Aug 26 2008]

a(n)=Sum_{k, 0<=k<=n}A120730(n,k)^2 and a(k+1)=Sum_{n, n>=k}A120730(n,k). [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 18 2008]

Comment from Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 27 2008: Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n-1} + a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-2}*a_1 for n >= t. For example the present sequence is Phi([1]) (also Phi([1,1])).

Formula from Thomas Wieder (wieder.thomas(AT)t-online.de), Feb 25 2009:

a(n) = sum_{l_1=0}^{n+1} sum_{l_2=0}^{n}...sum_{l_i=0}^{n-i}...sum_{l_n=0}^{1}

delta(l_1,l_2,...,l_i,...,l_n)

where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i < l_(i+1) and l_(i+1) <> 0

for i=1..n-1 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise.

a(n) = C(2*n,n)-C(2*n,n-1) . [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 17 2009]

A000108 := n->binomial(2*n, n)/(n+1); G000108 := (1 - sqrt(1 - 4*x)) / (2*x);

spec := [ A, {A=Prod(Z, Sequence(A))}, unlabeled ]: [ seq(combstruct[count](spec, size=n), n=0..42) ];

with(combstruct):bin := {B=Union(Z, Prod(B, B))}: seq (count([B, bin, unlabeled], size=n), n=1..25); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 05 2007

Z[0]:=0: for k to 42 do Z[k]:=simplify(1/(1-z*Z[k-1])) od: g:=sum((Z[j]-Z[j-1]), j=1..42): gser:=series(g, z=0, 42): seq(coeff(gser, z, n), n=0..41); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 21 2008

A000108[ n_ ] := (2 n)!/n!/(n+1)!

A000108[n_]:=Hypergeometric2F1[1-n, -n, 2, 1] - Richard L. Ollerton (r.ollerton(AT)uws.edu.au), Sep 13 2006

(MAGMA) C:= func< n | Binomial(2*n, n)/(n+1) >; [ C(n) : n in [0..60]];

(PARI) a(n)=if(n<0, 0, (2*n)!/n!/(n+1)!)

(PARI) a(n)=local(A, m); if(n<0, 0, m=1; A=1+x+O(x^2); while(m<=n, m*=2; A=sqrt(subst(A, x, 4*x^2)); A+=(A-1)/(2*x*A)); polcoeff(A, n))

(PARI) a(n)=if(n<1, n==0, polcoeff(serreverse(x/(1+x)^2+x*O(x^n)), n)) (from Michael Somos)

(Mupad) combinat::dyckWords::count(n) $ n = 0..38 - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 14 2007

sage: [catalan_number(i) for i in range(27)] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 26 2008

(Other) sage: [binomial(2*i, i)-binomial(2*i, i-1) for i in xrange(0, 25)]# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 17 2009]

Cf. A000984, A002420, A048990, A024492, A000142, A022553. A row of A060854.

Cf. A039599, A094216, A094638, A014137, A094639, A099731, A008549.

See A001003, A001190, A001699, A000081 for other ways to count parentheses.

Enumerates objects encoded by A014486.

Cf. A008276, A094638 (|A008276|), A094216, A094639, A000984.

A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.

Cf. A000108 A000245 A002057 A000344 A003517 A000588 A003518 A003519 A001392.

Cf. A124926.

Cf. A098597, A086117, A137697.

A diagonal of the square array described in A051168.

A154559 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 11 2009]

A000957, A068875 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 01 2009]

A032443 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 15 2009]

Sequence in context: A054394 A036769 A033191 this_sequence A168491 A115140 A120588

Adjacent sequences: A000105 A000106 A000107 this_sequence A000109 A000110 A000111

core,nonn,easy,eigen,nice

N. J. A. Sloane (njas(AT)research.att.com).

0,3

Number of edges in complete graph of order n, K_n.

Number of legal ways to insert a pair of parentheses in a string of n letters. E.g. there are 6 ways for three letters: (a)bc, (ab)c, (abc), a(b)c, a(bc), ab(c). [Proof: there are C(n+2,2) ways to choose where the parentheses might go, but n+1 of them are illegal because the parentheses are adjacent.] Cf. A002415.

For n >= 1 a(n)=n(n+1)/2 is also the genus of a nonsingular curve of degree n+2 like the Fermat curve x^(n+2) + y^(n+2) = 1 - Ahmed Fares (ahmedfares(AT)my_deja.com), Feb 21 2001

From Harnack's theorem (1876), the number of branches of a non-singuliar curve of order n is bounded by a(n) - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 29 2002

Number of tiles in the set of double-n dominoes. - Scott A. Brown (scottbrown(AT)neo.rr.com), Sep 24 2002

Number of ways a chain of n non-identical links can be be broken up. This is based on a similar problem in the field of proteomics: the number of ways a peptide of n amino acid residues can be be broken up in a mass spectrometer. In general each amino acid has a different mass, so AB and BC would have different masses. - James Raymond (raymond(AT)unlv.edu), Apr 08 2003

Maximum number of intersections of n+1 lines which may only have 2 lines per intersection point. Maximal number of closed regions when n+1 lines are maximally 2-intersected in given by T(n-1). Using n+1 lines with k>1 parallel lines, the maximum number of 2-intersections is given by T(n)-T(k-1). - Jon Perry (perry(AT)globalnet.co.uk), Jun 11 2003

Number of distinct straight lines that can pass through n points in 3-dimensional space. - Cino Hilliard (hillcino368(AT)gmail.com), Aug 12 2003

Triangular numbers - odd numbers = triangular numbers: 0,1,3,6,10,15,21... - 0,1,3,5,7,9,11... = 0,0,0,1,3,6,10... - Xavier Acloque Oct 31 2003

Centered polygonal numbers are the result of [number of sides * A000217 + 1]. E.g. centered pentagonal numbers (1,6,16,31...)= 5 * (0,1,3,6...) + 1. Centered heptagonal numbers (1,8,22,43...)= 7 * (0,1,3,6...) + 1. - Xavier Acloque Oct 31 2003

Maximum number of lines formed by the intersection of n+1 planes. - Ronald R. King (king_ron(AT)asdk12.org), Mar 29 2004

Number of permutations of [n] which avoid the pattern 132 and have exactly 1 descent. - Mike Zabrocki (zabrocki(AT)mathstat.yorku.ca), Aug 26 2004

a(n) == 1 mod (n+2) if n is odd and == n/2+2 mod (n+2) if n is even. - Jon Perry (perry(AT)globalnet.co.uk), Dec 16 2004

Number of ways two different numbers can be selected from the set {0,1,2,...,n} without repetition, or, number of ways two different numbers can be selected from the set {1,2,...,n} with repetition.

1, 6, 120 are the only numbers which are both triangular and factorial. - Christopher M. Tomaszewski (cmt1288(AT)comcast.net), Mar 30 2005

a(n) = A108299(n+3,4) = -A108299(n+4,5). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Jun 01 2005

In 24-bit RGB color cube, the number of color-lattice-points in r+g+b = n planes at n < 256 equals the triangular numbers. For n = 256, ..., 765 the number of legitimate color partitions is less than A000217(n) because {r,g,b} components cannot exceed 255. For n=256,..,511, the number of non-color partitions are computable with A045943(n-255), while for n = 512-765, the number of color points in r+g+b planes equals A000217(765-n). - Labos E. (labos(AT)ana.sote.hu), Jun 20 2005

A110560/A110561 = numerator/denominator of the coefficients of the exponential generating function. - Jonathan Vos Post (jvospost3(AT)gmail.com), Jul 27 2005

Binomial transform is {0, 1, 5, 18, 56, 160, 432, ... }, A001793 with one leading zero . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Aug 02 2005

a(n) = A111808(n,2) for n>1. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Aug 17 2005

Each pair of neighboring terms adds to a perfect square. - Zak Seidov (zakseidov(AT)yahoo.com), Mar 21 2006

a(n)*a(n+1) = A006011(n) = n^2*(n^2-1)/4 = 3*A002415(n) = 1/2*a(n^2+2*n). a(n-1)*a(n) = 1/2*a(n^2-1). - Alexander Adamchuk (alex(AT)kolmogorov.com), Apr 13 2006

Number of transpositions in the symmetric group of n+1 letters i.e. the number of permutations that leave all but two elements fixed. - Geoffrey Critzer (geoffreycritzer(AT)yahoo.com), Jun 23 2006

Beginning from a(3), a(n) is the number of way to get a semiprime from n primes. Example: From 2 and 3 the number of semiprimes is 3: 2*2, 3*3, 2*3; from 2 and 3 and 5 the number of semiprimes is 6: 2*2, 3*3, 5*5, 2*3, 2*5, 3*5. - Giovanni Teofilatto (g.teofilatto(AT)tiscalinet.it), Sep 17 2006

With rho(n):=exp(i*2*Pi/n) (an n-th root of 1) one has, for n>=1, rho(n)^a(n)=(-1)^(n+1). Just use the triviality a(2*k+1)=0(mod (2*k+1)) and a(2*k)=k(mod 2*k).

Comments from Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 18 2006: (Start)

a:=n->sum(j + 1,j=-1..n): seq(a(n),n=-1..50);

a:=n->sum(j + 2,j=0..n): seq(a(n),n=-1..51); => A000096 = this sequence + 1*A001477

a:=n->sum(j + 2,j=1..n): seq(a(n),n=0..48); => A055998 = this sequence + 2*A001477

a:=n->sum(j + 2,j=2..n):seq(a(n),n=1..50); => A055999 = this sequence + 3*A001477

a:=n->sum(j + 2,j=3..n):seq(a(n),n=2..52); => A056000 = this sequence + 4*A001477

a:=n->sum(j + 2,j=4..n):seq(a(n),n=3..53); => A056115 = this sequence + 5*A001477

a:=n->sum(j + 2,j=5..n):seq(a(n),n=4..54); => A056119 = this sequence + 6*A001477

a:=n->sum(j + 2,j=6..n):seq(a(n),n=5..50); => A056121 = this sequence + 7*A001477

a:=n->sum(j + 2,j=7..n):seq(a(n),n=6..56); => A056126 = this sequence + 8*A001477

a:=n->sum(j + 2,j=8..n):seq(a(n),n=7..56); => A051942 = this sequence + 9*A001477

a:=n->sum(j + 2,j=9..n):seq(a(n),n=8..59); => A101859 = this sequence + 10*A001477 (End)

a(n) = A126890(n,0). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Dec 30 2006

a(n) is the number of terms in the expansion of (a_1+a_2+a_3)^n - Sergio Falcon (sfalcon(AT)dma.ulpgc.es), Feb 12 2007

(sqrt(8 a(n) + 1) - 1)/2 = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 26 2007

The number of distinct handshakes in a room with n people (n>=2). - Mohammad K. Azarian (azarian(AT)evansville.edu), Apr 12 2007

Equal to the rank (minimal cardinality of a generating set) of the semigroup PT_n\S_n, where PT_n and S_n denote the partial transformation semigroup and symmetric group on [n]. - James East (james.east(AT)latrobe.edu.au), May 03 2007

Gives the total number of triangles found when cevians are drawn from a single vertex on a triangle to the side opposite that vertex, where n=the number of cevians drawn+1. For instance, with 1 cevian drawn, n=1+1=2 and a(n)=2(2+1)/2=3 so there is a total of 3 triangles in the figure. If 2 cevians are drawn from one point to the opposite side, then n=1+2=3 and a(n)=3(3+1)/2=6 so there is a total of 6 triangles in the figure. - Noah Priluck (npriluck(AT)gmail.com), Apr 30 2007

a(n), n>=1, is the number of ways in which n-1 can be written as a sum of three positive integers if representations differing in the order of the terms are considered to be different. In other words a(n),n>=1, is the number of positive integral solutions of the equation x + y + z = n-1. - Amarnath Murthy (amarnath_murthy(AT)yahoo.com), Apr 22 2001

a(n+1), n>=0, is the number of levels with energy n+3/2 (in units of h*f0, with Planck's constant h and the oscillator frequency f0) of the three dimensional isotropic harmonic quantum oscillator. See the comment by A. Murthy above: n=n1+n2+n3 with positive integers and ordered. Proof from the o.g.f. See the A. Messiah reference. W. Lang, Jun 29 2007.

Numbers m>=0 such that round(sqrt(2m+1))-round(sqrt(2m))=1. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 06 2007

Numbers m>=0 such that ceiling(2*sqrt(2m+1))-1=1+floor(2*sqrt(2m)). - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 06 2007

Numbers m>=0 such that fract(sqrt(2m+1))>1/2 and fract(sqrt(2m))<1/2, where fract(x) is the fractional part of x (i.e. x-floor(x), x>=0). - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 06 2007

Each term, except for the initial 0, is a sum of digits of terms in A007908. - Alexander R. Povolotsky (pevnev(AT)juno.com), Nov 01 2007

Sequence allows us to find X values of the equation: 8*X^3 + X^2 = Y^2. To find Y values: b(n)=n(n+1)(2n+1)/2. - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Nov 06 2007

If Y and Z are 3-blocks of an n-set X then, for n>=6, a(n-1) is the number of (n-2)-subsets of X intersecting both Y and Z. - Milan R. Janjic (agnus(AT)blic.net), Nov 09 2007

Number of n-permutations of 2 objects u,v, with repetition allowed, containing exactly two u's. Example: n=4, a(4) = 6 because we have uuvv, uvuv, vuuv, uvvu, vuvu and vvuu. - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jul 15 2008

Equals row sums of triangle A143320, n>0. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 07 2008]

a(n) is also a perfect number A000396 when n is a Mersenne prime A000668. [From Omar E. Pol (info(AT)polprimos.com), Sep 05 2008]

a(n) = A022264(n) - A049450(n). [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Oct 09 2008]

Equals row sums of triangle A152204 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 29 2008]

The number of matches played in a round robin tournament: n*(n-1)/2 gives the number of matches needed for n players. Everyone plays against everyone else exactly once. [From Georg Wrede (georg(AT)iki.fi), Dec 18 2008]

-a(n+1) = E(2)*C(n+2,2) (n>=0) where E(n) are the Euler number in the enumeration A122045 and C(n,k) are the binomial coefficients A007318. Viewed this way a(n) is the special case k=2 in the sequence of diagonals in the triangle A153641. [From Peter Luschny (peter(AT)luschny.de), Jan 06 2009]

4a(x)+4a(y)+1=(x+y+1)^2+(x-y)^2 [From Vladimir Shevelev (shevelev(AT)bgu.ac.il), Jan 21 2009]

Equivalent to the first differences of successive tetrahedral numbers. See A000292. [From Jeremy Cahill (jcahill(AT)inbox.com), Apr 15 2009]

Contribution from Peter Luschny (peter(AT)luschny.de), Jul 12 2009: (Start)

The general formula for alternating sums of powers is in terms of the Swiss-Knife polynomials P(n,x) A153641 2^(-n-1)(P(n,1)-(-1)^k P(n,2k+1)). Thus

a(k) = |2^(-3)(P(2,1)-(-1)^k P(2,2k+1))|. (End)

a(n) is the smallest number > a(n-1) such that gcd(n,a(n)) = gcd(n,a(n-1)). If n is odd this gcd is n; if n is even it is n/2. [From Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Aug 06 2009]

Number of units of a(n) belongs to a periodic sequence: 0, 1, 3, 6, 0, 5, 1, 8, 6, 5, 5, 6, 8, 1, 5, 0, 6, 3, 1, 0. [From Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 04 2009]

a(A006894(n)) = a(A072638(n-1)+1) = A072638(n) = A006894(n+1)-1 for n >= 1. For n=4, a(11) = 66. [From Jaroslav Krizek (jaroslav.krizek(AT)atlas.cz), Sep 12 2009]

Partial sums of nonnegative numbers. [From Juri-Stepan Gerasimov (2stepan(AT)rambler.ru), Jan 25 2010]

The numbers along the right edge of Floyd's triangle are 1, 3, 6, 10, 15, .... [From Paul Muljadi (paulmuljadi(AT)yahoo.com), Jan 25 2010]

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.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 189.

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 109ff.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 155.

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. 1.

Tomislav Doslic, Maximum Product Over Partitions Into Distinct Parts, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.8.

Clark Kimberling, Complementary Equations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.4.

Labos E.: On the number of RGB-colors we can distinguish. Partition Spectra. Lecture at 7th Hungarian Conference on Biometry and Biomathematics. Budapest. Jul 06,2005.

A. Messiah, Quantum Mechanics, Vol.1, North Holland, Amsterdam, 1965, p. 457.

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

T. Trotter, Some Identities for the Triangular Numbers, Journal of Recreational Mathematics, Spring 1973, 6(2).

D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, pp. 91-3 Penguin Books 1987.

Michael Boardman, "The Egg-Drop Numbers", Mathematics Magazine, 77 (2004), 368-372. [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Sep 30 2009]

N. J. A. Sloane, Table of n, a(n) for n = 0..10000

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. Beldon and T. Gardiner, Triangular numbers and perfect squares, The Mathematical Gazette 86 (2002), 423-431 [From Pasha Zusmanovich (justpasha(AT)gmail.com), Jan 28 2010]

H. Bottomley, Illustration of initial terms of A000217, A002378

Scott A. Brown, Brown's Math Page, etc.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

S. S. Gupta, Fascinating Triangular Numbers

C. Hamberg, Triangular Numbers Are Everywhere

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 253

Milan Janjic, Two Enumerative Functions

R. Jovanovic, Triangular numbers

R. Jovanovic, First 2500 Triangular numbers

H. K. Kim, "On Regular polytope numbers".

Clark Kimberling and John E. Brown, Partial Complements and Transposable Dispersions, J. Integer Seqs., Vol. 7, 2004.

J. Koller, Triangular Numbers

A. J. F. Leatherland, Triangle Numbers on Ulam Spiral

Ivars Peterson, Triangular Numbers and Magic Squares.

Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7

S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.

S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.

O. E. Pol, Determinacion geometrica de los numeros primos y perfectos.

F. Richman, Triangle numbers

sci.math, Jun 98 Square numbers that are triangular [From Pasha Zusmanovich (justpasha(AT)gmail.com), Jan 28 2010]

James A. Sellers, Partitions Excluding Specific Polygonal Numbers As Parts, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.4.

N. J. A. Sloane, Illustration of initial terms of A000217, A000290, A000326

Thesaurus.maths.org, Triangular Numbers

T. Trotter, Some Identities for the Triangular Numbers, J. Rec. Math. vol. 6, no. 2 Spring 1973.

G. Villemin's Almanach of Numbers, Nombres Triangulaires

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (1).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (3).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (4).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (5).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (6).

Eric Weisstein's World of Mathematics, Line Line Picking

Eric Weisstein's World of Mathematics, Trinomial Coefficient

Eric Weisstein's World of Mathematics, Wiener Index

Wikipedia, Floyd's triangle [From Paul Muljadi (paulmuljadi(AT)yahoo.com), Jan 25 2010]

Index entries for "core" sequences

Index entries for related partition-counting sequences

Index entries for two-way infinite sequences

Index entries for sequences related to linear recurrences with constant coefficients

G.f.: x/(1-x)^3. E.g.f.: exp(x)(x+x^2/2). a(n)=a(-1-n).

a(n) = a(n-1)+n. - Zak Seidov (zakseidov(AT)yahoo.com), Mar 06 2005

a(n) + a(n-1)*a(n+1) = a(n)^2. - Terry Trotter (ttrotter(AT)telesal.net), Apr 08, 2002

a(n) = (-1)^n*sum(k=1, n, (-1)^k*k^2) - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 29 2002

a(n) = ((n+2)/n)*a(n-1)

Sum(n=1..infinity, 1/a(n)) = 2. - Jon Perry (perry(AT)globalnet.co.uk), Jul 13 2003

For n>0, a(n)=A001109(n)-(sum_{k=0...n-1}((2k+1)*A001652(n-1-k))) e.g. 10=204-(1*119+3*20+5*3+7*0) - Charlie Marion (charliem(AT)bestweb.net), Jul 18 2003

G.f.: x/(1-x)^3. E.g.f.: exp(x)(x+x^2/2). a(n)=a(-1-n).

With interpolated zeros, this is n(n+2)/8*(1+(-1)^n)/2=sum{k=0..n, sum{j=0..k, floor(k^2/4)}}. - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 19 2003

a(n+1) is the determinant of the n X n symmetric Pascal matrix M_(i, j)=C(i+j+1, i) - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 19 2003

a(n)=[(n^3-(n-1)^3)-(n^1-(n-1)^1)]/(2^3-2^1)= (n^3-(n-1)^3-1)/6 - Xavier Acloque Oct 24 2003

a(n) = a(n-1) + (1 + sqrt[1 + 8*a(n-1)])/2. E.g. a(4) = a(3) + (1 + sqrt[1 + 8*a(3)])/2 = 6 + (1 + sqrt[49])/2 = 6+8/2 = 10. This recursive relation is inverted when taking the negative branch of the square root, i.e. a(n) is transformed into a(n-1) rather than a(n+1). - Carl R. White (cyrek(AT)cyreksoft.yorks.com), Nov 04 2003

a(n)+a(n+1) = (n+1)^2.

a(n) = a(n-2)+2n-1. - Paul Barry (pbarry(AT)wit.ie), Jul 17 2004

a(n) = Sqrt[Sum[Sum[(i*j), {i, 1, n}], {j, 1, n}]] - Alexander Adamchuk (alex(AT)kolmogorov.com), Oct 24 2004

a(n) = Sqrt[Sqrt[Sum[Sum[(i*j)^3, {i, 1, n}], {j, 1, n}]]]. a(n) = Sum[Sum[Sum[(i*j*k)^3, {i, 1, n}], {j, 1, n}], {k, 1, n}]^(1/6) - Alexander Adamchuk (alex(AT)kolmogorov.com), Oct 26 2004

a(0) = 0, a(1) = 1, a(n) = 2*a(n-1)-a(n-2)+1 - Miklos Kristof (kristmikl(AT)freemail.hu), Mar 09 2005

a(n) = Sum_{k = 1...n} phi(k)*floor(n/k) = Sum{k = 1...n} A000010(k)*A010766(n, k) (R. Dedekind). - Vladeta Jovovic = (vladeta(AT)eunet.rs), Feb 05 2004

a(n) = floor((2n+1)^2/8) - Paul Barry (pbarry(AT)wit.ie), May 29 2006

For positive n, we have a(8*a(n))/a(n) = 4*(2n+1)^2 = (4n+2)^2, i.e., a(A033996(n))/a(n) = 4*A016754(n) = (A016825(n))^2 = A016826(n). - Lekraj Beedassy (blekraj(AT)yahoo.com), Jul 29 2006

[a(n)]^2+[a(n+1)]^2 = a((n+1)^2) [R B Nelsen, Math Mag 70 (2) (1997) p 130]. - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 22 2006

a(n) = A023896(n) + A067392(n). - Lekraj Beedassy (blekraj(AT)yahoo.com), Mar 02 2007

a(n)=sum(sum(j-k, j=1..n),k=0..n), n>=0. - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 11 2007

Sum_{k, 0<=k<=n}a(k)*A039599(n,k)=A002457(n-1), for n>=1 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jun 10 2007

a(n) = (n+1)^2 - a(n+1) - Eugeny Yakimovitch (Eugeny.Yakimovitch(AT)gmail.com), Jan 21 2008

A general formula for polygonal numbers is: P(k,n) = (k-2)(n-1)n/2 + n, where P(k,n) is the n-th k-gonal number. - Omar E. Pol (info(AT)polprimos.com), Apr 28 2008

If we define f(n,i,a)=sum(binomial(n,k)*stirling1(n-k,i)*product(-a-j,j=0..k-1),k=0..n-i), then a(n)=-f(n,n-1,1), for n>=1. [From Milan R. Janjic (agnus(AT)blic.net), Dec 20 2008]

(2n+1)^2=8*a(n)+1 [From S. Vinatier (stephane.vinatier(AT)unilim.fr), Apr 03 2009]

a(n) = A000124(n-1) + (n-1) for n >= 2. a(n) = A000124(n) - 1. A000124(n) = central polygonal numbers. [From Jaroslav Krizek (jaroslav.krizek(AT)atlas.cz), Jun 16 2009]

An exponential generating function for the inverse of this sequence is given by sum((pochhammer(1, m)*pochhammer(1, m))*x^m/(pochhammer(3, m)*factorial(m)), m = 0 .. infinity)=((2-2*x)*ln(1-x)+2*x)/x^2; The n-th derivative of which has a closed form which must be evaluated by taking the limit x=0. A000217[n+1]=limit(Diff(((2-2*x)*ln(1-x)+2*x)/x^2, x$n),x=0)^-1=limit((2*GAMMA(n)*(-1/x)^n*(n*(x/(-1+x))^n*(-x+1+n)*LerchPhi(x/(-1+x), 1, n)+(-1+x)*(n+1)*(x/(-1+x))^n+n*(ln(1-x)+ln(-1/(-1+x)))*(-x+1+n))/x^2),x=0)^-1 [From Stephen Crowley (crow(AT)crowlogic.net), Jun 28 2009]

a(n) = A034856(n+1) - A005408(n) = A005843(n) + A000124(n) - A005408(n) = A000124(n) - 1. [From Jaroslav Krizek (jaroslav.krizek(AT)atlas.cz), Sep 05 2009]

When n=3, a(3) = 4*3/2 = 6.

Example(a(4)=10): ABCD where A, B, C and D are different links in a chain or different amino acids in a peptide possible fragments: A, B, C, D, AB, ABC, ABCD, BC, BCD, CD = 10

A000217 := proc(n) n*(n+1)/2; end; [ seq(n*(n+1)/2, n=0..100)];

istriangular:=proc(n) local t1; t1:=floor(sqrt(2*n)); if n = t1*(t1+1)/2 then RETURN(true) else RETURN(false); fi; end; (N. J. A. Sloane, May 25 2008)

a[0]:=0: a[1]:=1: for n from 2 to 50 do a[n]:=2*a[n-1]-a[n-2]+1 od: seq(a[n], n=0..50); (Kristof)

[seq (stirling2(n+1, n), n=1..53)]; - Zerinvary Lajos (zerinvarylajos(AT)yahoo), Dec 06 2006

ZL := [S, {S=Prod(B, B, B), B=Set(Z, 1 <= card)}, unlabeled]: seq(combstruct[count](ZL, size=n), n=2..55); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 24 2007

a:=n->sum(n+2*j, j=0..n)/4: seq(a(n), n=0..53); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 29 2007

a:=n->sum(sum(j-k, j=1..n), k=0..n): seq(a(n), n=0..53); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 11 2007

seq(sum(mul(gcd(j, k), j=0..n), k=0..n), n=0..53); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 01 2007

A000217:=-1/(z-1)**3; [S. Plouffe in his 1992 dissertation.]

seq(sum(binomial(n, k+1), k=1..1), n=1..54); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 14 2007

with(combinat):a:=n->sum(fibonacci(2, i), i=0..n): seq(a(n), n=0..53); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 20 2008

a:=n->sum(1+sum(1, k=1..n), k=1..n):seq(a(n)/2, n=0...55); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 20 2008

with(finance):seq(add(futurevalue(k, 3, 2), k=0..n)/16, n=0..55); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 20 2008

restart: G(x):=x^2*exp(x): f[0]:=G(x): for n from 1 to 54 do f[n]:=diff(f[n-1], x) od: x:=0: seq(f[n]/2, n=1..54); # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 05 2009]

Table[Sqrt[Sum[Sum[(i*j), {i, 1, n}], {j, 1, n}]], {n, 0, 10}]

Table[(m^2 - m)/2, {m, 54}] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 24 2007

Table[Sqrt[StirlingS2[i+1, i]*(-StirlingS1[i+1, i])], {i, 0, 53}] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 24 2007

...and/or... i=0; s=0; lst={}; Do[s+=n+i; If[s>=0, AppendTo[lst, s]], {n, 0, 6!, 1}]; lst [From Vladimir Orlovsky (4vladimir(AT)gmail.com), Oct 29 2008]

tr[a_]:=Module[{x}, s=0; For[i=1, i<a, s+=i; i++ ]; x=s]; [From Vladimir Orlovsky (4vladimir(AT)gmail.com), Apr 03 2009]

Array[ #*(# - 1)/2 &, 54, 1] [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jul 10 2009]

(PARI) a(n)=n*(n+1)/2

sage: [lucas_number1(3, n, n)/2 for n in xrange(1, 55)] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jul 15 2008

(Other) sage: [stirling_number1(n, n-1) for n in xrange(1, 55)] # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 16 2009]

Cf. A007318, A002024, A000096, A000124, A002378, A000292, A000330.

Cf. A000096, A055998, A055999, A056000, A056115, A056119, A056121, A056126, A051942, A101859, A001477.

Cf. A005563, A046092, A001082, A002378, A036666, A062717, A028347, A087475.

Cf. A006011, A002415, A010054.

a(2k-1)=A000384(k), a(2k)=A014105(k), k>0.

A diagonal of A008291. a(n) = A110555(n+2, 2).

a(n) = A110449(n, 0).

A143320 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 07 2008]

Cf. A000396, A000668. [From Omar E. Pol (info(AT)polprimos.com), Sep 05 2008]

a(3*n)=A081266, a(4*n)=A033585, a(5*n)=A144312, a(6*n)=A144314. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Sep 17 2008]

A152204 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 29 2008]

Sequence in context: A105339 A089594 A161680 this_sequence A105340 A109811 A025747

Adjacent sequences: A000214 A000215 A000216 this_sequence A000218 A000219 A000220

nonn,core,easy,nice,new

N. J. A. Sloane (njas(AT)research.att.com).

1,2

If the canonical factorization of n into prime powers is Product p^e(p) then d(n) = Product (e(p) + 1). More generally, for k>0, sigma_k(n) = Product_p ((p^((e(p)+1)*k))-1)/(p^k-1).

Number of ways to write n as n = x*y, 1 <= x <= n, 1 <= y <= n. For number of unordered solutions to x*y=n, see A038548.

Note that d(n) is not the number of Pythagorean triangles with radius of the inscribed circle equal to n (that is A078644). For number of primitive Pythagorean triangles having inradius n, see A068068(n).

Number of factors in the factorization of the polynomial x^n-1 over the integers. - T. D. Noe (noe(AT)sspectra.com), Apr 16 2003

If d(n) is odd, n is a perfect square. If d(n) = 2, n is prime. - Donald Sampson (Marsquo(AT)hotmail.com), Dec 10 2003

Number of even divisors of n = d(2*n) * (1 - n mod 2). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Dec 28 2003

Also equal to the number of partitions p of n such that all the parts have the same cardinality, i.e. max(p)=min(p). - Giovanni Resta (g.resta(AT)iit.cnr.it), Feb 06 2006

Equals A127093 as an infinite lower triangular matrix * the harmonic series, [1/1, 1/2, 1/3,...]. - Gary W. Adamson (qntmpkt(AT)yahoo.com), May 10 2007

Sum_{n>0} d(n)/(n^n) = Sum_{n>0, m>0} 1/(n*m). - Gerald McGarvey (gerald.mcgarvey(AT)comcast.net), Dec 15 2007

For odd n, this is the number of partitions of n into consecutive integers. Proof: For n = 1, clearly true. For n = 2k + 1, k >= 1, map each (necessarily odd) divisor to such a partition as follows: For 1 and n, map k + (k+1) and n, respectively. For any remaining divisor d <= sqrt(n), map (n/d - (d-1)/2) + ... + (n/d - 1) + (n/d) + (n/d + 1) + ... + (n/d + (d-1)/2) {i.e., n/d plus (d-1)/2 pairs each summing to 2n/d)}. For any remaining divisor d > sqrt(n), map ((d-1)/2 - (n/d - 1)) + ... + ((d-1)/2 - 1) + (d-1)/2 + (d+1)/2 + ((d+1)/2 + 1) + ... + ((d+1)/2 + (n/d - 1)) {i.e., n/d pairs each summing to d}. As all such partitions must be of one of the above forms, the 1-to-1 correspondence and proof is complete. - Rick L. Shepherd (rshepherd2(AT)hotmail.com), Apr 20 2008

Number of subgroups of the cyclic group of order n. - Benoit Jubin (benoit_jubin(AT)yahoo.fr), Apr 29 2008

Equals row sums of triangle A143319 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 07 2008]

Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 26 2009: (Start)

Equals row sums of triangle A159934, equivalent to generating a(n) by

convolving A000005 prefaced with a 1; (1, 1, 2, 2, 3, 2,...) with the

INVERTi transform of A000005, (A159933): (1, 1,-1, 0, -1, 2,...):

Example: a(6) = 4 = (1, 1, 2, 2, 3, 2) dot (2, -1, 0, -1, 1, 1) = (2, -1, 0, -2, 3, 2) = 4. (End)

a(n) = A048691(n) - A055205(n). [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Dec 08 2009]

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.

G. E. Andrews, Some debts I owe, Seminaire Lotharingien Combinatoire, Paper B42a, Issue 42, 2000; see (7.1).

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 38.

R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. [From N. J. A. Sloane, Mar 12 2009]

G. Chrystal, Algebra: An elementary text-book for the higher classes of secondary schools and for colleges, 6th ed, Chelsea Publishing Co., New York 1959 Part II, p. 345, Exercise XXI(16). MR0121327 (22 #12066)

P. Erdos and L. Mirsky, The distribution of values of the divisor function d(n), Proc. London Math. Soc., 2 (1952), 257-271.

C. R. Fletcher, Rings of small order, Math. Gaz. vol. 64, p. 13, 1980.

K. Knopp, Theory and Application of Infinite Series, Blackie, London, 1951, p. 451.

P. A. MacMahon, Divisors of numbers and their continuations in the theory of partitions, Proc. London Math. Soc., 19 (1919), 75-113.

D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Chap. II. (For inequalities, etc.)

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

B. Spearman and K. S. Williams, Handbook of Estimates in the Theory of Numbers, Carleton Math. Lecture Note Series No. 14, 1975; see p. 2.1.

E. C. Titchmarsh, The Theory of Functions, Oxford, 1938, p. 160.

E. C. Titchmarsh, On a series of Lambert type, J. London Math. Soc., 13 (1938), 248-253.

Daniel Forgues, Table of n, a(n) for n=1..100000

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].

Author?, Title?

G. E. Andrews, Some debts I owe

H. Bottomley, Illustration of initial terms

C. K. Caldwell, The Prime Glossary, Number of divisors

Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors ..., J. Integer Seqs., Vol. 6, 2003.

J. J. Holt & J. W. Jones, Discovering Number Theory, Section 1.4, Counting Divisors

M. Maia and M. Mendez, On the arithmetic product of combinatorial species

R. G. Martinez, Jr., The Factor Zone, Number of Factors for 1 through 600

Math Forum, Divisor Counting

K. Matthews, Factorizing n and calculating phi(n), omega(n), d(n), sigma(n) and mu(n)

S. Ramanujan, On The Number Of Divisors Of A Number

H. B. Reiter, Counting Divisors

W. Sierpinski, Number Of Divisors And Their Sum

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (1).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2).

Eric Weisstein's World of Mathematics, Dirichlet Series Generating Function

Eric Weisstein's World of Mathematics, Binomial Number

Wikipedia, Table of divisors

Wolfram Research, Divisors of first 50 numbers

Index entries for "core" sequences

O. E. Pol, Illustration of initial terms (1) [From Omar E. Pol (info(AT)polprimos.com), Oct 22 2009]

O. E. Pol, Illustration of initial terms (2) [From Omar E. Pol (info(AT)polprimos.com), Oct 22 2009]

O. E. Pol, Illustration of initial terms (3) [From Omar E. Pol (info(AT)polprimos.com), Oct 22 2009]

O. E. Pol, Illustration of initial terms (4) [From Omar E. Pol (info(AT)polprimos.com), Oct 25 2009]

O. E. Pol, Illustration of initial terms (5) [From Omar E. Pol (info(AT)polprimos.com), Oct 25 2009]

If n is written as 2^z*3^y*5^x*7^w*11^v*... then d(n)=(z+1)*(y+1)*(x+1)*(w+1)*(v+1)*...

Multiplicative with a(p^e) = e+1. - David W. Wilson (davidwwilson(AT)comcast.net), Aug 01, 2001.

G.f.: Sum_{n >= 1} d(n) x^n = Sum_{k>0} x^k/(1-x^k). This is usually called THE Lambert series (see Knopp, Titchmarsh).

d(n) <= 2 sqrt(n) [see Mitrinovich, p. 39, also A046522].

a(n) is odd iff n is a square. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Dec 29, 2001

a(n) = sum(k=1, n, f(k, n)) where f(k, n) = 1 if k divides n, 0 otherwise. Equivalently, f(k, n) = (1/k)*sum(l=1, k, z(k, l)^n) with z(k, l) the k-th roots of unity. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Dec 25 2002

G.f.: Sum_{n>0} ((-1)^(n+1) x^(n(n+1)/2) / ((1-x^n)*Product(1-x^i, i=1..n))).

a(n)=n-sum(k=1, n, ceil(n/k)-floor(n/k)) - Benoit Cloitre (benoit7848c(AT)orange.fr), May 11 2003

a(n) = A032741(n)+1 = A062011(n)/2 = A054519(n)-A054519(n-1) = A006218(n)-A006218(n-1) = sum(k=0, n-1, A051950(k)). - R. Stephan, Mar 26 2004

G.f.: Sum_{k>0} x^(k^2)*(1+x^k)/(1-x^k). Dirichlet g.f.: zeta(s)^2. - Michael Somos, Apr 05 2003

Sequence = M*V where M = A129372 as an infinite lower triangular matrix and V = ruler sequence A001511 as a vector: [1, 2, 1, 3, 1, 2, 1, 4,...]. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 15 2007

A000005 = M*V, where M = A115361 is an infinite lower triangular matrix and V = A001227, the number of odd divors of n, is a vector: [1, 1, 2, 1, 2, 2, 2,...]. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 15 2007

Row sums of triangle A051731 - Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 02 2007

a(n)=sum(k=1, n, floor(n/k)-floor((n-1)/k) [From Barbarel Tres Mil (barbarel3000(AT)yahoo.es), Aug 27 2009]

a(s)=2^omega(s), if s>1 is a squarefree number (A005117) and omega(s) is: A001221 [From Barbarel Tres Mil (barbarel3000(AT)yahoo.es), Sep 08 2009]

with(numtheory): A000005 := tau; [ seq(tau(n), n=1..100) ];

a[n_] := DivisorSigma[0, n]

a[n_] := Length[Divisors[n]]

Table[Sum[Floor[n/k] - Floor[(n - 1)/k], {k, 1, n}], {n, 1, 100}] [From Barbarel Tres Mil (barbarel3000(AT)yahoo.es), Aug 27 2009]

(PARI) a(n)=if(n<1, 0, numdiv(n))

(PARI) a(n)=if(n<1, 0, direuler(p=2, n, 1/(1-X)^2)[n])

(MAGMA) [ NumberOfDivisors(n) : n in [1..100] ]; - from Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

(MuPad)numlib::tau (n)$ n=1..90 - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 13 2008

(PARI from Joerg Arndt (arndt(AT)jjj.de), May 03, 2008)

N=17; default(seriesprecision, N); x=z+O(z^(N+1))

c=sum(j=1, N, j*x^j); \\ log case

s=-log(prod(j=1, N, (1-x^j)^(1/j))); \\ A000005 the number of divisors of n.

s=serconvol(s, c)

v=Vec(s)

(Other) sage: [sigma(n, 0)for n in xrange(1, 105)] # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 04 2009]

See A002183, A002182 for records. See A000203 for the sum-of-divisors function sigma(n).

Cf. A001227, A005237, A005238, A006601, A006558, A019273, A039665, A049051.

Cf. A001826, A001842, A051731, A066446, A129510, A115361, A129372, A115361, A127093, A143319.

a(n) = A091220(A091202(n)). Cf. A061017.

Factorizations into given number of factors: writing n = x*y (A038548, unordered, A000005, ordered), n = x*y*z (A034836, unordered, A007425, ordered), n = w*x*y*z (A007426, ordered).

a(n) = A083888(n) + A083889(n) + A083890(n) + A083891(n) + A083892(n) + A083893(n) + A083894(n) + A083895(n) + A083896(n). - Reinhard Zumkeller, May 08 2003

a(n) = A083910(n) + A083911(n) + A083912(n) + A083913(n) + A083914(n) + A083915(n) + A083916(n) + A083917(n) + A083918(n) + A083919(n). - Reinhard Zumkeller, May 08 2003

A159933, A159934 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 26 2009]

Cf. A027750, A163280. [From Omar E. Pol (info(AT)polprimos.com), Oct 22 2009]

Sequence in context: A074848 A167447 A134687 this_sequence A122667 A122668 A073668

Adjacent sequences: A000002 A000003 A000004 this_sequence A000006 A000007 A000008

easy,core,nonn,nice,mult

N. J. A. Sloane (njas(AT)research.att.com).

1,3

Number of elements in a reduced residue system modulo n.

Degree of the n-th cyclotomic polynomial (cf. A013595). - Benoit Cloitre (benoit7848c(AT)orange.fr), Oct 12 2002

Number of distinct generators of a cyclic group of order n. Number of primitive n-th roots of unity.(A primitive n-th root x is such that x^k is not equal to 1 for k=1, 2, ..., n-1, but x^n=1) - Lekraj Beedassy (blekraj(AT)yahoo.com), Mar 31 2005

Also number of complex Dirichlet characters modulo n and sum(k=1,n,a(k)) is asymptotic to (3/pi^2)*n^2. - S. R. Finch (Steven.Finch(AT)inria.fr), Feb 16 2006

a(n) is the highest degree of irreducible polynomial dividing 1 + x + x^2 + ... + x^(n-1) = (x^n - 1)/(x - 1). - Alexander Adamchuk (alex(AT)kolmogorov.com), Sep 02 2006, corrected Sep 27 2006

a(p) = p - 1 for prime p. a(n) is even for n>2. For n>2 a(n)/2 = A023022(n) = number of partitions of n into 2 ordered relatively prime parts. - Alexander Adamchuk (alex(AT)kolmogorov.com), Jan 25 2007

Row sums of A127448. - Mats O. Granvik (mgranvik(AT)abo.fi), May 28 2008

Equals row sums of triangle A143239 (a consequence of the Dedekind-Liouville rule, Cf. "Concrete Mathematics" p. 137). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 01 2008]

Number of automorphisms of the cyclic group of order n. [From Benoit Jubin (benoit_jubin(AT)yahoo.fr), Aug 09 2008]

Equals row sums of triangle A143353. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 10 2008]

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 24.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 193.

C. W. Curtis, Pioneers of Representation Theory ..., Amer. Math. Soc., 1999; see p. 3.

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.

Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994, p. 137. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 01 2008]

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 60, 62, 63, 288, 323, 328, 330.

M. Lal and P. Gillard, Table of Euler's phi function, n < 10^5, Math. Comp., 23 (1969), 682-683.

P. Ribenboim, The New Book of Prime Number Records.

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

Daniel Forgues, Table of n, phi(n) for n=1..100000

Joerg Arndt, Fxtbook

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].

D. Alpern, Factorization using the Elliptic Curve Method(along with sigma_0, sigma_1 and phi functions)

F. Bayart, Indicateur d'Euler

A. Bogomolny, Euler Function and Theorem

C. K. Caldwell, The Prime Glossary, Euler's phi function

K. Ford, [math/9907204] The number of solutions of phi(x)=m

H. Fripertinger, The Euler phi function

Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors ..., J. Integer Seqs., Vol. 6, 2003.

Mathforum, Proving phi(m) Is Even

K. Matthews, Factorizing n and calculating phi(n),omega(n),d(n),sigma(n) and mu(n)

Graeme McRae, Euler's Totient Function

Primefan, Euler's Totient Function Values For n=1 to 500, with Divisor Lists

Marko Riedel, Combinatorics and number theory page.

K. Schneider, PlanetMath.org, Euler phi-function

W. Sierpinski, Euler's Totient Function And The Theorem Of Euler

U. Sondermann, Euler's Totient Function

W. A. Stein, Phi is a Multiplicative Function

G. Villemin, Totient d'Euler

A. de Vries, The prime factors of an integer (along with Euler's phi and Carmichael's lambda functions)

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Wikipedia, Euler's totient function

Wolfram Research, First 50 values of phi(n)

G. Xiao, Numerical Calculator, To display phi(n) operate on "eulerphi(n)"

Index entries for "core" sequences

phi(n) = n*Product_{distinct primes p dividing n} (1-1/p).

Sum_{ d divides n } phi(d) = n.

phi(n) = Sum_{ d divides n } mu(d)*n/d, mu(d) = Moebius function A008683.

Sum_{n >= 1} phi(n)/n^s = zeta(s-1)/zeta(s). Also Sum_{n >= 1} phi(n)*x^n/(1-x^n) = x/(1-x)^2.

Multiplicative with a(p^e) = (p-1)*p^(e-1). - David W. Wilson (davidwwilson(AT)comcast.net), Aug 01, 2001.

Sum_{n>=1} [phi(n)*ln(1-x^n)/n] = -x/(1-x) for -1<x<1 (cf. A002088) - Henry Bottomley (se16(AT)btinternet.com), Nov 16 2001

a(n)=binomial(n+1, 2) - sum{i=1, n-1, a(i)*floor(n/i)} (see A000217 for inverse) - Jon Perry (perry(AT)globalnet.co.uk), Mar 02 2004

Comment from Pieter Moree, Sep 10 2004: It is a classical result (certainly known to Landau, 1909) that lim inf n/phi(n)=1 (taking n to be primes), lim sup n/(phi(n) log log n)=e^{gamma}, with gamma = Euler's constant (taking n to be products of consecutive primes starting from 2 and applying Mertens' theorem). See e.g. Ribenboim, pp. 319-320.

a(n)=sum(i=1, n, | k(n, i) | ) where k(n, i) is the Kronecker symbol. Also a(n)=#{ 1<=i<=n : k(n, i)=0} where k(n, i) is the Kronecker symbol. - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 06 2004

Dirichlet generating function: zeta(s-1)/zeta(s). - Franklin T. Adams-Watters, Sep 11 2005.

Conjecture : limit Sum((-1)^i/(i * phi(i)) 2<=i<=Infinity) exists and is ca. 0.558. - Orges Leka (oleka(AT)students.uni-mainz.de), Dec 23 2004

Equals A054525 * [1,2,3,...]; i.e. the Moebius transform of the natural numbers. - Gary W. Adamson (qntmpkt(AT)yahoo.com), May 20 2007

Equals row sums of triangle A143276 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 03 2008]

with(numtheory): A000010 := phi; [ seq(phi(n), n=1..100) ]; # version 1

with(numtheory): phi := proc(n) local i, t1, t2; t1 := ifactors(n)[2]; t2 := n*mul((1-1/t1[i][1]), i=1..nops(t1)); end; # version 2

a[n_] := EulerPhi[n]

(AXIOM) [eulerPhi(n) for n in 1..100]

(MAGMA) [ EulerPhi(n) : n in [1..100] ]; - from Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

(PARI) A000010(n)=eulerphi(n)

(SAGE program from Jaap Spies, Jan 7, 2007)

# euler_phi is a standard function in SAGE.

def A000010(n): return euler_phi(n)

def A000010_list(n): return [ euler_phi(i) for i in range(1, n+1)]

(PARI) { for (n=1, 100000, write("b000010.txt", n, " ", eulerphi(n))); } [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), Apr 26 2009]

(Other) sage: [euler_phi(n)for n in xrange(1, 70)]# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 06 2009]

Cf. A008683, A003434, A007755, A049108, A002202 (values).

For inverse see A002181, A006511, A058277.

Jordan function J_k(n) is a generalization - see A059379 and A059380 (triangle of values of J_k(n)), A000010 (J_1), A059376 (J_3), A059377 (J_4), A059378 (J_5).

Cf. A054521, A023022, A054525, A134540.

Row sums of triangle A134540.

A143276 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 03 2008]

Equals right and left borders of triangle A159937. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 26 2009]

Sequence in context: A011773 A080737 A152455 this_sequence A003978 A122645 A122646

Adjacent sequences: A000007 A000008 A000009 this_sequence A000011 A000012 A000013

easy,core,nonn,mult,nice

N. J. A. Sloane (njas(AT)research.att.com).

Replaced a geocities.com URL - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Oct 30 2009

0,5

C(n,k) = number of k-element subsets of an n-element set.

Row n gives coefficients in expansion of (1+x)^n.

C(n+k-1,n-1) is the number of ways of placing k indistinguishable balls into n boxes (the "bars and stars" argument - see Feller).

C(n-1,m-1) is the number of compositions of n with m summands.

If thought of as an infinite lower triangular matrix, inverse begins:

+1

-1 +1

+1 -2 +1

-1 +3 -3 +1

+1 -4 +6 -4 +1

The string of 2^n palindromic binomial coefficients starting after the A006516(n)-th entry are all odd. - Lekraj Beedassy (blekraj(AT)yahoo.com), May 20 2003

C(n+k-1,n-1) is the number of standard tableaux of shape (n,1^k). - Emeric Deutsch (deutsch(AT)duke.poly.edu), May 13 2004

Can be viewed as an array, read by antidiagonals, where the entries in the first row and column are all 1's and A(i,j) = A(i-1,j) + A(i,j-1) for all other entries. The determinants of all its n X n subarrays starting at (0,0) are all 1. - Gerald McGarvey (Gerald.McGarvey(AT)comcast.net), Aug 17 2004

Also the lower triangular readout of the exponential of a matrix whose entry {j+1,j} equals j+1 (and all other entries are zero). - Joseph Biberstine (jrbibers(AT)indiana.edu), May 26 2006

C(n-3,k-1) counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 132 and k descents. C(n-3,k-1) also counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 213 and k descents. - David Hoek (david.hok(AT)telia.com), Feb 28 2007

Inverse of A130595 (as an infinite lower triangular matrix). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Aug 21 2007

Consider integer lists LL of lists L of the form LL=[m#L]=[m#[k#2]] (where '#' means 'times') like LL(m=3,k=3) = [[2,2,2],[2,2,2],[2,2,2]]. The number of the integer list partitions of LL(m,k) is equal to C(m+k,k) if multiple partitions like [[1,1],[2],[2]] and [[2],[2],[1,1]] and [[2],[1,1],[2]] are count only once. For the example we find 4*5*6/3! = 20 = C(6,3). - Thomas Wieder (thomas.wieder(AT)t-online.de), Oct 03 2007

The infinitesimal generator for the Pascal triangle and its inverse is A132440. - Tom Copeland (tcjpn(AT)msn.com), Nov 15 2007

Row n>=2 gives the number of k-digit (k>0) base n numbers with strictly decreasing digits; e.g. row 10 for A009995. Similarly, row n-1>=2 gives the number of k-digit (k>1) base n numbers with strictly increasing digits; see A009993 and compare A118629. - Rick L. Shepherd (rshepherd2(AT)hotmail.com), Nov 25 2007

Comments from Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008: (Start) C(n+k-1, k) is the number of ways a sequence of length k can be partitioned into n subsequences (see the Naish link).

C(n+k-1, k) is also the number of n- (or fewer) digit numbers written in radix at least k whose digits sum to k. For example, in decimal, there are C(3+3-1,3)=10 3-digit numbers whose digits sum to 3 (see A052217) and also C(4+2-1,2)=10 4-digit numbers whose digits sum to 2 (see A052216). This relationship can be used to generate the numbers of sequences A052216 to A052224 (and further sequences using radix greater than 10). (End)

Denote by sigma_k(x_1,x_2,...,x_n) the elementary symmetric polynomials. Then: C(2n+1,2k+1)=sigma_{n-k}(x_1,x_2,...,x_n), where x_i=tan^2(i*Pi/(2n+1)),(i=1,2,...,n). C(2n,2k+1)=2n*sigma_{n-1-k}(x_1,x_2,...,x_{n-1}), where x_i=tan^2(i*Pi/(2n)), (i=1,2,...,n-1). C(2n,2k)=sigma_{n-k}(x_1,x_2,...,x_n), where x_i=tan^2((2i-1)Pi/(4n)), (i=1,2,...,n). C(2n+1,2k)=(2n+1)sigma_{n-k}(x_1,x_2,...,x_n), where x_i=tan^2((2i-1)Pi/(4n+2)), (i=1,2,...,n). - Milan R. Janjic (agnus(AT)blic.net), May 07 2008

Given matrices R and S with R(n,k) = C(n,k)*r(n-k) and S(n,k) = C(n,k)*s(n-k), then R*S = T where T(n,k) = C(n,k)*[r(.)+s(.)]^(n-k), umbrally. And, the e.g.f.s for the row polynomials of R, S and T are, respectively, exp(x*t)*exp[r(.)*x], exp(x*t)*exp[s(.)*x] and exp(x*t)*exp[r(.)*x]*exp[s(.)*x] = exp{[t+r(.)+s(.)]*x}. The row polynomials are essentially Appell polynomials. See A132382 for an example. [From Tom Copeland (tcjpn(AT)msn.com), Aug 21 2008]

Contribution from Clark Kimberling (ck6(AT)evansville.edu), Sep 15 2008: (Start)

As the rectangle R(m,n)=C(m+n-2,m-1), the weight array W (defined

generally at A114112) of R is essentially R itself, in the sense that

if row 1 and column 1 of W=A144225 are deleted, the remaining array is R. (End)

If A007318 = M as infinite lower triangular matrix, M^n gives A130595, A023531, A007318, A038207, A027465, A038231, A038243, A038255, A027466, A038279, A038291, A038303, A038315, A038327, A133371, A147716, A027467 for n=-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 respectively. [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 11 2008]

The coefficients of the polynomials with e.g.f. exp(x*t)*(cosh(t)+sinh(t)). [From Peter Luschny (peter(AT)luschny.de), Jul 09 2009]

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.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 63ff.

B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8. English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 4.

Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 306.

P. Curtz, Integration numerique des systemes differentiels..,C.C.S.A.,Arcueil,1969. [From Paul Curtz (bpcrtz(AT)free.fr), Mar 06 2009]

W. Feller, An Introduction to Probability Theory and Its Application, Vol. 1, 2nd ed. New York: Wiley, p. 36, 1968.

D. Fowler, The binomial coefficient function, Amer. Math. Monthly, 103 (1996), 1-17.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, p. 155.

D. Hoek, Parvisa moenster i permutationer [Swedish], 2007.

D. E. Knuth, The Art of Computer Programming, Vol. 1, 2nd ed., p. 52.

S. K. Lando, Lecture on Generating Functions, Amer. Math. Soc., Providence, R.I., 2003, pp. 60-61.

D. Merlini, F. Uncini and M. C. Verri, A unified approach to the study of general and palindromic compositions, Integers 4 (2004), A23, 26 pp.

Y. Moshe, The density of 0's in recurrence double sequences, J. Number Theory, 103 (2003), 109-121.

Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 6.

J. Riordan, Combinatorial Identities, Wiley, 1968, p. 2.

R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996, p. 143.

L. W. Shapiro, S. Getu, W.-J. Woan and L. C. Woodson, The Riordan group, Discrete Applied Math., 34 (1991), 229-239.

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

D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, pp. 115-8, Penguin Books 1987.

N. J. A. Sloane, First 141 rows of Pascal's triangle, formatted as a simple linear sequence n, a(n)

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].

V. Asundi, Generate a Yanghui Triangle [Broken link]

C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps

D. Butler, Pascal's Triangle

L. Euler, On the expansion of the power of any polynomial (1+x+x^2+x^3+x^4+etc)^n

L. Euler, De evolutione potestatis polynomialis cuiuscunque (1+x+x^2+x^3+x^4+etc)^n E709

S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle (arXiv:0802.2654)

Nick Hobson, Python program

Matthew Hubbard and Tom Roby, Pascal's Triangle From Top to Bottom

S. Kak, The Golden Mean and the Physics of Aesthetics

W. Knight, Short Table of Binomial Coefficients

W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.

Mathforum, Pascal's Triangle

Mathforum, Links for Pascal's triangle

C. McDermottroe, n-th row generator of Pascal's triangle

D. Merlini, R. Sprugnoli and M. C. Verri, An algebra for proper generating trees

Lee Naish Pascal's Triangle and debugging software

A. Necer, Series formelles et produit de Hadamard

G. Sivek et al., ThinkQuest, Pascal's Triangle Row Generator

N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).

H. Verrill, Pascal's Triangle and related triangles

G. Villemin's Almanach of Numbers, Triangle de Pascal

Eric Weisstein's World of Mathematics, More information.

Thomas Wieder, Home Page.

Thomas Wieder, (Old) Home Page.

Wikipedia, Pascal's triangle

H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, pp. 12ff.

K. Williams, Mathforum, Interactive Pascal's Triangle

K. Williams, MathForum, Pascal's Triangle to Row 19

D. Zeilberger, [math/9809136] The Combinatorial Astrology of Rabbi Abraham Ibn Ezra

Index entries for triangles and arrays related to Pascal's triangle

a(n, m)=binomial(n, m); a(n+1, m) = a(n, m)+a(n, m-1), a(n, -1) := 0, a(n, m) := 0, n<m; a(0, 0)=1.

C(n, k)=n!/(k!(n-k)!) if 0<=k<=n, otherwise 0. C(n, k) = C(n-1, k) + C(n-1, k-1).

G.f.: 1/(1-y-xy)=Sum(C(n, k)x^k*y^n, n, k>=0); also g.f.: 1/(1-x-y)=Sum(C(n+k, k)x^k*y^n, n, k>=0). G.f. for row n: (1+x)^n = sum(k=0..n, C(n, k)x^k). G.f. for column n: x^n/(1-x)^n.

E.g.f.: A(x, y)=exp(x+xy). E.g.f. for column n: x^n*exp(x)/n!.

In general the m-th power of A007318 is given by: T(0, 0) = 1, T(n, k) = T(n-1, k-1) + m*T(n-1, k), where n is the row-index and k is the column; also T(n, k) = m^(n-k) C(n, k).

Triangle T(n, k) read by rows; given by A000007 DELTA A000007, where DELTA is Deleham's operator defined in A084938.

With P(n+1) = the number of integer partitions of (n+1), p(i) = the number of parts of the i-th partition of (n+1), d(i) = the number of different parts of the i-th partition of (n+1), m(i, j) = multiplicity of the j-th part of the i-th partition of (n+1), sum_[p(i)=k]_{i=1}^{P(n+1)} = sum running from i=1 to i=P(n+1) but taking only partitions with p(i)=(k+1) parts into account, prod_{j=1}^{d(i)} = product running from j=1 to j=d(i) one has B(n, k) = sum_[p(i)=(k+1)]_{i=1}^{P(n+1)} 1/prod_{j=1}^{d(i)} m(i, j)! E.g. B(5, 3) = 10 because n=6 has the following partitions with m=3 parts: (114), (123), (222). For their multiplicities one has: (114): 3!/(2!*1!) = 3, (123): 3!/(1!*1!*1!) = 6, (222): 3!/3! = 1. The sum is 3+6+1=10=B(5, 3). - Thomas Wieder (wieder.thomas(AT)t-online.de), Jun 03 2005

C(n, k) = Sum_{j, 0<=j<=k} = (-1)^j*C(n+1+j, k-j)*A000108(j) . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 10 2005

G.f.: 1 + x(1 + x) + x^3(1 + x)^2 + x^6(1 + x)^3 + ... . - Michael Somos Sep 16 2006

Sum_{k, 0<=k<=[n/2]} x^(n-k)*T(n-k,k)= A000007(n), A000045(n+1), A002605(n), A030195(n+1), A057087(n), A057088(n), A057089(n), A057090(n), A057091(n), A057092(n), A057093(n) for x= 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 respectively . Sum_{k, 0<=k<=[n/2]} (-1)^k*x^(n-k)*T(n-k,k)= A000007(n), A010892(n), A009545(n+1), A057083(n), A001787(n+1), A030191(n), A030192(n), A030240(n), A057084(n), A057085(n+1), A057086(n), A084329(n+1) for x= 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20 respectively . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Sep 16 2006

C(n,k) <= A062758(n) for n > 1. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Mar 04 2008

C(t+p-1, t) = Sum(i=0..t, C(i+p-2, i)) = Sum(i=1..p, C(i+t-2, t-1)) A binomial number is the sum of its left parent and all its right ancestors, which equals the sum of its right parent and all its left ancestors. - Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008

Triangle begins:

1

1, 1

1, 2, 1

1, 3, 3, 1

1, 4, 6, 4, 1

1, 5, 10, 10, 5, 1

1, 6, 15, 20, 15, 6, 1

1, 7, 21, 35, 35, 21, 7, 1

1, 8, 28, 56, 70, 56, 28, 8, 1

1, 9, 36, 84, 126, 126, 84, 36, 9, 1

1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1

1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1

A007318 := (n, k)->binomial(n, k);

with(combstruct):for n from 0 to 11 do seq(count(Combination(n), size=m), m = 0 .. n) od; - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 16 2007

Flatten[Table[Binomial[n, k], {n, 0, 11}, {k, 0, n}]] (from Robert G. Wilson v Jan 19 2004)

(AXIOM) -- (start)

)set expose add constructor OutputForm

pascal(0, n) == 1

pascal(n, n) == 1

pascal(i, j | 0 < i and i < j) == pascal(i-1, j-1) + pascal(i, j-1)

pascalRow(n) == [pascal(i, n) for i in 0..n]

displayRow(n) == output center blankSeparate pascalRow(n)

for i in 0..20 repeat displayRow i -- (end)

(PARI) C(n, k)=if(k<0|k>n, 0, n!/k!/(n-k)!)

(PARI) C(n, k)=if(n<0, 0, polcoeff((1+x)^n, k))

(PARI) C(n, k)=if(k<0|k>n, 0, if(k==0&n==0, 1, C(n-1, k)+C(n-1, k-1)))

(Python) See Hobson link.

Equals differences between consecutive terms of A102363 - David G. Williams (davidwilliams(AT)Paxway.com), Jan 23 2006

Cf. A047999, A026729, A052553. Row sums give A000079 (powers of 2).

Cf. A083093 (triangle read mod 3).

Partial sums of rows give triangle A008949.

Infinite matrix squared: A038207, cubed: A027465

Cf. A101164. If rows are sorted we get A061554 or A107430.

Another version: A108044.

Cf. A008277.

Cf. A132311, A132312.

Cf. A052216, A052217, A052218, A052219, A052220, A052221, A052222, A052223.

Cf. A144225. [From Clark Kimberling (ck6(AT)evansville.edu), Sep 15 2008]

Sequence in context: A154926 A117440 A118433 this_sequence A108086 A130595 A108363

Adjacent sequences: A007315 A007316 A007317 this_sequence A007319 A007320 A007321

nonn,tabl,nice,easy,core

N. J. A. Sloane (njas(AT)research.att.com), Mira Bernstein (mira(AT)math.berkeley.edu)

0,3

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 (layman(AT)math.vt.edu), 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 (callan(AT)stat.wisc.edu), 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. n=5, we consider the distinct subsets of ABBCCCDDDD and there are 5!=120.) - Jon Perry (perry(AT)globalnet.co.uk), Jun 12 2003

n! is the smallest number with that prime signature. E.g. 720 = 2^4*3^2*5. - Amarnath Murthy (amarnath_murthy(AT)yahoo.com), Jul 01 2003

a(n) is the permanent of the n X n matrix M with M(i,j) = 1 . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Dec 15 2003

Given n objects of distinct sizes (e.g. areas, volumes) such that each object is sufficiently large simultaneously to contain all previous objects, then n! is the total number of essentially different arrangements using all n objects. Arbitrary levels of nesting of objects is permitted within arrangements. (...sequence inspired by considering left-over moving boxes.). If the restriction exists that each object is only 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 (rshepherd2(AT)hotmail.com), Jan 14 2004

Stirling transform of a(n)=[2,2,6,24,120,...] is A052856(n)=[2,2,4,14,76,...]. - Michael Somos Mar 04 2004

Stirling transform of a(n)=[1,2,6,24,120,...] is A000670(n)=[1,3,13,75,...]. - Michael Somos Mar 04 2004

Stirling transform of a(n)=[0,2,6,24,120,...] is A052875(n)=[0,2,12,74,...]. - Michael Somos Mar 04 2004

Stirling transform of a(n-1)=[1,1,2,6,24,...] is A000629(n-1)=[1,2,6,26,...]. - Michael Somos Mar 04 2004

Stirling transform of a(n-1)=[0,1,2,6,24,...] is A002050(n-1)=[0,1,5,25,140,...]. - Michael Somos Mar 04 2004

Stirling transform of A006252(n)=[1,1,2,4,14,38,216,...] is a(n)=[1,2,6,24,120,...]. - Michael Somos Mar 04 2004

Stirling transform of -(-1)^n*A089064(n)=[1,0,1,-1,8,-26,194,...] is a(n-1)=[1,1,2,6,24,120,...]. - Michael Somos Mar 04 2004

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[e(n,k)s(k), k=0...n], where e(n,k) is a first-order Eulerian number [A008292]. - Ross La Haye (rlahaye(AT)new.rr.com), Feb 13 2005

1, 6, 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 (pbarry(AT)wit.ie), 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 (amarnath_murthy(AT)yahoo.com), 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 (rshepherd2(AT)hotmail.com), 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)=number of deco polyominoes of height n (n>=1; see definitions in the Barcucci et al. references). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 07 2006

a(n) = number of partition tableaux of size n. See Steingrimsson/Williams link for the definition. - David Callan (callan(AT)stat.wisc.edu), Oct 06 2006

Consider the n! permutation of the integer sequence [n]=1,2,...,n. The i-th permutation consists of ncycle(i) permutation cycles. Then, if the sum 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 (thomas.wieder(AT)t-online.de), Oct 11 2006

a(n) = 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 (callan(AT)stat.wisc.edu), 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 (rshepherd2(AT)hotmail.com), Jan 14 2004. - Thomas Wieder (thomas.wieder(AT)t-online.de), 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 (paulmuljadi(AT)yahoo.com), Apr 15 2008

Number of terms in a determinant when writing down all multiplication permutations. [From Mats O. Granvik (mgranvik(AT)abo.fi), Sep 12 2008]

Triangle A144107 has row sums = n!(n>0) with right border n! and left border A003319, the INVERTi transform of (1, 2, 6, 24,...) [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 11 2008]

Equals INVERT transform of A052186: (1, 0, 1, 3, 14, 77,...) and row sums of triangle A144108. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 11 2008]

Contribution from A. Umar (aumarh(AT)squ.edu.om), Oct 12 2008: (Start)

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)

Contribution from Calin D. Morosan (cd_moros(AT)alumni.concordia.ca), Nov 28 2008: (Start)

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). (End)

Sum_{n>=0} 1/a(n) = e [From Jaume Oliver Lafont (joliverlafont(AT)gmail.com), Mar 03 2009]

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 ). [From Kailasam Viswanathan Iyer (kvi(AT)nitt.edu), 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. [From Timothy Hopper (timothyhopper(AT)hotmail.co.uk), Aug 20 2009]

a(n) is also the determinant of an square matrix, An, whose coefficients are the reciprocals of beta function: a{i,j}=1/beta(i,j), det(An)=n! [From Barbarel Tres Mil (barbarel3000(AT)yahoo.es), Sep 21 2009]

Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Oct 20 2009: (Start)

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.

(End)

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.

S.B.Akers and B.Krishnamurthy, "A group-theoretic model for symmetric interconnection networks" , IEEE Trans. Comput., 38(4), April 1989, 555-566. [From Kailasam Viswanathan Iyer (kvi(AT)nitt.edu), Mar 18 2009]

E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.

E. Barcucci, A. Del Lungo, R. Pinzani and R. Sprugnoli, La hauteur des polyominos dirige's verticalement convexes, Actes du 31e Se'minaire Lotharingien de Combinatoire, Publ. IRMA, Universite' Strasbourg I (1993).

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.

M. Bhargava, The Factorial Function and Generalizations, Amer. Math. Monthly 107 (2000) 783-799. [From Jonathan Sondow (jsondow(AT)alumni.princeton.edu), Jul 26 2009]

G. Labelle et al., Stirling numbers interpolation using permutations with forbidden subsequences, Discrete Math. 246 (2002), 177-195.

R. Ondrejka, 1273 exact factorials, Math. Comp., 24 (1970), 231.

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

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

Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.

R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.

Umar, A. On the semigroups of order-decreasing finite full transformations, Proc. Roy. Soc. Edinburgh 120A (1992), 129-142. [From A. Umar (aumarh(AT)squ.edu.om), Oct 12 2008]

D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, pp. 102 Penguin Books 1987.

R. W. Whitty, Rook polynomials on two-dimensional surfaces..., Discrete Math., 308 (2008), 674-683.

N. J. A. Sloane, The first 100 factorials: Table of n, n! for n = 0..100

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].

David Applegate and N. J. A. Sloane, Table giving cycle index of S_0 through S_40 in Maple format [gzipped]

H. Bottomley, Illustration of initial terms

D. Butler, Factorials!

David Callan, Counting Stabilized-Interval-Free Permutations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.1.8.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

R. M. Dickau, Permutation diagrams

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 18

H. Fripertinger, The elements of the symmetric group

H. Fripertinger, The elements of the symmetric group in cycle notation

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 20

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 297

Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets

C. Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.

W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

Paul Leyland, Generalized Cullen and Woodall numbers

N. E. Noerlund, Vorlesungen ueber Differenzenrechnung Springer 1924, p. 98.

Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7

F. Richman, Multiple precision arithmetic(Computing factorials up to 765!)

R. P. Stanley, A combinatorial miscellany

Einar Steingrimsson and Lauren K. Williams, Permutation tableaux and permutation patterns

G. Villemin's Almanach of Numbers, Factorielles

A. Walker, Factors of n!+-1

Sage Weil, The First 999 Factorials

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Laguerre Polynomial

Eric Weisstein's World of Mathematics, Diagonal Matrix

Eric Weisstein's World of Mathematics, Chromatic Invariant

Wikipedia, Factorial

Index entries for sequences related to factorial numbers

Index entries for "core" sequences

Barbarel Tres Mil, Beta function matrix determinant Psychedelic Geometry blogspot-09/21/09 [From Barbarel Tres Mil (barbarel3000(AT)yahoo.es), Sep 21 2009]

Sum((-1)^i * i^n * binomial(n, i), i=0..n) = (-1)^n * n! - Yong Kong (ykong(AT)curagen.com), Dec 26 2000

Sum((-1)^i * (n-i)^n * binomial(n, i), i=0..n) = n! - Peter C. Heinig (algorithms(AT)gmx.de), Apr 10 2007

The sequence trivially satisfies the recurrence a(n+1) = sum(binomial(n,k)*a(k)*a(n-k),k=0..n). - Robert Ferreol, Dec 05 2009

a(0)=1; 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, diff(1/(2-x), x$n)), n=1, 2... - Karol A. Penson (penson(AT)lptl.jussieu.fr), Nov 12 2001

E.g.f.: 1/(1-x).

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)} . - DELEHAM Philippe, Jul 08 2004

Binomial transform of A000166. - Ross La Haye (rlahaye(AT)new.rr.com), Sep 21 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 4! = (6+8+12+24) - (2+3+4+6+8+12) + 10 - 1 4! = 50 - 35 + 10 - 1 = 24 - Jon Perry (perry(AT)globalnet.co.uk), Nov 14 2005

a(0)=1, a(1)=1; a(n)=(n-1)*(a(n-1)+a(n-2)), n >= 2. - Matthew J. White (mattjameswhite(AT)hotmail.com), Feb 21 2006

a(n) = 1/Det[Table[(i+j)!/i!/(j+1)!,{i,1,n},{j,1,n}]] for n>0. This is a matrix with Catalan numbers on diagonal. - Alexander Adamchuk (alex(AT)kolmogorov.com), Jul 04 2006

Hankel transform of A074664 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jun 21 2007

For n>=2, a(n-2)=(-1)^n*sum((j+1)*stirling1(n,j+1),j=0..n-1); [From Milan R. Janjic (agnus(AT)blic.net), Dec 14 2008]

Contribution from Paul Barry (pbarry(AT)wit.ie), Jan 15 2009: (Start)

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)

A007814(a(n))=n-A000120(n). [From Vladimir Shevelev (shevelev(AT)bgu.ac.il), Jul 20 2009]

a(n) = Prod_{p prime} p^{Sum_{k>0} [n/p^k]} by Legendre's formula for the highest power of a prime dividing n!. [From Jonathan Sondow (jsondow(AT)alumni.princeton.edu), Jul 24 2009]

a(n) = A053657(n)/A163176(n) for n > 0. [From Jonathan Sondow (jsondow(AT)alumni.princeton.edu), Jul 26 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. [From Timothy Hopper (timothyhopper(AT)hotmail.co.uk), Aug 12 2009]

a(0)=1, a(1)=1; a(n)=(a(n-1)^2+a(n-1)*a(n-2))/a(n-2), n>=2 [From Jaume Oliver Lafont (joliverlafont(AT)gmail.com), Sep 21 2009]

a(n)=Gamma(n+1) [From Barbarel Tres Mil (barbarel3000(AT)yahoo.es), Sep 21 2009]

There are 3! = 1*2*3 = 6 ways to arrange 3 letters {a,b,c}, namely abc, acb, bac, bca, cab, cba.

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:=40: f:=array(0..M): f[0]:=1: lprint("n= ", 0); lprint(f[0]); f[1]:=x[1]: lprint("n= ", 1); lprint(f[1]);

for n from 2 to M do f[n]:=expand((1/n)*add( x[l]*f[n-l], l=1..n)); lprint("n= ", n); lprint(f[n]); od:

with(combinat):seq((stirling1(j+1, 1)*(stirling2(j+1, 1))*(-1)^j), j=0..20); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 30 2007

with(combstruct):ZL0:=[S, {S=Set(Cycle(Z, card>0))}, labeled]: seq(count(ZL0, size=n), n=0..20); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Sep 26 2007

a:=n->mul(numer (k/(k+1)), k=1..n): seq(a(n), n=0..20); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 26 2008

a:=n->mul(denom (1/(k+2)), k=0..n): seq(a(n), n=-2..18); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 26 2008

restart:a:= proc(n) option remember; if n=0 then 1 else add(a(n-1), j=0..n-1) fi end: seq (a(n), n=0..20); # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 29 2009]

a[n_] := n!; Table[a[n], {n, 0, 20}] - Stefan Steinerberger (stefan.steinerberger(AT)gmail.com), Mar 30 2006

Table[(-1)^(n + 1)* Sum[(-1)^(n - k) k (-1)^(n - k) StirlingS1[n + 1, k + 1], {k, 0, n}], {n, 1, 21}] [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jul 08 2009]

a[n_] := Product[Prime[j]^Sum[Floor[n/Prime[j]^k], {k, 1, Ceiling[Log[n]/Log[Prime[j]]]}], {j, 1, n}]; Table[a[n], {n, 1, 20}] [From Jonathan Sondow (jsondow(AT)alumni.princeton.edu), Jul 24 2009]

(AXIOM) [factorial(n) for n in 0..10]

(MAGMA) a:= func< n | Factorial(n) >; [ a(n) : n in [0..10]];

(PARI) a(n)=if(n<0, 0, n!)

(Other) sage: [stirling_number1(n, 1) for n in xrange(1, 22)] # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 16 2009]

Cf. A047920, A048631, A003422, A000165, A001563, A001044, A010050, A009445, A038507, A033312.

Cf. A034886.

Factorial base representation: A007623.

Cf. A012245.

Cf. A144108, A052186, A144107, A003319 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 11 2008]

Complement of A063992. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Oct 11 2008]

Row products of A139547. [From Mats Granvik (mats.granvik(AT)abo.fi), Jun 28 2009]

Cf. A053657, A163176. [From Jonathan Sondow (jsondow(AT)alumni.princeton.edu), Jul 26 2009]

Sequence in context: A072167 A154659 A155456 this_sequence A104150 A124355 A133942

Adjacent sequences: A000139 A000140 A000141 this_sequence A000143 A000144 A000145

core,easy,nonn,nice

N. J. A. Sloane (njas(AT)research.att.com).

0,3

Also number of nonnegative solutions to b+2c+3d+4e+...=n and the number of nonnegative solutions to 2c+3d+4e+...<=n. - Henry Bottomley (se16(AT)btinternet.com), Apr 17 2001

a(n) is also the number of conjugacy classes in the symmetric group S_n (and the number of irreducible representations of S_n).

Also the number of rooted trees with n+1 nodes and height at most 2.

Coincides with the sequence of numbers of nilpotent conjugacy classes in the Lie algebras gl(n). A006950, A015128 and this sequence together cover the nilpotent conjugacy classes in the classical A,B,C,D series of Lie algebras. - Alexander Elashvili, Sep 08 2003

a(n)=a(0)b(n)+a(1)b(n-2)+a(2)b(n-4)+... where b=A000009.

Number of distinct Abelian groups of order p^n, where p is prime (the number is independent of p). - Lekraj Beedassy (blekraj(AT)yahoo.com), Oct 16 2004

Number of graphs on n vertices that do not contain P3 as an induced subgraph. - Washington Bomfim (webonfim(AT)bol.com.br), May 10 2005

It is unknown if there are infinitely many partition numbers divisible by 3, although it is known that there are infinitely many divisible by 2. - Jonathan Vos Post (jvospost3(AT)gmail.com), Jun 21 2005

Numbers of terms to be added when expanding the n-th derivative of 1/f(x). - Thomas Baruchel (baruchel(AT)users.sourceforge.net), Nov 07 2005

a(n) = A114099(9*n). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Feb 15 2006

Comment from Maurice D. Craig (towenaar(AT)optusnet.com.au), Oct 30 2006: sequence agrees with expansion of Molien series for symmetric group S_n up to the term in x^n.

Also the number of nonnegative integer solutions to x_1+x_2+x_3+...+x_n=n such that n>=x_1>=x_2>=x_3>=...>=x_n>=0, because by letting y_k=x_k-x_(k+1)>=0 (where 0<k<n) we get y_1+2y_2+3y_3+...+(n-1)y_(n-1)+nx_n=n. - Werner Grundlingh (wgrundlingh(AT)gmail.com), Mar 14 2007

Let P(z):= Sum{j=0..inf} b_j z^j, b_0 != 0. Then 1/P(z) = Sum{j=0..inf} c_j z^j, where the c_j must be computed from the infinite triangular system b_0 c_0 = 1, b_0 c_1 + b_1 c_0 = 0 and so on (Cauchy products of the coefficients set to zero). The n-th partition number arises as the number of terms in the numerator of the expression for c_n: The coefficient c_n of the inverted power series is a fraction with b_0^(n+1) in the denominator and in its numerator having a(n) products of n coefficients b_i each. The partitions may be read off from the indices of the b_i. - Peter C. Heinig (algorithms(AT)gmx.de), Apr 09 2007

A026820(a(n),n) = A134737(n) for n>0. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Nov 07 2007

Equals row sums of triangle A137683 - Gary W. Adamson (qntmpkt(AT)yahoo.com), Feb 05 2008

This is also the number of parts equal to 1 in the outer shell of the partitions of n+1 (see A138151). - Omar E. Pol (info(AT)polprimos.com), Apr 17 2008

a(n)= the number of different ways to run up a staircase with n steps, taking steps of sizes 1,2,3,... and r (r<=n), where the order is not important and there is no restriction on the number or the size of each step taken. - Mohammad K. Azarian (azarian(AT)evansville.edu), May 21 2008

Equals the eigenvector of triangle A145006 and row sums of the eigentriangle of the partition numbers, A145007. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 28 2008]

Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 05 2008: (Start)

Starting with offset 1 = INVERT transform of (1, 1, 0, 0, -1, 0, -1,...),

where A080995, the characteristic function of A001318 (1, 2, 5, 7, 12,...) is

signed (++ -- ++,...) as to 1's. This is equivalent to Lim__{n=1..inf}

A145006^n as a vector. The INVERT transform of (1, 1, 0, 0, -1,...) begins (1, 2,..)

then for each successive operation we take a dot product of (1, 1, 0, 0, -1,...) in reverse and the ongoing results of our series (1, 2, 3, 5, 7,...)

then add the result to the next term in (1, 1, 0, 0, -1,...). For example, a

(7) = 15 = (0, -1, 0, 0, 1, 1) dot (1, 2, 3, 5, 7, 11) = (0*1, (-1)*2, 0*3, 0*5, 1*7, 1*11)

= (-2 + 7 + 11) = 16, then add to (-1) = 15. (End)

Convolved with A147843 = A000203 prefaced with a zero: (0, 1, 3, 4, 7,...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 15 2008]

Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Jun 12 2009: (Start)

Equals an infinite convolution product_(1,1,1,...)*(1,0,1,0,1,...)*

(1,0,0,1,0,0,1,...)*(1,0,0,0,1,0,0,0,1,...)* ...; = a*b*c*...; where a =

(1/(1-x), b = (1/(1-x^2), c = (1/(1-x^3), ...etc. An array by rows: row 1 =

a, row 2 = a*b, row 3 = a*b*c,...; gives:

1, 1, 1, 1, 1, 1,. 1,. 1,. 1,..1,... = (a).................................

1, 1, 2, 2, 3, 3,. 4,..4,. 5,..5,... = (a*b)...............................

1, 1, 2, 3, 4, 5,. 7,..8,.10,.11,... = (a*b*c).............................

1, 1, 2, 3, 4, 5,. 6,..9,.11,.17,... = (a*b*c*d)...........................

1, 1, 2, 3, 5, 5,. 7,.10,.13,.18,... = (a*b*c*d*e).........................

1, 1, 2, 3, 5, 7,.11,.14,.20,.25,... = (a*b*c*d*e*f).......................

1, 1, 2, 3, 5, 7,.11,.15,.21,.27,... = (a*b*c*d*e*f*g).....................

1, 1, 2, 3, 5, 7,.11,.15,.22,.28,... = (a*b*c*d*e*f*g*h)...................

1, 1, 2, 3, 5, 7,.11,.15,.22,.29,... = (a*b*c*d*e*f*g*h*i).................

...with rows tending to A000041. Partition triangles A058398 = ascending

antidiagonals. Partition triangle A008284 reversal of A058398. (End)

a(n) is also the number of partitions of 2n into even parts. More generally, it appears that a(n) is also the number of partitions of k*n into parts divisible by k, for k>0. [From Omar E. Pol (info(AT)polprimos.com), Nov 20 2009, Nov 25 2009]

Starting with offset 1 = row sums of triangle A168532 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 28 2009]

Contribution from Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Jan 21 2010: (Start)

a(n) = A026820(n,n);

a(n) = A108949(n)+A045931(n)+A108950(n) = A130780(n)+A171966(n)-A045931(n) = A045931(n)+A171967(n). (End)

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 836.

George E. Andrews, The Theory of Partitions, Addison-Wesley, Reading, Mass., 1976

G. E. Andrews & K. Ericksson, Integer Partitions, Cambridge University Press 2004.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 307.

R. Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; Chapter III.

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997

B. C. Berndt, Number Theory in the Spirit of Ramanujan, Chap. I Amer. Math. Soc. Providence RI 2006.

L. E. Dickson, History of the Theory of Numbers, Vol.II Chapter III pp. 101-164,Chelsea NY 1992.

N. J. Fine, Basic Hypergeometric Series and Applications, Amer. Math. Soc., 1988; p. 37, Eq. (22.13).

H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4, Cambridge Univ. Press, 1958, p. 90.

G. H. Hardy and S. Ramanujan, Asymptotic formulae in combinatorial analysis, Proc. London Math. Soc., 17 (1918), 75-.

J. M. Kane, Distribution of orders of Abelian groups, Math. Mag., 49 (1976), 132-135.

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, (to appear), section 7.2.1.4.

S. Markovski and M. Mihova, An explicit formula for computing the partition numbers p(n), preprint, 2005

D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIV.1, p. 491.

S. Ramanujan, Collected Papers, Chap. 25, Cambridge Univ. Press 1927 (Proceedings of the Camb.Phil.Soc., 19(1919)207-213).

S. Ramanujan, Collected Papers, Chap. 28, Cambridge Univ. Press 1927 (Proceedings of the London Math.Soc., 2, 18(1920)).

S. Ramanujan, Collected Papers, Chap. 30, Cambridge Univ. Press 1927 (Mathematische Zeitschrift, 9(1921)147-163).

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 122.

J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.

J. E. Roberts, Lure of the Integers, pp. 168-9 MAA 1992.

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

R. E. Tapscott and D. Marcovich, "Enumeration of Permutational Isomers: The Porphyrins", Journal of Chemical Education, 55 (1978), 446-447. [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Sep 21 2008]

Robert M. Young, "Excursions in Calculus", Mathematical Association of America, p. 367. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 05 2008]

Robert M. Ziff, "On Cardy's formula for the critical crossing probability in 2d percolation," J. Phys. A. 28, 1249-1255 (1995).

David W. Wilson, Table of n, a(n) for n = 0..10000

Joerg Arndt, Fxtbook

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].

S. Ahlgren and K. Ono, Addition and Counting: The Arithmetic of Partitions

S. Ahlgren & K. Ono, Congruence properties for the partition function

S. Ahlgren & K. Ono, Congruence properties for the partition function

G. Almkvist, Asymptotic Formulas and Generalized Dedekind Sums

G. Almkvist and H. S. Wilf, On the coefficients in the Hardy-Ramanujan-Rademacher formula for p(n)

Amazing Mathematical Object Factory, Information on Partitions [Broken link corrected by Steve Vonn (5463math(AT)gmail.com), Jan 03 2009]

G. E. Andrews, Three Aspects of Partitions

G. E. Andrews, On a Partition Function of Richard Stanley.

G. E. Andrews & K. Ono, Ramanujan's congruences and Dyson's crank

G. E. Andrews & R. Roy, Ramanujan's Method in q-series Congruences

Anonymous, Bibliography on Partitions

A. O. L. Atkins & F. G. Garvan, Relations between the ranks and cranks of partitions

A. Berkovich & F. G. Garvan, On the Andrews-Stanley Refinement of Ramanujan's Partition Congruence Modulo 5

A. Berkovich & F. G. Garvan, On the Andrews-Stanley Refinement of Ramanujan's Partition Congruence Modulo 5 and Generalizations

B. C. Berndt, Ramanujan's congruences for the partition function modulo 5,7 and 11

B. C. Berndt and K. Ono, Ramanujan's Unpublished Manuscript On The Partition And Tau Functions With Proofs And Commentary

B. C. Berndt and K. Ono, Ramanujan's Unpublished Manuscript on the Partition and Tau Functions with Proofs and Commentary

H. Bottomley, Illustration of initial terms

H. Bottomley, Illustration of initial terms of A000009, A000041 and A047967

H. Bottomley, Partition and composition calculator

K. S. Brown, Additive Partitions of Numbers

K. S. Brown's Mathpages, Computing the Partitions of n

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions.

J. Davis & E. Perez, Computations Of The Partition Function, p(n)

N. J. Fine, Some New Results On Partitions

B. Forslund, Partitioning Integers

H. Fripertinger, Partitions of an Integer

GEO magazine, Zahlenspalterei

A. Hassen and T. J. Olsen, Playing With Partitions On The Computer

A. D. Healy, Partition Identities

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 61

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 74

E. Klarreich, Pieces of Numbers: A proof brings closure to a dramatic tale of partitions and primes, Science News, Week of Jun 18, 2005; Vol. 167, No. 25, p. 392.

J. Laurendi, Partitions of Integers

T. Lockette, Explore Magazine, "Path To Partitions"

Dr. Math, Partitioning the Integers

Dr. Math, Partitioning an Integer

M. MacMahon, Collected Papers of Ramanujan, Table for p(n);n=1 through 200

G. P. Michon, Table of partition function p(n) (n=0 through 4096)

G. P. Michon, Partition function

G. A. Miller, Number Of The Abelian Groups Of A Given Order

Hisanori Mishima, Factorization of Partition Numbers

D. J. Newman, A Simplified Proof Of The Partition Formula

K. Ono, Arithmetic of The Partition Function

K. Ono, Parity Of The Partition Function

K. Ono, Distribution of the partition function modulo m

T. J. Osler, Playing with Partitions on the Computer

I. Peterson, The Power Of Partitions

G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

M. Planat, Quantum 1/f Noise in Equilibrium: from Planck to Ramanujan

S. Plouffe, Partitions [Contains first 10000000 terms]

S. Plouffe, Partition numbers through n = 300000

S. Plouffe, Partitions numbers from 300000 to 450000

S. Plouffe, Partitions numbers from 450000 to 500000

O. E. Pol, How to build a shell model of partitions [From Omar E. Pol (info(AT)polprimos.com), Sep 06 2008]

O. E. Pol, A shell model of partitions (2D and 3D) [From Omar E. Pol (info(AT)polprimos.com), Sep 06 2008]

O. E. Pol, Illustration of initial terms (2D view) [From Omar E. Pol (info(AT)polprimos.com), Sep 06 2008]

O. E. Pol, Illustration of initial terms (3D view) [From Omar E. Pol (info(AT)polprimos.com), Sep 06 2008]

M. Presern, Some Results On Partitions

W. A. Pribitkin, The Ramanujan Journal 4(4) 2000, Revisiting Rademacher's Formula for the Partition Function p(n)

PYTHAGORAS, Ramanujan and The Partition Function(Text in Dutch)

S. Ramanujan, Some Properties Of p(n), The Number Of Partitions Of n

S. Ramanujan, Congruence Properties Of Partitions

S. Ramanujan, Congruence Properties Of Partitions

S. Ramanujan & G. H. Hardy, Une formule asymptotique pour le nombre de partitions de n

J. D. Rosenhouse, Partitions of Integers

J. D. Rosenhouse, Solutions to Problems

F. Ruskey, Generate Numerical Partitions

F. Ruskey, The first 284547 partition numbers (52MB compressed file)

M. Savic, The Partition Function and Ramanujan's 5k+4 Congruence

T. Sillke, Number of integer partitions

R. P. Stanley, A combinatorial miscellany

R. L. Weaver, The Ramanujan Journal 5(1) 2001, New Congruences for the Partition Function

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (1).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics(3)

West Sussex Grid for Learning, Multicultural Mathematics, Ramanujan's Partition of Numbers

Thomas Wieder, Comment on A000041

Wikipedia, Integer Partition

H. S. Wilf, Lectures on Integer Partitions

Wolfram Research, Generating functions of p(n)

D. J. Wright, Partitions

Index entries for "core" sequences

Index entries for related partition-counting sequences

Index entries for expansions of Product_{k >= 1} (1-x^k)^m

Index entries for sequences related to rooted trees

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 41

G.f.: Product_{k>0} 1/(1-x^k) = Sum_{k>= 0} x^k Product_{i = 1..k} 1/(1-x^i) = 1+Sum_{k>0} x^(k^2)/(Product_{i = 1..k} (1-x^i))^2.

a(n) - a(n-1) - a(n-2) + a(n-5) + a(n-7) - a(n-12) - a(n-15) + ... = 0, where the sum is over n-k and k is a generalized pentagonal number (A001318) <= n and the sign of the k-th term is (-1)^([(k+1)/2]). See A001318 for a good way to remember this!

a(n) = (1/n) * Sum_{k=0, 1, ..., n-1} sigma(n-k)*a(k), where sigma(k) is the sum of divisors of k (A000203).

a(n) ~ 1/(4*n*sqrt(3)) * e^(Pi * sqrt(2n/3)) as n -> infinity (Hardy and Ramanujan).

a(n) < exp( (2/3)^(1/2) pi sqrt(n) ) (Ayoub, p. 197).

G.f.: Product (1+x^m)^A001511(m); m=1..inf. - Vladeta Jovovic (vladeta(AT)eunet.rs), Mar 26 2004

a(n)=sum(i=0, n-1, P(i, n-i)), where P(x, y) is the number of partitions of x into at most y parts and P(0, y)=1. - Jon Perry (perry(AT)globalnet.co.uk), Jun 16 2003

G.f. : product(i=1, oo, product(j=0, oo, (1+x^((2i-1)*2^j))^(j+1))) - Jon Perry (perry(AT)globalnet.co.uk), Jun 06 2004

G.f. e^{Sum_{k>0} (x^k/(1-x^k)/k)}. - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Feb 08 2006

Euler transform of all 1's sequence (A000012). Weighout transform of A001511. - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Mar 15 2006

a(n) = A027187(n)+A027193(n) = A000701(n)+A046682(n). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Apr 22 2006

1/(1-x) + sum{ k=1,oo, x^k(k+1)/ prod(i=1,k, (1-x^i)^2)*(1-x^k+1) } (the pronic equivalent of the Durfee Square GF) [From Jon Perry (johnandruth(AT)jrperry.orangehome.co.uk), Aug 02 2008]

Convolved with A152537 gives A000079, powers of 2. [From Gary W. Adamson (qntmpkt(AT)haoo.com), Dec 06 2008]

with(combinat); A000041 := numbpart; [ seq(numbpart(i), i=0..50) ]; [Warning: Maple 10 and 11 give incorrect answers in some cases, for example combinat[numbpart](11269); is wrong.]

spec := [ B, {B=Set(Set(Z, card>=1))}, unlabeled ]; [seq(combstruct[count](spec, size=n), n=0..50)];

with(combstruct):ZL0:=[S, {S=Set(Cycle(Z, card>0))}, unlabeled]:seq(count(ZL0, size=n), n=0..45); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Sep 24 2007

G:={P=Set(Set(Atom, card>0))}:combstruct[gfsolve](G, labeled, x); seq(combstruct[count]([P, G, unlabeled], size=i), i=0..45); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 16 2007

Table[ PartitionsP[n], {n, 0, 45}]

(MAGMA) a:= func< n | NumberOfPartitions(n) >; [ a(n) : n in [0..10]];

(PARI) a(n)=if(n<0, 0, polcoeff(1/eta(x+x*O(x^n)), n))

(PARI) The Hardy-Ramanujan-Rademacher exact formula in PARI is as follows (this is no longer necessary since it is now built in to the numbpart command): - Ralf Stephan (ralf(AT)ark.in-berlin.de), Nov 30 2002

Psi(n, q) = local(a, b, c); a=sqrt(2/3)*Pi/q; b=n-1/24; c=sqrt(b); (sqrt(q)/(2*sqrt(2)*b*Pi))*(a*cosh(a*c)-(sinh(a*c)/c))

L(n, q) = if(q==1, 1, sum(h=1, q-1, if(gcd(h, q)>1, 0, cos((g(h, q)-2*h*n)*Pi/q))))

g(h, q) = if(q<3, 0, sum(k=1, q-1, k*(frac(h*k/q)-1/2)))

part(n) = round(sum(q=1, max(5, 0.24*sqrt(n)+2), L(n, q)*Psi(n, q)))

(PARI) a(n)=numbpart(n)

(PARI) a(n)=if(n<0, 0, polcoeff(sum(k=1, sqrtint(n), x^k^2/prod(i=1, k, 1-x^i, 1+x*O(x^n))^2, 1), n))

(PARI) f(n)= {local(v, i, k, s, t); v=vector(n, k, 0); v[n]=2; t=0; while(v[1]<n, i=2; while(v[i]==0, i++); v[i]--; s=sum(k=i, n, k*v[k]); while(i>1, i--; s+=i*(v[i]=(n-s)\i)); t++); t } (Thomas Baruchel (baruchel(AT)users(AT)sourceforge.net), Nov 07 2005)

(Mupad) combinat::partitions::count(i) $i=0..54 - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 16 2007

(Other) sage: [number_of_partitions(n)for n in xrange(0, 46)] # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 24 2009]

Cf. A000009, A008284, A008284, A000203, A001318.

For successive differences see A002865, A053445, A072380, A081094, A081095.

Antidiagonal sums of triangle A092905.

Cf. A132311.

Cf. A138151.

Cf. A135010, A138121. [From Omar E. Pol (info(AT)polprimos.com), Sep 06 2008]

A145006, A145007 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 28 2008]

A080995 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 05 2008]

A147843 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 15 2008]

Cf. A152537, A000079 [From Gary W. Adamson (qntmpkt(AT)haoo.com), Dec 06 2008]

a(n) = A035363(2n). [From Omar E. Pol (info(AT)polprimos.com), Nov 20 2009]

A168532 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 28 2009]

Sequence in context: A008641 A046054 A092885 this_sequence A084251 A024794 A091955

Adjacent sequences: A000038 A000039 A000040 this_sequence A000042 A000043 A000044

core,easy,nonn,nice,new

N. J. A. Sloane (njas(AT)research.att.com).

Links contributed by Patrick De Geest (pdg(AT)worldofnumbers.com), Oct 15 1999. Additional comments from Ola Veshta (olaveshta(AT)my-deja.com), Feb 28 2001 and from Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 07 2001.

Further links contributed by Lekraj Beedassy (blekraj(AT)yahoo.com), Spring 2003

0,2

Number of subsets of an n-set.

There are 2^(n-1) compositions (ordered partitions) of n - see for example Riordan. This is the unlabeled analogue of the preferential labelings sequence A000670.

This is also the number of weakly unimodal permutations of 1..n, that is, permutations with exactly one local maximum. E.g. a(5)=16: 12345, 12354, 12453, 12543, 13452, 13542, 14532 and 15432 and their reversals. - Jon Perry (perry(AT)globalnet.co.uk), Jul 27 2003. Proof: see next line! See also A087783.

Proof: n must appear somewhere and there are 2^(n-1) possible choices for the subset that precedes it. These must appear in increasing order and the rest must follow n in decreasing order. QED. - N. J. A. Sloane (njas(AT)research.att.com), Oct 26, 2003.

a(n+1) = smallest number that is not the sum of any number of (distinct) earlier terms.

Same as Pisot sequences E(1,2), L(1,2), P(1,2), T(1,2). See A008776 for definitions of Pisot sequences.

With initial 1 omitted, same as Pisot sequences E(2,4), L(2,4), P(2,4), T(2,4). - David W. Wilson.

Not the sum of two or more consecutive numbers. - Lekraj Beedassy (blekraj(AT)yahoo.com), May 14 2004

Least deficient or near-perfect numbers (i.e. n such that sigma(n)=A000203(n)=2n-1). - Lekraj Beedassy (blekraj(AT)yahoo.com), Jun 03 2004. Comment from Max Alekseyev (maxale(AT)gmail.com), Jan 26 2005: All the powers of 2 are least deficient numbers but it is not known if there exists a least deficient number not a power of 2.

The sum of the numbers in the n-th row of Pascal's triangle; the sum of the coefficients of x in the expansion of (x+1)^n.

The only hailstone sequence which doesn't rebound (except "on the ground"). - Alexandre Wajnberg (alexandre.wajnberg(AT)ulb.ac.be), Jan 29 2005

With p(n) = the number of integer partitions of n, p(i) = the number of parts of the i-th partition of n, d(i) = the number of different parts of the i-th partition of n, m(i,j) = multiplicity of the j-th part of the i-th partition of n, sum_{i=1}^{p(n)} = sum over i and prod_{j=1}^{d(i)} = product over j one has: a(n)=sum_{i=1}^{p(n)} p(i)!/(prod_{j=1}^{d(i)} m(i,j)!) - Thomas Wieder (wieder.thomas(AT)t-online.de), May 18 2005

a(n+1) = a(n) XOR 3a(n) where XOR is binary exclusive OR operator. - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jun 19 2005

The number of binary relations on an n-element set that are both symmetric and antisymmetric. Also the number of binary relations on an n-element set that are symmetric, antisymmetric and transitive.

An autocopy sequence: its first differences are the sequence itself. - Alexandre Wajnberg & Eric Angelini (alexandre.wajnberg(AT)ulb.ac.be), Sep 07 2005

a(n) = largest number with shortest addition chain involving n additions. - David W. Wilson (davidwwilson(AT)comcast.net), Apr 23 2006

Beginning with a(1) = 0, numbers not equal to the sum of previous distinct natural numbers. - Giovanni Teofilatto (g.teofilatto(AT)tiscalinet.it), Aug 06 2006

Smallest order of exactly p(n) nonisomorphic Abelian groups, where p(n)=A000041(n). {First occurrence of p(n) in A000688(n)} - Lekraj Beedassy (blekraj(AT)yahoo.com), Jul 11 2006

For n>=1, a(n) is equal to the number of functions f:{1,2...,n}->{1,2} such that for a fixed x in {1,2,...,n} and a fixed y in {1,2]} we have f(x)<>y. - Aleksandar M. Janjic and Milan R. Janjic (agnus(AT)blic.net), Mar 27 2007

Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which x = y. - Ross La Haye (rlahaye(AT)new.rr.com), Jan 09 2008 Ross La Haye

a(n)= the number of different ways to run up a staircase with n steps, taking steps of sizes 1,2,3,... and r (r<=n), where the order IS important and there is no restriction on the number or the size of each step taken. - Mohammad K. Azarian (azarian(AT)evansville.edu), May 21 2008

a(n)=number of permutations on [n+1] such that every initial segment is an interval of integers. Example: a(3) counts 1234, 2134, 2314, 2341, 3214, 3241, 3421, 4321. The map "p -> ascents of p" is a bijection from these permutations to subsets of [n]. An ascent of a permutation p is a position i such that p(i) < p(i+1). The permutations shown map to 123, 23, 13, 12, 3, 2, 1 and the empty set respectively. - David Callan (callan(AT)stat.wisc.edu), Jul 25 2008

2^(n-1) is the largest number having n divisors (in the sense of A077569); A005179(n) is the smallest. [From T. D. Noe (noe(AT)sspectra.com), Sep 02 2008]

Contribution from Bill R McEachen (bmceachen(AT)centralsan.org), Oct 29 2008: (Start)

a(n) appears to match the number of divisors of the modified primorials (excluding 2,3and 5)

Very limited range examined, PARI example shown (End)

Successive k such that EulerPhi[k]/k = 1/2. [From Artur Jasinski (grafix(AT)csl.pl), Nov 07 2008]

A classical transform consists (for general a(n)) in swapping a(2n) and a(2n+1);examples for Jacobsthal A001045 and successive differences: A092808,A094359,A140505. a(n)=A000079 leads to 2,1,8,4,32,16,=A135520. [From Paul Curtz (bpcrtz(AT)free.fr), Jan 05 2009]

This is also the (L)-sieve transform of {2,4,6,8,...,2n,...}=A005843. (See A152079 for the definition of the (L)-sieve transform.) [From John W. Layman (layman(AT)math.vt.edu), Jan 23 2009]

a(n) = a(n-1)-th even natural numbers (A005843) for n > 1. [From Jaroslav Krizek (jaroslav.krizek(AT)atlas.cz), Apr 25 2009]

For n >= 0, a(n) is the number of leaves in a complete binary tree of height n. For n > 0, a(n) is the number of nodes in an n-cube. [From Kailasam Viswanathan Iyer (kvi(AT)nitt.edu), May 04 2009]

Permutations of n+1 elements where no element is more than one position left of its original place. For example, there are 4 such permutations of three elements: 123, 132, 213, and 312. The 8 such permutations of four elements are 1234, 1243, 1324, 1423, 2134, 2143, 3124, and 4123. [From Joerg Arndt (arndt(AT)jjj.de), June 24 2009]

Catalan transform of A099087. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jun 29 2009]

a(n) written in base 2: 1,10,100,1000,10000,..., i.e. (n+1)times 1, n times 0 (A011557(n)). [From Jaroslav Krizek (jaroslav.krizek(AT)atlas.cz), Aug 02 2009]

Except for the first term, number n such that if A=(7/8)*n^4; B=(7/16)*n^4; C=(17/16)*n^4; D=(5/4)*n^4; then A^3+B^3+C^3=D^3 [From Vincenzo Librandi (vincenzo.librandi(AT)tin.it), Sep 08 2009]

Or, phi(n) is equal to the number of perfect partitions of n. [From Juri-Stepan Gerasimov (2stepan(AT)rambler.ru), Oct 10 2009]

These are the 2-smooth numbers, positive integers with no prime factors greater than 2. [From Michael Porter (michael_b_porter(AT)yahoo.com), Oct 04 2009]

A064614(a(n)) = A000244(n) and A064614(m)<A000244(n) for m<a(n). [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Feb 08 2010]

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 1016.

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

R. Ondrejka, Exact values of 2^n, n=1(1)4000, Math. Comp., 23 (1969), 456.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.

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

Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.

N. J. A. Sloane, Table of n, 2^n for n = 0..1000

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].

Henry Bottomley, Illustration of initial terms

D. Butler, Powers of Two up to 2^222

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 18

Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors ..., J. Integer Seqs., Vol. 6, 2003.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 6

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 68

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 72

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 267

Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

G. Villemin's Almanac of Numbers, Puissances de 2

Sage Weil, 1058 powers of two

Eric Weisstein's World of Mathematics, Fractional Part

Eric Weisstein's World of Mathematics, PowerFractional Parts

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (1).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (3).

Eric Weisstein's World of Mathematics, Hypercube

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics(4)

Eric Weisstein's World of Mathematics, Hailstone Number

Eric Weisstein's World of Mathematics, Erf

Eric Weisstein's World of Mathematics, Abundance

Wikipedia, Almost perfect number

Index entries for "core" sequences

Index entries for related partition-counting sequences

Index entries for sequences related to linear recurrences with constant coefficients

a(n) = 2^n; a(n) = 2*a(n-1). G.f.: 1/(1-2x), e.g.f.: exp(2x).

2^n = Sum_{k=0..n} binomial(n, k).

a(n) is the number of occurrences of n in A000523. a(n) = A001045(n) + A001045(n+1). a(n) = 1 + sum_{k=0..(n-1)} a(k). The Hankel transform of this sequence gives A000007 = [1, 0, 0, 0, 0, 0, ...]. - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Feb 25 2004

n such that phi(n)=n/2, for n>1, where phi is the Euler's totient (A000010). - Lekraj Beedassy (lbeedassy(AT)hotmail.com), Sep 07 2004

This sequence can be generated by the following formula: a(n) = a(n-1) + 2*a(n-2) when n > 2; a[1] = 1, a[2] = 2 - Alex Vinokur (alexvn(AT)barak-online.net), Oct 24 2004

a(n) = StirlingS2(n+1,2) + 1 - Ross La Haye (rlahaye(AT)new.rr.com), Jan 09 2008 Ross La Haye

This sequence can be generated by a(n+2)=6a(n+1)-8a(n), n=1,2,3,... with a(1)=1, a(2)=2. - Yosu Yurramendi (yosu.yurramendi(AT)ehu.es), Aug 06 2008

a(n)=ka(n-1)+(4-2k)a(n-2) for any integer k and n>1, with a(0)=1, a(1)=2. [From Jaume Oliver Lafont (joliverlafont(AT)gmail.com), Dec 05 2008]

Equals the partition numbers A000041 convolved with A152537. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 06 2008]

Formula from Thomas Wieder (wieder.thomas(AT)t-online.de), Feb 25 2009:

a(n) = sum_{l_1=0}^{n+1} sum_{l_2=0}^{n}...sum_{l_i=0}^{n-i}...sum_{l_n=0}^{1}

delta(l_1,l_2,...,l_i,...,l_n)

where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i <= l_(i+1) and l_(i+1) <> 0

and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise.

G.f.: exp(x)*cosh(x) . [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 05 2009]

a(0)=1, a(1)=2; a(n)=a(n-1)^2/a(n-2), n>=2 [From Jaume Oliver Lafont (joliverlafont(AT)gmail.com), Sep 22 2009]

A000010(a(n))=A002033(a(n)). [From Juri-Stepan Gerasimov (2stepan(AT)rambler.ru), Oct 10 2009]

There are 2^3 = 8 subsets of a 3-element set {1,2,3}, namely { -, 1, 2, 3, 12, 13, 23, 123 }.

For n=2, A=14, B=7, C=17, D=20, and 14^3+7^3+17^3=20^3 [From Vincenzo Librandi (vincenzo.librandi(AT)tin.it), Jun 25 2009]

A000079 := n->2^n; [ seq(2^n, n=0..50) ];

with(combstruct); SeqSetU := [S, {S=Sequence(U), U=Set(Z, card >= 1)}, unlabeled]; seq(count(SeqSetU, size=j), j=1..12);

with(combinat):seq(stirling2(n, 2)+1, n=1..34); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Oct 04 2007

seq(binomial(n+0, 0)*2^n, n=0..33); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jul 08 2008

with(finance):seq(futurevalue(2, 1, n), n=-1..31); # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 24 2009]

restart: G(x):=exp(x)*cosh(x): f[0]:=G(x): for n from 1 to 54 do f[n]:=diff(f[n-1], x) od: x:=0: seq(f[n], n=1..34 ); # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 05 2009]

Array[ 2^#&, 50, 0 ]

a = {}; Do[If[EulerPhi[x]/x == 1/2, AppendTo[a, x]], {x, 1, 2048}]; a [From Artur Jasinski (grafix(AT)csl.pl), Nov 07 2008]

(PARI) a(n)=if(n<0, 0, 2^n)

(PARI) { unimodal(n)=local(x, d, um, umc); umc=0; for (c=0, n!-1, x=numtoperm(n, c); d=0; um=1; for (j=2, n, if (x[j]<x[j-1], d=1); if (x[j]>x[j-1] && d==1, um=0); if (um==0, break)); if (um==1, print(x)); umc+=um); umc }

sage: [lucas_number2(n, 4, 4) for n in xrange(-1, 27)] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jul 08 2008

(PARI) a=7*11*13*17*19*23*29*31*37*41*43*47*53*59*61 %32 = 3909612711980232366109 ? b=numdiv(a) %33 = 32768 [From Bill R McEachen (bmceachen(AT)centralsan.org), Oct 29 2008]

(PARI) { x=1; for (n=0, 1000, write("b000079.txt", n, " ", x); x+=x); } [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), Apr 26 2009]

a(n) = 2*A001045(n)+A078008(n) = 3*A001045(n)+(-1)^n. - Paul Barry (pbarry(AT)wit.ie), Feb 20 2003

Cf. A000225.

A000079 is the Hankel transform (see A001906 for the definition) of A000984, A002426, A026375, A026387, A026569, A026585, A026671 and A032351 - John W. Layman (layman(AT)math.vt.edu), Jul 31 2000

Euler transform of A001037.

Complement of A057716.

a(n) = A118654(n, 2).

a(n) = A140740(n+1, 1).

Cf. A038754, A133464, A140730, A037124.

Cf. A001787, A001788, A001789, A003472, A054849, A002409, A054851, A140325, A140354.

Cf. A000041, A152537 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 06 2008]

Equals row sums of the partition convolution triangle, A152538 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 10 2008]

Cf. A000010, A002033.[From Juri-Stepan Gerasimov (2stepan(AT)rambler.ru), Oct 10 2009]

Sequence in context: A166444 A084633 A122803 this_sequence A120617 A171449 A050732

Adjacent sequences: A000076 A000077 A000078 this_sequence A000080 A000081 A000082

core,easy,nice,nonn,new