cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 11-20 of 54 results. Next

A000108 Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

These were formerly sometimes called Segner numbers.
A very large number of combinatorial interpretations are known - see references, esp. R. P. Stanley, "Catalan Numbers", Cambridge University Press, 2015. This is probably the longest entry in the OEIS, and rightly so.
The solution to Schröder's first problem: number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); 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 that never go below the x-axis (Dyck paths) is C(n). [Chung-Feller]
Number of noncrossing partitions of the n-set. For example, of the 15 set partitions of the 4-set, only [{13},{24}] is crossing, so there are a(4)=14 noncrossing partitions of 4 elements. - Joerg Arndt, Jul 11 2011
Noncrossing partitions are partitions of genus 0. - Robert Coquereaux, Feb 13 2024
a(n-1) is the number of ways of expressing an n-cycle (123...n) in the symmetric group S_n as a product of n-1 transpositions (u_1,v_1)*(u_2,v_2)*...*(u_{n-1},v_{n-1}) where u_iA000272. - Joerg Arndt and Greg Stevenson, Jul 11 2011
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. - Wolfdieter Lang, Aug 07 2007
As shown in the paper from Beineke and Pippert (1971), a(n-2)=D(n) is the number of labeled dissections of a disk, related to the number R(n)=A001761(n-2) of labeled planar 2-trees having n vertices and rooted at a given exterior edge, by the formula D(n)=R(n)/(n-2)!. - M. F. Hasler, Feb 22 2012
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
Number of ways of joining 2n points on a circle to form n nonintersecting chords. (If no such restriction imposed, then the number of 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, 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. - Philippe Deléham, Mar 04 2004
a(n) equals the 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, Apr 23 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], ... - Donald D. Cross (cosinekitty(AT)hotmail.com), Feb 04 2005
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. - Franklin T. Adams-Watters, 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, Mar 06 2006
The answer is yes. Using the formula C_n = binomial(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. - Franklin T. Adams-Watters, Apr 14 2006
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, 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. - Abdullahi Umar, 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)). - 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. - Mats Granvik, Gary W. Adamson and Roger L. Bagula, Sep 09 2008, Sep 12 2008
Limit_{n->oo} a(n)/a(n-1) = 4. - Francesco Antoni (francesco_antoni(AT)yahoo.com), Nov 24 2008
Starting with offset 1 = row sums of triangle A154559. - Gary W. Adamson, Jan 11 2009
C(n) is the degree of the Grassmannian 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 Grassmannian 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. - Benji Fisher (benji(AT)FisherFam.org), Mar 05 2009
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. - Gary W. Adamson, May 01 2009
Convolved with A032443: (1, 3, 11, 42, 163, ...) = powers of 4, A000302: (1, 4, 16, ...). - Gary W. Adamson, May 15 2009
Sum_{k>=1} C(k-1)/2^(2k-1) = 1. The k-th term in the summation is the probability that a random walk on the integers (beginning at the origin) will arrive at positive one (for the first time) in exactly (2k-1) steps. - Geoffrey Critzer, Sep 12 2009
C(p+q)-C(p)*C(q) = Sum_{i=0..p-1, j=0..q-1} C(i)*C(j)*C(p+q-i-j-1). - Groux Roland, Nov 13 2009
Leonhard Euler used the formula C(n) = Product_{i=3..n} (4*i-10)/(i-1) in his 'Betrachtungen, auf wie vielerley Arten ein gegebenes polygonum durch Diagonallinien in triangula zerschnitten werden könne' and computes by recursion C(n+2) for n = 1..8. (Berlin, 4th September 1751, in a letter to Goldbach.) - Peter Luschny, Mar 13 2010
Let A179277 = A(x). Then C(x) is satisfied by A(x)/A(x^2). - Gary W. Adamson, Jul 07 2010
a(n) is also the number of quivers in the mutation class of type B_n or of type C_n. - Christian Stump, Nov 02 2010
From Matthew Vandermast, Nov 22 2010: (Start)
Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1) equals the number of ways to choose 0 or more balls of each color while satisfying the following conditions: 1. No two colors are chosen the same positive number of times. 2. For any two colors (c, d) that are chosen at least once, color c is chosen more times than color d iff color c appears more times in the original set than color d.
If the second requirement is lifted, the number of acceptable ways equals A000110(n+1). See related comments for A016098, A085082. (End)
Deutsch and Sagan prove the Catalan number C_n is odd if and only if n = 2^a - 1 for some nonnegative integer a. Lin proves for every odd Catalan number C_n, we have C_n == 1 (mod 4). - Jonathan Vos Post, Dec 09 2010
a(n) is the number of functions f:{1,2,...,n}->{1,2,...,n} such that f(1)=1 and for all n >= 1 f(n+1) <= f(n)+1. For a nice bijection between this set of functions and the set of length 2n Dyck words, see page 333 of the Fxtbook (see link below). - Geoffrey Critzer, Dec 16 2010
Postnikov (2005) defines "generalized Catalan numbers" associated with buildings (e.g., Catalan numbers of Type B, see A000984). - N. J. A. Sloane, Dec 10 2011
Number of permutations in S(n) for which length equals depth. - Bridget Tenner, Feb 22 2012
a(n) is also the number of standard Young tableau of shape (n,n). - Thotsaporn Thanatipanonda, Feb 25 2012
a(n) is the number of binary sequences of length 2n+1 in which the number of ones first exceed the number of zeros at entry 2n+1. See the example below in the example section. - Dennis P. Walsh, Apr 11 2012
Number of binary necklaces of length 2*n+1 containing n 1's (or, by symmetry, 0's). All these are Lyndon words and their representatives (as cyclic maxima) are the binary Dyck words. - Joerg Arndt, Nov 12 2012
Number of sequences consisting of n 'x' letters and n 'y' letters such that (counting from the left) the 'x' count >= 'y' count. For example, for n=3 we have xxxyyy, xxyxyy, xxyyxy, xyxxyy and xyxyxy. - Jon Perry, Nov 16 2012
a(n) is the number of Motzkin paths of length n-1 in which the (1,0)-steps come in 2 colors. Example: a(4)=14 because, denoting U=(1,1), H=(1,0), and D=(1,-1), we have 8 paths of shape HHH, 2 paths of shape UHD, 2 paths of shape UDH, and 2 paths of shape HUD. - José Luis Ramírez Ramírez, Jan 16 2013
If p is an odd prime, then (-1)^((p-1)/2)*a((p-1)/2) mod p = 2. - Gary Detlefs, Feb 20 2013
Conjecture: For any positive integer n, the polynomial Sum_{k=0..n} a(k)*x^k is irreducible over the field of rational numbers. - Zhi-Wei Sun, Mar 23 2013
a(n) is the size of the Jones monoid on 2n points (cf. A225798). - James Mitchell, Jul 28 2013
For 0 < p < 1, define f(p) = Sum_{n>=0} a(n)*(p*(1-p))^n, then f(p) = min{1/p, 1/(1-p)}, so f(p) reaches its maximum value 2 at p = 0.5, and p*f(p) is constant 1 for 0.5 <= p < 1. - Bob Selcoe, Nov 16 2013 [Corrected by Jianing Song, May 21 2021]
No a(n) has the form x^m with m > 1 and x > 1. - Zhi-Wei Sun, Dec 02 2013
From Alexander Adamchuk, Dec 27 2013: (Start)
Prime p divides a((p+1)/2) for p > 3. See A120303(n) = Largest prime factor of Catalan number.
Reciprocal Catalan Constant C = 1 + 4*sqrt(3)*Pi/27 = 1.80613.. = A121839.
Log(Phi) = (125*C - 55) / (24*sqrt(5)), where C = Sum_{k>=1} (-1)^(k+1)*1/a(k). See A002390 = Decimal expansion of natural logarithm of golden ratio.
3-d analog of the Catalan numbers: (3n)!/(n!(n+1)!(n+2)!) = A161581(n) = A006480(n) / ((n+1)^2*(n+2)), where A006480(n) = (3n)!/(n!)^3 De Bruijn's S(3,n). (End)
For a relation to the inviscid Burgers's, or Hopf, equation, see A001764. - Tom Copeland, Feb 15 2014
From Fung Lam, May 01 2014: (Start)
One class of generalized Catalan numbers can be defined by g.f. A(x) = (1-sqrt(1-q*4*x*(1-(q-1)*x)))/(2*q*x) with nonzero parameter q. Recurrence: (n+3)*a(n+2) -2*q*(2*n+3)*a(n+1) +4*q*(q-1)*n*a(n) = 0 with a(0)=1, a(1)=1.
Asymptotic approximation for q >= 1: a(n) ~ (2*q+2*sqrt(q))^n*sqrt(2*q*(1+sqrt(q))) /sqrt(4*q^2*Pi*n^3).
For q <= -1, the g.f. defines signed sequences with asymptotic approximation: a(n) ~ Re(sqrt(2*q*(1+sqrt(q)))*(2*q+2*sqrt(q))^n) / sqrt(q^2*Pi*n^3), where Re denotes the real part. Due to Stokes' phenomena, accuracy of the asymptotic approximation deteriorates at/near certain values of n.
Special cases are A000108 (q=1), A068764 to A068772 (q=2 to 10), A240880 (q=-3).
(End)
Number of sequences [s(0), s(1), ..., s(n)] with s(n)=0, Sum_{j=0..n} s(j) = n, and Sum_{j=0..k} s(j)-1 >= 0 for k < n-1 (and necessarily Sum_{j=0..n-1} s(j)-1 = 0). These are the branching sequences of the (ordered) trees with n non-root nodes, see example. - Joerg Arndt, Jun 30 2014
Number of stack-sortable permutations of [n], these are the 231-avoiding permutations; see the Bousquet-Mélou reference. - Joerg Arndt, Jul 01 2014
a(n) is the number of increasing strict binary trees with 2n-1 nodes that avoid 132. For more information about increasing strict binary trees with an associated permutation, see A245894. - Manda Riehl, Aug 07 2014
In a one-dimensional medium with elastic scattering (zig-zag walk), first recurrence after 2n+1 scattering events has the probability C(n)/2^(2n+1). - Joachim Wuttke, Sep 11 2014
The o.g.f. C(x) = (1 - sqrt(1-4x))/2, for the Catalan numbers, with comp. inverse Cinv(x) = x*(1-x) and the functions P(x) = x / (1 + t*x) and its inverse Pinv(x,t) = -P(-x,t) = x / (1 - t*x) form a group under composition that generates or interpolates among many classic arrays, such as the Motzkin (Riordan, A005043), Fibonacci (A000045), and Fine (A000957) numbers and polynomials (A030528), and enumerating arrays for Motzkin, Dyck, and Łukasiewicz lattice paths and different types of trees and non-crossing partitions (A091867, connected to sums of the refined Narayana numbers A134264). - Tom Copeland, Nov 04 2014
Conjecture: All the rational numbers Sum_{i=j..k} 1/a(i) with 0 < min{2,k} <= j <= k have pairwise distinct fractional parts. - Zhi-Wei Sun, Sep 24 2015
The Catalan number series A000108(n+3), offset n=0, gives Hankel transform revealing the square pyramidal numbers starting at 5, A000330(n+2), offset n=0 (empirical observation). - Tony Foster III, Sep 05 2016
Hankel transforms of the Catalan numbers with the first 2, 4, and 5 terms omitted give A001477, A006858, and A091962, respectively, without the first 2 terms in all cases. More generally, the Hankel transform of the Catalan numbers with the first k terms omitted is H_k(n) = Product_{j=1..k-1} Product_{i=1..j} (2*n+j+i)/(j+i) [see Cigler (2011), Eq. (1.14) and references therein]; together they form the array A078920/A123352/A368025. - Andrey Zabolotskiy, Oct 13 2016
Presumably this satisfies Benford's law, although the results in Hürlimann (2009) do not make this clear. See S. J. Miller, ed., 2015, p. 5. - N. J. A. Sloane, Feb 09 2017
Coefficients of the generating series associated to the Magmatic and Dendriform operadic algebras. Cf. p. 422 and 435 of the Loday et al. paper. - Tom Copeland, Jul 08 2018
Let M_n be the n X n matrix with M_n(i,j) = binomial(i+j-1,2j-2); then det(M_n) = a(n). - Tony Foster III, Aug 30 2018
Also the number of Catalan trees, or planted plane trees (Bona, 2015, p. 299, Theorem 4.6.3). - N. J. A. Sloane, Dec 25 2018
Number of coalescent histories for a caterpillar species tree and a matching caterpillar gene tree with n+1 leaves (Rosenberg 2007, Corollary 3.5). - Noah A Rosenberg, Jan 28 2019
Finding solutions of eps*x^2+x-1 = 0 for eps small, that is, writing x = Sum_{n>=0} x_{n}*eps^n and expanding, one finds x = 1 - eps + 2*eps^2 - 5*eps^3 + 14*eps^3 - 42*eps^4 + ... with x_{n} = (-1)^n*C(n). Further, letting x = 1/y and expanding y about 0 to find large roots, that is, y = Sum_{n>=1} y_{n}*eps^n, one finds y = 0 - eps + eps^2 - 2*eps^3 + 5*eps^3 - ... with y_{n} = (-1)^n*C(n-1). - Derek Orr, Mar 15 2019
Permutations of length n that produce a bipartite permutation graph of order n [see Knuth (1973), Busch (2006), Golumbic and Trenk (2004)]. - Elise Anderson, R. M. Argus, Caitlin Owens, Tessa Stevens, Jun 27 2019
For n > 0, a random selection of n + 1 objects (the minimum number ensuring one pair by the pigeonhole principle) from n distinct pairs of indistinguishable objects contains only one pair with probability 2^(n-1)/a(n) = b(n-1)/A098597(n), where b is the 0-offset sequence with the terms of A120777 repeated (1,1,4,4,8,8,64,64,128,128,...). E.g., randomly selecting 6 socks from 5 pairs that are black, blue, brown, green, and white, results in only one pair of the same color with probability 2^(5-1)/a(5) = 16/42 = 8/21 = b(4)/A098597(5). - Rick L. Shepherd, Sep 02 2019
See Haran & Tabachnikov link for a video discussing Conway-Coxeter friezes. The Conway-Coxeter friezes with n nontrivial rows are generated by the counts of triangles at each vertex in the triangulations of regular n-gons, of which there are a(n). - Charles R Greathouse IV, Sep 28 2019
For connections to knot theory and scattering amplitudes from Feynman diagrams, see Broadhurst and Kreimer, and Todorov. Eqn. 6.12 on p. 130 of Bessis et al. becomes, after scaling, -12g * r_0(-y/(12g)) = (1-sqrt(1-4y))/2, the o.g.f. (expressed as a Taylor series in Eqn. 7.22 in 12gx) given for the Catalan numbers in Copeland's (Sep 30 2011) formula below. (See also Mizera p. 34, Balduf pp. 79-80, Keitel and Bartosch.) - Tom Copeland, Nov 17 2019
Number of permutations in S_n whose principal order ideals in the weak order are modular lattices. - Bridget Tenner, Jan 16 2020
Number of permutations in S_n whose principal order ideals in the weak order are distributive lattices. - Bridget Tenner, Jan 16 2020
Legendre gives the following formula for computing the square root modulo 2^m:
sqrt(1 + 8*a) mod 2^m = (1 + 4*a*Sum_{i=0..m-4} C(i)*(-2*a)^i) mod 2^m
as cited by L. D. Dickson, History of the Theory of Numbers, Vol. 1, 207-208. - Peter Schorn, Feb 11 2020
a(n) is the number of length n permutations sorted to the identity by a consecutive-132-avoiding stack followed by a classical-21-avoiding stack. - Kai Zheng, Aug 28 2020
Number of non-crossing partitions of a 2*n-set with n blocks of size 2. Also number of non-crossing partitions of a 2*n-set with n+1 blocks of size at most 3, and without cyclical adjacencies. The two partitions can be mapped by rotated Kreweras bijection. - Yuchun Ji, Jan 18 2021
Named by Riordan (1968, and earlier in Mathematical Reviews, 1948 and 1964) after the French and Belgian mathematician Eugène Charles Catalan (1814-1894) (see Pak, 2014). - Amiram Eldar, Apr 15 2021
For n >= 1, a(n-1) is the number of interpretations of x^n is an algebra where power-associativity is not assumed. For example, for n = 4 there are a(3) = 5 interpretations: x(x(xx)), x((xx)x), (xx)(xx), (x(xx))x, ((xx)x)x. See the link "Non-associate powers and a functional equation" from I. M. H. Etherington and the page "Nonassociative Product" from Eric Weisstein's World of Mathematics for detailed information. See also A001190 for the case where multiplication is commutative. - Jianing Song, Apr 29 2022
Number of states in the transition diagram associated with the Laplacian system over the complete graph K_N, corresponding to ordered initial conditions x_1 < x_2 < ... < x_N. - Andrea Arlette España, Nov 06 2022
a(n) is the number of 132-avoiding stabilized-interval-free permutations of size n+1. - Juan B. Gil, Jun 22 2023
Number of rooted polyominoes composed of n triangular cells of the hyperbolic regular tiling with Schläfli symbol {3,oo}. A rooted polyomino has one external edge identified, and chiral pairs are counted as two. A stereographic projection of the {3,oo} tiling on the Poincaré disk can be obtained via the Christensson link. - Robert A. Russell, Jan 27 2024
a(n) is the number of extremely lucky Stirling permutations of order n; i.e., the number of Stirling permutations of order n that have exactly n lucky cars. (see Colmenarejo et al. reference) - Bridget Tenner, Apr 16 2024

Examples

			From _Joerg Arndt_ and Greg Stevenson, Jul 11 2011: (Start)
The following products of 3 transpositions lead to a 4-cycle in S_4:
(1,2)*(1,3)*(1,4);
(1,2)*(1,4)*(3,4);
(1,3)*(1,4)*(2,3);
(1,4)*(2,3)*(2,4);
(1,4)*(2,4)*(3,4). (End)
G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 + 429*x^7 + ...
For n=3, a(3)=5 since there are exactly 5 binary sequences of length 7 in which the number of ones first exceed the number of zeros at entry 7, namely, 0001111, 0010111, 0011011, 0100111, and 0101011. - _Dennis P. Walsh_, Apr 11 2012
From _Joerg Arndt_, Jun 30 2014: (Start)
The a(4) = 14 branching sequences of the (ordered) trees with 4 non-root nodes are (dots denote zeros):
01:  [ 1 1 1 1 . ]
02:  [ 1 1 2 . . ]
03:  [ 1 2 . 1 . ]
04:  [ 1 2 1 . . ]
05:  [ 1 3 . . . ]
06:  [ 2 . 1 1 . ]
07:  [ 2 . 2 . . ]
08:  [ 2 1 . 1 . ]
09:  [ 2 1 1 . . ]
10:  [ 2 2 . . . ]
11:  [ 3 . . 1 . ]
12:  [ 3 . 1 . . ]
13:  [ 3 1 . . . ]
14:  [ 4 . . . . ]
(End)

References

  • The large number of references and links demonstrates the ubiquity of the Catalan numbers.
  • 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.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, many references.
  • 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, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see pp. 183, 196, etc.).
  • Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.
  • E. Deutsch, Dyck path enumeration, Discrete Math., 204, 167-202, 1999.
  • E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bulletin of the Institute of Combinatorics and its Applications, 31, 31-38, 2001.
  • 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. 1, 207-208.
  • Tomislav Doslic and Darko Veljan, Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182-2212. MR2404544 (2009j:05019)
  • S. Dulucq and J.-G. Penaud, Cordes, arbres et permutations. Discrete Math. 117 (1993), no. 1-3, 89-105.
  • A. Errera, Analysis situs - Un problème d'énumération, Mémoires Acad. Bruxelles, Classe des sciences, Série 2, Vol. XI, Fasc. 6, No. 1421 (1931), 26 pp.
  • Ehrenfeucht, Andrzej; Haemer, Jeffrey; Haussler, David. Quasimonotonic sequences: theory, algorithms and applications. SIAM J. Algebraic Discrete Methods 8 (1987), no. 3, 410-429. MR0897739 (88h:06026)
  • I. M. H. Etherington, Non-associate powers and a functional equation. The Mathematical Gazette, 21 (1937): 36-39; addendum 21 (1937), 153.
  • I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
  • I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
  • K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc., 10 (1997), 139-167.
  • Susanna Fishel, Myrto Kallipoliti and Eleni Tzanaki, Facets of the Generalized Cluster Complex and Regions in the Extended Catalan Arrangement of Type A, The electronic Journal of Combinatorics 20(4) (2013), #P7.
  • 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.
  • Fürlinger, J.; Hofbauer, J., q-Catalan numbers. J. Combin. Theory Ser. A 40 (1985), no. 2, 248-264. MR0814413 (87e:05017)
  • 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).
  • M. C. Golumbic and A. N. Trenk, Tolerance graphs, Vol. 89, Cambridge University Press, 2004, pp. 32.
  • S Goodenough, C Lavault, Overview on Heisenberg—Weyl Algebra and Subsets of Riordan Subgroups, The Electronic Journal of Combinatorics, 22(4) (2015), #P4.16,
  • H. W. Gould, Research bibliography of two special number sequences, Mathematica Monongaliae, Vol. 12, 1971.
  • D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableau de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986.
  • M. Griffiths, The Backbone of Pascal's Triangle, United Kingdom Mathematics Trust (2008), 53-63 and 85-93.
  • 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.
  • R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967.
  • R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis. Amer. Math. Monthly 80 (1973), 868-876.
  • Peter Hajnal and Gabor V. Nagy, A bijective proof of Shapiro's Catalan convolution, Elect. J. Combin., 21 (2014), #P2.42.
  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.23).
  • F. Harary, G. Prins, and W. T. Tutte, The number of plane trees. Indag. Math. 26, 319-327, 1964.
  • J. Harris, Algebraic Geometry: A First Course (GTM 133), Springer-Verlag, 1992, pages 245-247.
  • S. Heubach, N. Y. Li and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math., 308 (2008), 5954-5964.
  • Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
  • Higgins, Peter M. Combinatorial results for semigroups of order-preserving mappings. Math. Proc. Camb. Phil. Soc. (1993), 113: 281-296.
  • B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 513, Eq. (7.282).
  • F. Hurtado, M. Noy, Ears of triangulations and Catalan numbers, Discrete Mathematics, Volume 149, Issues 1-3, Feb 22 1996, Pages 319-324.
  • M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5.
  • R. H. Jeurissen, Raney and Catalan, Discrete Math., 308 (2008), 6298-6307.
  • M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 36.
  • Kim, Ki Hang; Rogers, Douglas G.; Roush, Fred W. Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013)
  • Klarner, D. A. A Correspondence Between Sets of Trees. Indag. Math. 31, 292-296, 1969.
  • M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.
  • D. E. Knuth, The Art of Computer Programming, 2nd Edition, Vol. 1, Addison-Wesley, 1973, pp. 238.
  • D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.6 (p. 450).
  • 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.
  • E. Krasko, A. Omelchenko, Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.
  • C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., 14 (1922), 55-62, 122-138 and 143-146.
  • P. Lafar and C. T. Long, A combinatorial problem, Amer. Math. Mnthly, 69 (1962), 876-883.
  • Laradji, A. and Umar, A. On certain finite semigroups of order-decreasing transformations I, Semigroup Forum 69 (2004), 184-200.
  • 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.
  • C. L. Mallows, R. J. Vanderbei, Which Young Tableaux Can Represent an Outer Sum?, Journal of Integer Sequences, Vol. 18, 2015, #15.9.1.
  • Toufik Mansour, Matthias Schork, and Mark Shattuck, Catalan numbers and pattern restricted set partitions. Discrete Math. 312(2012), no. 20, 2979-2991. MR2956089
  • Toufik Mansour and Simone Severini, Enumeration of (k,2)-noncrossing partitions, Discrete Math., 308 (2008), 4570-4577.
  • M. E. Mays and Jerzy Wojciechowski, A determinant property of Catalan numbers. Discrete Math. 211, No. 1-3, 125-133 (2000). Zbl 0945.05037
  • 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.
  • Miller, Steven J., ed. Benford's Law: Theory and Applications. Princeton University Press, 2015.
  • David Molnar, "Wiggly Games and Burnside's Lemma", Chapter 8, The Mathematics of Various Entertaining Subjects: Volume 3 (2019), Jennifer Beineke & Jason Rosenhouse, eds. Princeton University Press, Princeton and Oxford, p. 102.
  • 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).
  • Papoulis, Athanasios. "A new method of inversion of the Laplace transform."Quart. Appl. Math 14.405-414 (1957): 124.
  • 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.
  • G. Pólya, On the number of certain lattice polygons. J. Combinatorial Theory 6 1969 102-105. MR0236031 (38 #4329)
  • C. Pomerance, Divisors of the middle binomial coefficient, Amer. Math. Monthly, 112 (2015), 636-644.
  • Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.
  • Ronald C. Read, "The Graph Theorists who Count -- and What They Count", in 'The Mathematical Gardner', in D. A. Klarner, Ed., pp. 331-334, Wadsworth CA 1989.
  • 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, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
  • E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.
  • Shapiro, Louis W. Catalan numbers and "total information" numbers. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pp. 531-539. Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975. MR0398853 (53 #2704).
  • 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 and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.
  • L. W. Shapiro, W.-J. Woan and S. Getu, The Catalan numbers via the World Series, Math. Mag., 66 (1993), 20-22.
  • D. M. Silberger, Occurrences of the integer (2n-2)!/n!(n-1)!, Roczniki Polskiego Towarzystwa Math. 13 (1969): 91-96.
  • 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).
  • S. Snover and S. Troyer, Multidimensional Catalan numbers, Abstracts 848-05-94 and 848-05-95, 848th Meeting, Amer. Math. Soc., Worcester Mass., March 15-16, 1989.
  • 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.
  • Richard P. Stanley, "Catalan Numbers", Cambridge University Press, 2015.
  • J. J. Sylvester, On reducible cyclodes, Coll. Math. Papers, Vol. 2, see especially page 670, where Catalan numbers appear.
  • Thiel, Marko. "A new cyclic sieving phenomenon for Catalan objects." Discrete Mathematics 340.3 (2017): 426-429.
  • 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.
  • D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 41.
  • J. Wuttke, The zig-zag walk with scattering and absorption on the real half line and in a lattice model, J. Phys. A 47 (2014), 215203, 1-9.

Links

Crossrefs

Cf. A000142, A000245, A000344, A000588, A000957, A000984, A001392, A001453, A001791, A002057, A002420, A003046, A003517, A003518, A003519, A006480, A008276, A008549, A014137, A014138, A014140, A022553 (inv. Eul. trans.), A024492, A032357, A032443, A039599, A048990, A059288, A068875, A069640, A086117, A088327 (Eul. trans.), A094216, A094638, A094639, A098597, A099731, A119822, A120304, A124926, A129763, A137697, A154559, A161581, A167892, A167893, A179277, A211611, A275431 (multisets).
A row of A060854.
See A001003, A001190, A001699, A000081 for other ways to count parentheses.
Enumerates objects encoded by A014486.
A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
Cf. A051168 (diagonal of the square array described).
Cf. A033552, A176137 (partitions into Catalan numbers).
Cf. A000753, A000736 (Boustrophedon transforms).
Cf. A120303 (largest prime factor of Catalan number).
Cf. A121839 (reciprocal Catalan constant), A268813.
Cf. A038003, A119861, A119908, A120274, A120275 (odd Catalan number).
Cf. A002390 (decimal expansion of natural logarithm of golden ratio).
Coefficients of square root of the g.f. are A001795/A046161.
For a(n) mod 6 see A259667.
For a(n) in base 2 see A264663.
Hankel transforms with first terms omitted: A001477, A006858, A091962, A078920, A123352, A368025.
Cf. A001147, A163960.
Cf. A332602 (conjectured production matrix).
Polyominoes: A001683(n+2) (oriented), A000207 (unoriented), A369314 (chiral), A208355(n-1) (achiral), A001764 {4,oo}.

Programs

  • GAP
    A000108:=List([0..30],n->Binomial(2*n,n)/(n+1)); # Muniru A Asiru, Feb 17 2018
  • Haskell
    import Data.List (genericIndex)
a000108 n = genericIndex a000108_list n
a000108_list = 1 : catalan [1] where
   catalan cs = c : catalan (c:cs) where
      c = sum $ zipWith (*) cs $ reverse cs
-- Reinhard Zumkeller, Nov 12 2011
a000108 = map last $ iterate (scanl1 (+) . (++ [0])) [1]
-- David Spies, Aug 23 2015
  • Magma
    C:= func< n | Binomial(2*n,n)/(n+1) >; [ C(n) : n in [0..60]];
  • Magma
    [Catalan(n): n in [0..40]]; // Vincenzo Librandi, Apr 02 2011
  • Maple
    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+1), n=0..42) ];
with(combstruct): bin := {B=Union(Z,Prod(B,B))}: seq(count([B,bin,unlabeled],size=n+1), n=0..25); # Zerinvary Lajos, Dec 05 2007
gser := series(G000108, x=0, 42): seq(coeff(gser, x, n), n=0..41); # Zerinvary Lajos, May 21 2008
seq((2*n)!*coeff(series(hypergeom([],[2],x^2),x,2*n+2),x,2*n),n=0..30); # Peter Luschny, Jan 31 2015
A000108List := proc(m) local A, P, n; A := [1, 1]; P := [1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), A[-1]]);
A := [op(A), P[-1]] od; A end: A000108List(31); # Peter Luschny, Mar 24 2022
  • Mathematica
    Table[(2 n)!/n!/(n + 1)!, {n, 0, 20}]
Table[4^n Gamma[n + 1/2]/(Sqrt[Pi] Gamma[n + 2]), {n, 0, 20}] (* Eric W. Weisstein, Oct 31 2024 *)
Table[Hypergeometric2F1[1 - n, -n, 2, 1], {n, 0, 20}] (* Richard L. Ollerton, Sep 13 2006 *)
Table[CatalanNumber @ n, {n, 0, 20}] (* Robert G. Wilson v, Feb 15 2011 *)
CatalanNumber[Range[0, 20]] (* Eric W. Weisstein, Oct 31 2024 *)
CoefficientList[InverseSeries[Series[x/Sum[x^n, {n, 0, 31}], {x, 0, 31}]]/x, x] (* Mats Granvik, Nov 24 2013 *)
CoefficientList[Series[(1 - Sqrt[1 - 4 x])/(2 x), {x, 0, 20}], x] (* Stefano Spezia, Aug 31 2018 *)
  • Maxima
    A000108(n):=binomial(2*n,n)/(n+1)$ makelist(A000108(n),n,0,30); /* Martin Ettl, Oct 24 2012 */
  • MuPAD
    combinat::dyckWords::count(n) $ n = 0..38 // Zerinvary Lajos, Apr 14 2007
  • PARI
    a(n)=binomial(2*n,n)/(n+1) \\ M. F. Hasler, Aug 25 2012
  • PARI
    a(n) = (2*n)! / n! / (n+1)!
  • PARI
    a(n) = my(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))}; /* Michael Somos */
  • PARI
    (recur(a,b)=if(b<=2,(a==2)+(a==b)+(a!=b)*(1+a/2), (1+a/b)*recur(a,b-1))); a(n)=recur(n,n); \\ R. J. Cano, Nov 22 2012
  • PARI
    x='x+O('x^40); Vec((1-sqrt(1-4*x))/(2*x)) \\ Altug Alkan, Oct 13 2015
  • Python
    from gmpy2 import divexact
A000108 = [1, 1]
for n in range(1, 10**3):
    A000108.append(divexact(A000108[-1]*(4*n+2),(n+2))) # Chai Wah Wu, Aug 31 2014
  • Python
    # Works in Sage also.
A000108 = [1]
for n in range(1000):
    A000108.append(A000108[-1]*(4*n+2)//(n+2)) # Günter Rote, Nov 08 2023
  • Sage
    [catalan_number(i) for i in range(27)] # Zerinvary Lajos, Jun 26 2008
  • Sage
    # Generalized algorithm of L. Seidel
def A000108_list(n) :
    D = [0]*(n+1); D[1] = 1
    b = True; h = 1; R = []
    for i in range(2*n-1) :
        if b :
            for k in range(h,0,-1) : D[k] += D[k-1]
            h += 1; R.append(D[1])
        else :
            for k in range(1,h, 1) : D[k] += D[k+1]
        b = not b
    return R
A000108_list(31) # Peter Luschny, Jun 02 2012

Formula

a(n) = binomial(2*n, n)/(n+1) = (2*n)!/(n!*(n+1)!) = A000984(n)/(n+1).
Recurrence: a(n) = 2*(2*n-1)*a(n-1)/(n+1) with a(0) = 1.
Recurrence: a(n) = Sum_{k=0..n-1} a(k)a(n-1-k).
G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x), and satisfies A(x) = 1 + x*A(x)^2.
a(n) = Product_{k=2..n} (1 + n/k).
a(n+1) = Sum_{i} binomial(n, 2*i)*2^(n-2*i)*a(i). - Touchard
It is known that a(n) is odd if and only if n=2^k-1, k=0, 1, 2, 3, ... - Emeric Deutsch, Aug 04 2002, corrected by M. F. Hasler, Nov 08 2015
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) = (1/(2*Pi))*Integral_{x=0..4} x^n*sqrt((4-x)/x). - Karol A. Penson, Apr 12 2001
E.g.f.: exp(2*x)*(I_0(2*x)-I_1(2*x)), where I_n is Bessel function. - Karol A. Penson, Oct 07 2001
a(n) = 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). - Philippe Deléham, Dec 22 2003
a(n+1) = (1/(n+1))*Sum_{k=0..n} a(n-k)*binomial(2k+1, k+1). - Philippe Deléham, Jan 24 2004
a(n) = Sum_{k>=0} A008313(n, k)^2. - Philippe Deléham, Feb 14 2004
a(m+n+1) = Sum_{k>=0} A039598(m, k)*A039598(n, k). - Philippe Deléham, Feb 15 2004
a(n) = Sum_{k=0..n} (-1)^k*2^(n-k)*binomial(n, k)*binomial(k, floor(k/2)). - Paul Barry, Jan 27 2005
Sum_{n>=0} 1/a(n) = 2 + 4*Pi/3^(5/2) = F(1,2;1/2;1/4) = A268813 = 2.806133050770763... (see L'Univers de Pi link). - Gerald McGarvey and Benoit Cloitre, Feb 13 2005
a(n) = Sum_{k=0..floor(n/2)} ((n-2*k+1)*binomial(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, Apr 23 2005
a((m+n)/2) = Sum_{k>=0} A053121(m, k)*A053121(n, k) if m+n is even. - Philippe Deléham, May 26 2005
E.g.f. Sum_{n>=0} a(n) * x^(2*n) / (2*n)! = BesselI(1, 2*x) / 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 + (u*v)^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)). - Franklin T. Adams-Watters, Feb 08 2006
Sum_{k>=1} a(k)/4^k = 1. - Franklin T. Adams-Watters, Jun 28 2006
a(n) = A047996(2*n+1, n). - Philippe Deléham, Jul 25 2006
Binomial transform of A005043. - Philippe Deléham, Oct 20 2006
a(n) = Sum_{k=0..n} (-1)^k*A116395(n,k). - Philippe Deléham, 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!. - André F. Labossière, May 29 2007
a(n) = Sum_{k=0..n} A129818(n,k) * A007852(k+1). - Philippe Deléham, Jun 20 2007
a(n) = Sum_{k=0..n} A109466(n,k) * A127632(k). - Philippe Deléham, Jun 20 2007
Row sums of triangle A124926. - Gary W. Adamson, Oct 22 2007
Limit_{n->oo} (1 + Sum_{k=0..n} a(k)/A004171(k)) = 4/Pi. - Reinhard Zumkeller, Aug 26 2008
a(n) = Sum_{k=0..n} A120730(n,k)^2 and a(k+1) = Sum_{n>=k} A120730(n,k). - Philippe Deléham, Oct 18 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])). - Gary W. Adamson, Oct 27 2008
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. - Thomas Wieder, Feb 25 2009
a(n) = A000680(n)/A006472(n+1). - Mark Dols, Jul 14 2010; corrected by M. F. Hasler, Nov 08 2015
Let A(x) be the g.f., then B(x)=x*A(x) satisfies the differential equation B'(x)-2*B'(x)*B(x)-1=0. - Vladimir Kruchinin, Jan 18 2011
Complement of A092459; A010058(a(n)) = 1. - Reinhard Zumkeller, Mar 29 2011
G.f.: 1/(1-x/(1-x/(1-x/(...)))) (continued fraction). - Joerg Arndt, Mar 18 2011
With F(x) = (1-2*x-sqrt(1-4*x))/(2*x) an o.g.f. in x for the Catalan series, G(x) = x/(1+x)^2 is the compositional inverse of F (nulling the n=0 term). - Tom Copeland, Sep 04 2011
With H(x) = 1/(dG(x)/dx) = (1+x)^3 / (1-x), the n-th Catalan number is given by (1/n!)*((H(x)*d/dx)^n)x evaluated at x=0, i.e., F(x) = exp(x*H(u)*d/du)u, evaluated at u = 0. Also, dF(x)/dx = H(F(x)), and H(x) is the o.g.f. for A115291. - Tom Copeland, Sep 04 2011
From Tom Copeland, Sep 30 2011: (Start)
With F(x) = (1-sqrt(1-4*x))/2 an o.g.f. in x for the Catalan series, G(x)= x*(1-x) is the compositional inverse and this relates the Catalan numbers to the row sums of A125181.
With H(x) = 1/(dG(x)/dx) = 1/(1-2x), the n-th Catalan number (offset 1) is given by (1/n!)*((H(x)*d/dx)^n)x evaluated at x=0, i.e., F(x) = exp(x*H(u)*d/du)u, evaluated at u = 0. Also, dF(x)/dx = H(F(x)). (End)
G.f.: (1-sqrt(1-4*x))/(2*x) = G(0) where G(k) = 1 + (4*k+1)*x/(k+1-2*x*(k+1)*(4*k+3)/(2*x*(4*k+3)+(2*k+3)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 30 2011
E.g.f.: exp(2*x)*(BesselI(0,2*x) - BesselI(1,2*x)) = G(0) where G(k) = 1 + (4*k+1)*x/((k+1)*(2*k+1)-x*(k+1)*(2*k+1)*(4*k+3)/(x*(4*k+3)+(k+1)*(2*k+3)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 30 2011
E.g.f.: Hypergeometric([1/2],[2],4*x) which coincides with the e.g.f. given just above, and also by Karol A. Penson further above. - Wolfdieter Lang, Jan 13 2012
A076050(a(n)) = n + 1 for n > 0. - Reinhard Zumkeller, Feb 17 2012
a(n) = A208355(2*n-1) = A208355(2*n) for n > 0. - Reinhard Zumkeller, Mar 04 2012
a(n+1) = A214292(2*n+1,n) = A214292(2*n+2,n). - Reinhard Zumkeller, Jul 12 2012
G.f.: 1 + 2*x/(U(0)-2*x) where U(k) = k*(4*x+1) + 2*x + 2 - x*(2*k+3)*(2*k+4)/U(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Sep 20 2012
G.f.: hypergeom([1/2,1],[2],4*x). - Joerg Arndt, Apr 06 2013
Special values of Jacobi polynomials, in Maple notation: a(n) = 4^n*JacobiP(n,1,-1/2-n,-1)/(n+1). - Karol A. Penson, Jul 28 2013
For n > 0: a(n) = sum of row n in triangle A001263. - Reinhard Zumkeller, Oct 10 2013
a(n) = binomial(2n,n-1)/n and a(n) mod n = binomial(2n,n) mod n = A059288(n). - Jonathan Sondow, Dec 14 2013
a(n-1) = Sum_{t1+2*t2+...+n*tn=n} (-1)^(1+t1+t2+...+tn)*multinomial(t1+t2 +...+tn,t1,t2,...,tn)*a(1)^t1*a(2)^t2*...*a(n)^tn. - Mircea Merca, Feb 27 2014
a(n) = Sum_{k=1..n} binomial(n+k-1,n)/n if n > 0. Alexander Adamchuk, Mar 25 2014
a(n) = -2^(2*n+1) * binomial(n-1/2, -3/2). - Peter Luschny, May 06 2014
a(n) = (4*A000984(n) - A000984(n+1))/2. - Stanislav Sykora, Aug 09 2014
a(n) = A246458(n) * A246466(n). - Tom Edgar, Sep 02 2014
a(n) = (2*n)!*[x^(2*n)]hypergeom([],[2],x^2). - Peter Luschny, Jan 31 2015
a(n) = 4^(n-1)*hypergeom([3/2, 1-n], [3], 1). - Peter Luschny, Feb 03 2015
a(2n) = 2*A000150(2n); a(2n+1) = 2*A000150(2n+1) + a(n). - John Bodeen, Jun 24 2015
a(n) = Sum_{t=1..n+1} n^(t-1)*abs(Stirling1(n+1, t)) / Sum_{t=1..n+1} abs(Stirling1(n+1, t)), for n > 0, see (10) in Cereceda link. - Michel Marcus, Oct 06 2015
a(n) ~ 4^(n-2)*(128 + 160/N^2 + 84/N^4 + 715/N^6 - 10180/N^8)/(N^(3/2)*Pi^(1/2)) where N = 4*n+3. - Peter Luschny, Oct 14 2015
a(n) = Sum_{k=1..floor((n+1)/2)} (-1)^(k-1)*binomial(n+1-k,k)*a(n-k) if n > 0; and a(0) = 1. - David Pasino, Jun 29 2016
Sum_{n>=0} (-1)^n/a(n) = 14/25 - 24*arccsch(2)/(25*sqrt(5)) = 14/25 - 24*A002390/(25*sqrt(5)) = 0.353403708337278061333... - Ilya Gutkovskiy, Jun 30 2016
C(n) = (1/n) * Sum_{i+j+k=n-1} C(i)*C(j)*C(k)*(k+1), n >= 1. - Yuchun Ji, Feb 21 2016
C(n) = 1 + Sum_{i+j+kYuchun Ji, Sep 01 2016
a(n) = A001700(n) - A162551(n) = binomial(2*n+1,n+1). - 2*binomial(2*n,n-1). - Taras Goy, Aug 09 2018
G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x) = 2F1(1/2,1;2;4*x). G.f. A(x) satisfies A = 1 + x*A^2. - R. J. Mathar, Nov 17 2018
C(n) = 1 + Sum_{i=0..n-1} A000245(i). - Yuchun Ji, Jan 10 2019
From A.H.M. Smeets, Apr 11 2020: (Start)
(1+sqrt(1+4*x))/2 = 1-Sum_{i >= 0} a(i)*(-x)^(i+1), for any complex x with |x| < 1/4; and sqrt(x+sqrt(x+sqrt(x+...))) = 1-Sum_{i >= 0} a(i)*(-x)^(i+1), for any complex x with |x| < 1/4 and x <> 0. (End)
a(3n+1)*a(5n+4)*a(15n+10) = a(3n+2)*a(5n+2)*a(15n+11). The first case of Catalan product equation of a triple partition of 23n+15. - Yuchun Ji, Sep 27 2020
a(n) = 4^n * (-1)^(n+1) * 3F2[{n + 1,n + 1/2,n}, {3/2,1}, -1], n >= 1. - Sergii Voloshyn, Oct 22 2020
a(n) = 2^(1 + 2 n) * (-1)^(n)/(1 + n) * 3F2[{n, 1/2 + n, 1 + n}, {1/2, 1}, -1], n >= 1. - Sergii Voloshyn, Nov 08 2020
a(n) = (1/Pi)*4^(n+1)*Integral_{x=0..Pi/2} cos(x)^(2*n)*sin(x)^2 dx. - Greg Dresden, May 30 2021
From Peter Bala, Aug 17 2021: (Start)
G.f. A(x) satisfies A(x) = 1/sqrt(1 - 4*x) * A( -x/(1 - 4*x) ) and (A(x) + A(-x))/2 = 1/sqrt(1 - 4*x) * A( -2*x/(1 - 4*x) ); these are the cases k = 0 and k = -1 of the general formula 1/sqrt(1 - 4*x) * A( (k-1)*x/(1 - 4*x) ) = Sum_{n >= 0} ((k^(n+1) - 1)/(k - 1))*Catalan(n)*x^n.
2 - sqrt(1 - 4*x)/A( k*x/(1 - 4*x) ) = 1 + Sum_{n >= 1} (1 + (k + 1)^n) * Catalan(n-1)*x^n. (End)
Sum_{n>=0} a(n)*(-1/4)^n = 2*(sqrt(2)-1) (A163960). - Amiram Eldar, Mar 22 2022
0 = a(n)*(16*a(n+1) - 10*a(n+2)) + a(n+1)*(2*a(n+1) + a(n+2)) for all n>=0. - Michael Somos, Dec 12 2022
G.f.: (offset 1) 1/G(x), with G(x) = 1 - 2*x - x^2/G(x) (Jacobi continued fraction). - Nikolaos Pantelidis, Feb 01 2023
a(n) = K^(2n+1, n, 1) for all n >= 0, where K^(n, s, x) is the Krawtchouk polynomial defined to be Sum_{k=0..s} (-1)^k * binomial(n-x, s-k) * binomial(x, k). - Vladislav Shubin, Aug 17 2023
From Peter Bala, Feb 03 2024: (Start)
The g.f. A(x) satisfies the following functional equations:
A(x) = 1 + x/(1 - 4*x) * A(-x/(1 - 4*x))^2,
A(x^2) = 1/(1 - 2*x) * A(- x/(1 - 2*x))^2 and, for arbitrary k,
1/(1 - k*x) * A(x/(1 - k*x))^2 = 1/(1 - (k+4)*x) * A(-x/(1 - (k+4)*x))^2. (End)
a(n) = A363448(n) + A363449(n). - Julien Rouyer, Jun 28 2024

A001037 Number of degree-n irreducible polynomials over GF(2); number of n-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive period n; number of binary Lyndon words of length n.

Original entry on oeis.org

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182, 4080, 7710, 14532, 27594, 52377, 99858, 190557, 364722, 698870, 1342176, 2580795, 4971008, 9586395, 18512790, 35790267, 69273666, 134215680, 260300986, 505286415, 981706806, 1908866960, 3714566310, 7233615333, 14096302710, 27487764474
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also dimensions of free Lie algebras - see A059966, which is essentially the same sequence.
This sequence also represents the number N of cycles of length L in a digraph under x^2 seen modulo a Mersenne prime M_q=2^q-1. This number does not depend on q and L is any divisor of q-1. See Theorem 5 and Corollary 3 of the Shallit and Vasiga paper: N=sum(eulerphi(d)/order(d,2)) where d is a divisor of 2^(q-1)-1 such that order(d,2)=L. - Tony Reix, Nov 17 2005
Except for a(0) = 1, Bau-Sen Du's [1985/2007] Table 1, p. 6, has this sequence as the 7th (rightmost) column. Other columns of the table include (but are not identified as) A006206-A006208. - Jonathan Vos Post, Jun 18 2007
"Number of binary Lyndon words" means: number of binary strings inequivalent modulo rotation (cyclic permutation) of the digits and not having a period smaller than n. This provides a link to A103314, since these strings correspond to the inequivalent zero-sum subsets of U_m (m-th roots of unity) obtained by taking the union of U_n (n|m) with 0 or more U_d (n | d, d | m) multiplied by some power of exp(i 2Pi/n) to make them mutually disjoint. (But not all zero-sum subsets of U_m are of that form.) - M. F. Hasler, Jan 14 2007
Also the number of dynamical cycles of period n of a threshold Boolean automata network which is a quasi-minimal positive circuit of size a multiple of n and which is updated in parallel. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Feb 25 2009
Also, the number of periodic points with (minimal) period n in the iteration of the tent map f(x):=2min{x,1-x} on the unit interval. - Pietro Majer, Sep 22 2009
Number of distinct cycles of minimal period n in a shift dynamical system associated with a totally disconnected hyperbolic iterated function system (see Barnsley link). - Michel Marcus, Oct 06 2013
From Jean-Christophe Hervé, Oct 26 2014: (Start)
For n > 0, a(n) is also the number of orbits of size n of the transform associated to the Kolakoski sequence A000002 (and this is true for any map with 2^n periodic points of period n). The Kolakoski transform changes a sequence of 1's and 2's by the sequence of the lengths of its runs. The Kolakoski sequence is one of the two fixed points of this transform, the other being the same sequence without the initial term. A025142 and A025143 are the periodic points of the orbit of size 2. A027375(n) = n*a(n) gives the number of periodic points of minimal period n.
For n > 1, this sequence is equal to A059966 and to A060477, and for n = 1, a(1) = A059966(1)+1 = A060477(1)-1; this because the n-th term of all 3 sequences is equal to (1/n)*sum_{d|n} mu(n/d)*(2^d+e), with e = -1/0/1 for resp. A059966/this sequence/A060477, and sum_{d|n} mu(n/d) equals 1 for n = 1 and 0 for all n > 1. (End)
Warning: A000031 and A001037 are easily confused, since they have similar formulas.
From Petros Hadjicostas, Jul 14 2020: (Start)
Following Kam Cheong Au (2020), let d(w,N) be the dimension of the Q-span of weight w and level N of colored multiple zeta values (CMZV). Here Q are the rational numbers.
Deligne's bound says that d(w,N) <= D(w,N), where 1 + Sum_{w >= 1} D(w,N)*t^w = (1 - a*t + b*t^2)^(-1) when N >= 3, where a = phi(N)/2 + omega(N) and b = omega(N) - 1 (with omega(N) = A001221(N) being the number of distinct primes of N).
For N = 3, a = phi(3)/2 + omega(3) = 2/2 + 1 = 2 and b = omega(3) - 1 = 0. It follows that D(w, N=3) = A000079(w) = 2^w.
For some reason, Kam Cheong Au (2020) assumes Deligne's bound is tight, i.e., d(w,N) = D(w,N). He sets Sum_{w >= 1} c(w,N)*t^w = log(1 + Sum_{w >= 1} d(w,N)*t^w) = log(1 + Sum_{w >= 1} D(w,N)*t^w) = -log(1 - a*t + b*t^2) for N >= 3.
For N = 3, we get that c(w, N=3) = A000079(w)/w = 2^w/w.
He defines d*(w,N) = Sum_{k | w} (mu(k)/k)*c(w/k,N) to be the "number of primitive constants of weight w and level N". (Using the terminology of A113788, we may perhaps call d*(w,N) the number of irreducible colored multiple zeta values at weight w and level N.)
Using standard techniques of the theory of g.f.'s, we can prove that Sum_{w >= 1} d*(w,N)*t^w = Sum_{s >= 1} (mu(s)/s) Sum_{k >= 1} c(k,N)*(t^s)^k = -Sum_{s >= 1} (mu(s)/s)*log(1 - a*t^s + b*t^(2*s)).
For N = 3, we saw that a = 2 and b = 0, and hence d*(w, N=3) = a(w) = Sum_{k | w} (mu(k)/k) * 2^(w/k) / (w/k) = (1/w) * Sum_{k | w} mu(k) * 2^(w/k) for w >= 1. See Table 1 on p. 6 in Kam Cheong Au (2020). (End)

Examples

			Binary strings (Lyndon words, cf. A102659):
a(0) = 1 = #{ "" },
a(1) = 2 = #{ "0", "1" },
a(2) = 1 = #{ "01" },
a(3) = 2 = #{ "001", "011" },
a(4) = 3 = #{ "0001", "0011", "0111" },
a(5) = 6 = #{ "00001", "00011", "00101", "00111", "01011", "01111" }.

References

  • Michael F. Barnsley, Fractals Everywhere, Academic Press, San Diego, 1988, page 171, Lemma 3.
  • E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
  • E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie. On the digraph defined by squaring mod m, when m has primitive roots. Congr. Numer. 82 (1991), 167-177.
  • P. J. Freyd and A. Scedrov, Categories, Allegories, North-Holland, Amsterdam, 1990. See 1.925.
  • M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983, pp. 65, 79.
  • Robert M. May, "Simple mathematical models with very complicated dynamics." Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - N. J. A. Sloane, Mar 17 2019
  • Guy Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
  • M. R. Nester, (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence in entries N0046 and N0287).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Column 2 of A074650.
Row sums of A051168, which gives the number of Lyndon words with fixed number of zeros and ones.
Euler transform is A000079.
See A058943 and A102569 for initial terms. See also A058947, A011260, A059966.
Irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058943, A058944, A058948, A058945, A058946. Primitive irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058947, A058949, A058952, A058950, A058951.
Cf. A000031 (n-bead necklaces but may have period dividing n), A014580, A046211, A046209, A006206-A006208, A038063, A060477, A103314.
Cf. A027750, A008683, A254040.
See also A102659 for the list of binary Lyndon words themselves.
Cf. A000010, A008683.

Programs

  • Haskell
    a001037 0 = 1
a001037 n = (sum $ map (\d -> (a000079 d) * a008683 (n `div` d)) $
                       a027750_row n) `div` n
-- Reinhard Zumkeller, Feb 01 2013
  • Maple
    with(numtheory): A001037 := proc(n) local a,d; if n = 0 then RETURN(1); else a := 0: for d in divisors(n) do a := a+mobius(n/d)*2^d; od: RETURN(a/n); fi; end;
  • Mathematica
    f[n_] := Block[{d = Divisors@ n}, Plus @@ (MoebiusMu[n/d]*2^d/n)]; Array[f, 32]
  • PARI
    A001037(n)=if(n>1,sumdiv(n,d,moebius(d)*2^(n/d))/n,n+1) \\ Edited by M. F. Hasler, Jan 11 2016
  • PARI
    {a(n)=polcoeff(1-sum(k=1,n,moebius(k)/k*log(1-2*x^k+x*O(x^n))),n)} \\ Paul D. Hanna, Oct 13 2010
  • PARI
    a(n)=if(n>1,my(s);forstep(i=2^n+1,2^(n+1),2,s+=polisirreducible(Mod(1,2) * Pol(binary(i))));s,n+1) \\ Charles R Greathouse IV, Jan 26 2012
  • Python
    from sympy import divisors, mobius
def a(n): return sum(mobius(d) * 2**(n//d) for d in divisors(n))/n if n>1 else n + 1 # Indranil Ghosh, Apr 26 2017

Formula

For n >= 1:
a(n) = (1/n)*Sum_{d | n} mu(n/d)*2^d.
A000031(n) = Sum_{d | n} a(d).
2^n = Sum_{d | n} d*a(d).
a(n) = A027375(n)/n.
a(n) = A000048(n) + A051841(n).
For n > 1, a(n) = A059966(n) = A060477(n).
G.f.: 1 - Sum_{n >= 1} moebius(n)*log(1 - 2*x^n)/n, where moebius(n) = A008683(n). - Paul D. Hanna, Oct 13 2010
From Richard L. Ollerton, May 10 2021: (Start)
For n >= 1:
a(n) = (1/n)*Sum_{k=1..n} mu(gcd(n,k))*2^(n/gcd(n,k))/phi(n/gcd(n,k)).
a(n) = (1/n)*Sum_{k=1..n} mu(n/gcd(n,k))*2^gcd(n,k)/phi(n/gcd(n,k)). (End)
a(n) ~ 2^n / n. - Vaclav Kotesovec, Aug 11 2021

Extensions

Revised by N. J. A. Sloane, Jun 10 2012

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

Original entry on oeis.org

1, 1, 3, 6, 15, 27, 63, 120, 252, 495, 1023, 2010, 4095, 8127, 16365, 32640, 65535, 130788, 262143, 523770, 1048509, 2096127, 4194303, 8386440, 16777200, 33550335, 67108608, 134209530, 268435455, 536854005, 1073741823, 2147450880
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Also number of compositions of n into relatively prime parts (that is, the gcd of all the parts is 1). Also number of subsets of {1,2,..,n} containing n and consisting of relatively prime numbers. - Vladeta Jovovic, Aug 13 2003
Also number of perfect parity patterns that have exactly n columns (see A118141). - Don Knuth, May 11 2006
a(n) is odd if and only if n is squarefree (Tim Keller). - Emeric Deutsch, Apr 27 2007
a(n) is a multiple of 3 for all n>=3 (see Problem 11161 link). - Emeric Deutsch, Aug 13 2008
Row sums of triangle A143424. - Gary W. Adamson, Aug 14 2008
a(n) is the number of monic irreducible polynomials with nonzero constant coefficient in GF(2)[x] of degree n. - Michel Marcus, Oct 30 2016
a(n) is the number of aperiodic compositions of n, the number of compositions of n with relatively prime parts, and the number of compositions of n with relatively prime run-lengths. - Gus Wiseman, Dec 21 2017

Examples

			For n=4, there are 6 compositions of n into coprime parts: <3,1>, <2,1,1>, <1,3>, <1,2,1>, <1,1,2>, and <1,1,1,1>.
From _Gus Wiseman_, Dec 19 2017: (Start)
The a(6) = 27 aperiodic compositions are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1221), (1311), (2112), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
The a(6) = 27 compositions into relatively prime parts are:
  (111111),
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1212), (1221), (1311), (2112), (2121), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (51).
The a(6) = 27 compositions with relatively prime run-lengths are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1131), (1212), (1221), (1311), (2112), (2121), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
(End)

References

  • H. O. Peitgen and P. H. Richter, The Beauty of Fractals, Springer-Verlag; contribution by A. Douady, p. 165.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A000837, A003239, A008683, A008965, A022553, A034738, A035928, A038199, A051168, A054525, A056267, A059966, A143424, A167606, A178472, A216954, A228369, A294859, A296302.
Equals A027375/2.
See A056278 for a variant.
First differences of A085945.
Column k=2 of A143325.
Row sums of A101391.

Programs

  • Maple
    with(numtheory): a[1]:=1: a[2]:=1: for n from 3 to 32 do div:=divisors(n): a[n]:=2^(n-1)-sum(a[n/div[j]],j=2..tau(n)) od: seq(a[n],n=1..32); # Emeric Deutsch, Apr 27 2007
with(numtheory); A000740:=n-> add(mobius(n/d)*2^(d-1), d in divisors(n)); # N. J. A. Sloane, Oct 18 2012
  • Mathematica
    a[n_] := Sum[ MoebiusMu[n/d]*2^(d - 1), {d, Divisors[n]}]; Table[a[n], {n, 1, 32}] (* Jean-François Alcover, Feb 03 2012, after PARI *)
  • PARI
    a(n) = sumdiv(n,d,moebius(n/d)*2^(d-1))
  • Python
    from sympy import mobius, divisors
def a(n): return sum([mobius(n // d) * 2**(d - 1) for d in divisors(n)])
[a(n) for n in range(1, 101)]  # Indranil Ghosh, Jun 28 2017

Formula

a(n) = Sum_{d|n} mu(n/d)*2^(d-1), Mobius transform of A011782. Furthermore, Sum_{d|n} a(d) = 2^(n-1).
a(n) = A027375(n)/2 = A038199(n)/2.
a(n) = Sum_{k=0..n} A051168(n,k)*k. - Max Alekseyev, Apr 09 2013
Recurrence relation: a(n) = 2^(n-1) - Sum_{d|n,d>1} a(n/d). (Lafayette College Problem Group; see the Maple program and Iglesias eq (6)). - Emeric Deutsch, Apr 27 2007
G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - Ilya Gutkovskiy, Oct 24 2018
G.f. satisfies Sum_{n>=1} A( (x/(1 + 2*x))^n ) = x. - Paul D. Hanna, Apr 02 2025

Extensions

Connection with Mandelbrot set discovered by Warren D. Smith and proved by Robert Munafo, Feb 06 2000
Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012

A006918 a(n) = binomial(n+3, 3)/4 for odd n, n*(n+2)*(n+4)/24 for even n.

Original entry on oeis.org

0, 1, 2, 5, 8, 14, 20, 30, 40, 55, 70, 91, 112, 140, 168, 204, 240, 285, 330, 385, 440, 506, 572, 650, 728, 819, 910, 1015, 1120, 1240, 1360, 1496, 1632, 1785, 1938, 2109, 2280, 2470, 2660, 2870, 3080, 3311, 3542, 3795, 4048, 4324, 4600, 4900, 5200, 5525, 5850, 6201, 6552, 6930
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Maximal number of inconsistent triples in a tournament on n+2 nodes [Kac]. - corrected by Leen Droogendijk, Nov 10 2014
a(n-4) is the number of aperiodic necklaces (Lyndon words) with 4 black beads and n-4 white beads.
a(n-3) is the maximum number of squares that can be formed from n lines, for n>=3. - Erich Friedman; corrected by Leen Droogendijk, Nov 10 2014
Number of trees with diameter 4 where at most 2 vertices 1 away from the graph center have degree > 2. - Jon Perry, Jul 11 2003
a(n+1) is the number of partitions of n into parts of two kinds, with at most two parts of each kind. Also a(n-3) is the number of partitions of n with Durfee square of size 2. - Franklin T. Adams-Watters, Jan 27 2006
Factoring the g.f. as x/(1-x)^2 times 1/(1-x^2)^2 we find that the sequence equals (1, 2, 3, 4, ...) convolved with (1, 0, 2, 0, 3, 0, 4, ...), A000027 convolved with its aerated variant. - Gary W. Adamson, May 01 2009
Starting with "1" = triangle A171238 * [1,2,3,...]. - Gary W. Adamson, Dec 05 2009
The Kn21, Kn22, Kn23, Fi2 and Ze2 triangle sums, see A180662 for their definitions, of the Connell-Pol triangle A159797 are linear sums of shifted versions of this sequence, e.g., Kn22(n) = a(n+1) + a(n) + 2*a(n-1) + a(n-2) and Fi2(n) = a(n) + 4*a(n-1) + a(n-2). - Johannes W. Meijer, May 20 2011
For n>3, a(n-4) is the number of (w,x,y,z) having all terms in {1,...,n} and w+x+y+z=|x-y|+|y-z|. - Clark Kimberling, May 23 2012
a(n) is the number of (w,x,y) having all terms in {0,...,n} and w+x+y < |w-x|+|x-y|. - Clark Kimberling, Jun 13 2012
For n>0 number of inequivalent (n-1) X 2 binary matrices, where equivalence means permutations of rows or columns or the symbol set. - Alois P. Heinz, Aug 17 2014
Number of partitions p of n+5 such that p[3] = 2. Examples: a(1)=1 because we have (2,2,2); a(2)=2 because we have (2,2,2,1) and (3,2,2); a(3)=5 because we have (2,2,2,1,1), (2,2,2,2), (3,2,2,1), (3,3,2), and (4,2,2). See the R. P. Stanley reference. - Emeric Deutsch, Oct 28 2014
Sum over each antidiagonal of A243866. - Christopher Hunt Gribble, Apr 02 2015
Number of nonisomorphic outer planar graphs of order n>=3, size n+2, and maximum degree 3. - Christian Barrientos and Sarah Minion, Feb 27 2018
a(n) is the number of 2413-avoiding odd Grassmannian permutations of size n+1. - Juan B. Gil, Mar 09 2023

Examples

			G.f. = x + 2*x^2 + 5*x^3 + 8*x^4 + 14*x^5 + 20*x^6 + 30*x^7 + 40*x^8 + 55*x^9 + ...
From _Gus Wiseman_, Apr 06 2019: (Start)
The a(4 - 3) = 1 through a(8 - 3) = 14 integer partitions with Durfee square of length 2 are the following (see Franklin T. Adams-Watters's second comment). The Heinz numbers of these partitions are given by A325164.
  (22)  (32)   (33)    (43)     (44)
        (221)  (42)    (52)     (53)
               (222)   (322)    (62)
               (321)   (331)    (332)
               (2211)  (421)    (422)
                       (2221)   (431)
                       (3211)   (521)
                       (22111)  (2222)
                                (3221)
                                (3311)
                                (4211)
                                (22211)
                                (32111)
                                (221111)
The a(0 + 1) = 1 through a(4 + 1) = 14 integer partitions of n into parts of two kinds with at most two parts of each kind are the following (see Franklin T. Adams-Watters's first comment).
  ()()  ()(1)  ()(2)   ()(3)    ()(4)
        (1)()  (2)()   (3)()    (4)()
               ()(11)  (1)(2)   (1)(3)
               (1)(1)  ()(21)   ()(22)
               (11)()  (2)(1)   (2)(2)
                       (21)()   (22)()
                       (1)(11)  ()(31)
                       (11)(1)  (3)(1)
                                (31)()
                                (11)(2)
                                (1)(21)
                                (2)(11)
                                (21)(1)
                                (11)(11)
The a(6 - 5) = 1 through a(10 - 5) = 14 integer partitions whose third part is 2 are the following (see Emeric Deutsch's comment). The Heinz numbers of these partitions are given by A307373.
  (222)  (322)   (332)    (432)     (442)
         (2221)  (422)    (522)     (532)
                 (2222)   (3222)    (622)
                 (3221)   (3321)    (3322)
                 (22211)  (4221)    (4222)
                          (22221)   (4321)
                          (32211)   (5221)
                          (222111)  (22222)
                                    (32221)
                                    (33211)
                                    (42211)
                                    (222211)
                                    (322111)
                                    (2221111)
(End)

References

  • J. M. Borwein, D. H. Bailey and R. Girgensohn, Experimentation in Mathematics, A K Peters, Ltd., Natick, MA, 2004. x+357 pp. See p. 147.
  • M. Kac, An example of "counting without counting", Philips Res. Reports, 30 (1975), 20*-22* [Special issue in honour of C. J. Bouwkamp].
  • E. V. McLaughlin, Numbers of factorizations in non-unique factorial domains, Senior Thesis, Allegeny College, Meadville, PA, 2004.
  • K. B. Reid and L. W. Beineke "Tournaments", pp. 169-204 in L. W. Beineke and R. J. Wilson, editors, Selected Topics in Graph Theory, Academic Press, NY, 1978, p. 186, Theorem 6.11.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 2nd ed., 2012, Exercise 4.16, pp. 530, 552.
  • W. A. Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 33.

Links

Crossrefs

Cf. A000031, A001037, A028723, A051168. a(n) = T(n,4), array T as in A051168.
Cf. A000094.
Cf. A171238. - Gary W. Adamson, Dec 05 2009
Row sums of A173997. - Gary W. Adamson, Mar 05 2010
Column k=2 of A242093. Column k=2 of A115720 and A115994.
Cf. A117485, A257990, A307373, A325164, A325168.

Programs

  • Haskell
    a006918 n = a006918_list !! n
a006918_list = scanl (+) 0 a008805_list
-- Reinhard Zumkeller, Feb 01 2013
  • Magma
    [Floor(Binomial(n+4, 4)/(n+4))-Floor((n+2)/8)*(1+(-1)^n)/2: n in [0..60]]; // Vincenzo Librandi, Nov 10 2014
  • Maple
    with(combstruct):ZL:=[st,{st=Prod(left,right),left=Set(U,card=r),right=Set(U,card=r),U=Sequence(Z,card>=3)}, unlabeled]: subs(r=1,stack): seq(count(subs(r=2,ZL),size=m),m=11..58) ; # Zerinvary Lajos, Mar 09 2007
A006918 := proc(n)
    if type(n,'even') then
        n*(n+2)*(n+4)/24 ;
    else
        binomial(n+3,3)/4 ;
    fi ;
end proc: # R. J. Mathar, May 17 2016
  • Mathematica
    f[n_]:=If[EvenQ[n],(n(n+2)(n+4))/24,Binomial[n+3,3]/4]; Join[{0},Array[f,60]]  (* Harvey P. Dale, Apr 20 2011 *)
durf[ptn_]:=Length[Select[Range[Length[ptn]],ptn[[#]]>=#&]];
Table[Length[Select[IntegerPartitions[n],durf[#]==2&]],{n,0,30}] (* Gus Wiseman, Apr 06 2019 *)
  • PARI
    { parttrees(n)=local(pt,k,nk); if (n%2==0, pt=(n/2+1)^2, pt=ceil(n/2)*(ceil(n/2)+1)); pt+=floor(n/2); for (x=1,floor(n/2),pt+=floor(x/2)+floor((n-x)/2)); if (n%2==0 && n>2, pt-=floor(n/4)); k=1; while (3*k<=n, for (x=k,floor((n-k)/2), pt+=floor(k/2); if (x!=k, pt+=floor(x/2)); if ((n-x-k)!=k && (n-x-k)!=x, pt+=floor((n-x-k)/2))); k++); pt }
  • PARI
    {a(n) = n += 2; (n^3 - n * (2-n%2)^2) / 24}; /* Michael Somos, Aug 15 2009 */

Formula

G.f.: x/((1-x)^2*(1-x^2)^2) = x/((1+x)^2*(1-x)^4).
0, 0, 0, 1, 2, 5, 8, 14, ... has a(n) = (Sum_{k=0..n} floor(k(n-k)/2))/2. - Paul Barry, Sep 14 2003
0, 0, 0, 0, 0, 1, 2, 5, 8, 14, 20, 30, 40, 55, ... has a(n) = binomial(floor(1/2 n), 3) + binomial(floor(1/2 n + 1/2), 3) [Eke]. - N. J. A. Sloane, May 12 2012
a(0)=0, a(1)=1, a(n) = (2/(n-1))*a(n-1) + ((n+3)/(n-1))*a(n-2). - Benoit Cloitre, Jun 28 2004
a(n) = floor(binomial(n+4, 4)/(n+4)) - floor((n+2)/8)(1+(-1)^n)/2. - Paul Barry, Jan 01 2005
a(n+1) = a(n) + binomial(floor(n/2)+2,2), i.e., first differences are A008805. Convolution of A008619 with itself, then shifted right (or A004526 with itself, shifted left by 3). - Franklin T. Adams-Watters, Jan 27 2006
a(n+1) = (A027656(n) + A003451(n+5))/2 with a(1)=0. - Yosu Yurramendi, Sep 12 2008
Linear recurrence: a(n) = 2a(n-1) + a(n-2) - 4a(n-3) + a(n-4) + 2a(n-5) - a(n-6). - Jaume Oliver Lafont, Dec 05 2008
Euler transform of length 2 sequence [2, 2]. - Michael Somos, Aug 15 2009
a(n) = -a(-4-n) for all n in Z.
a(n+1) + a(n) = A002623(n). - Johannes W. Meijer, May 20 2011
a(n) = (n+2)*(2*n*(n+4)-3*(-1)^n+3)/48. - Bruno Berselli, May 21 2011
a(2n) = A007290(n+2). - Jon Perry, Nov 10 2014
G.f.: (1/(1-x)^4-1/(1-x^2)^2)/4. - Herbert Kociemba, Oct 23 2016
E.g.f.: (x*(18 + 9*x + x^2)*cosh(x) + (6 + 15*x + 9*x^2 + x^3)*sinh(x))/24. - Stefano Spezia, Dec 07 2021
From Amiram Eldar, Mar 20 2022: (Start)
Sum_{n>=1} 1/a(n) = 75/4 - 24*log(2).
Sum_{n>=1} (-1)^(n+1)/a(n) = 69/4 - 24*log(2). (End)

A001840 Expansion of g.f. x/((1 - x)^2*(1 - x^3)).

Original entry on oeis.org

0, 1, 2, 3, 5, 7, 9, 12, 15, 18, 22, 26, 30, 35, 40, 45, 51, 57, 63, 70, 77, 84, 92, 100, 108, 117, 126, 135, 145, 155, 165, 176, 187, 198, 210, 222, 234, 247, 260, 273, 287, 301, 315, 330, 345, 360, 376, 392, 408, 425, 442, 459, 477, 495, 513, 532, 551, 570, 590
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n-3) is the number of aperiodic necklaces (Lyndon words) with 3 black beads and n-3 white beads.
Number of triangular partitions (see Almkvist).
Consists of arithmetic progression quadruples of common difference n+1 starting at A045943(n). Refers to the least number of coins needed to be rearranged in order to invert the pattern of a (n+1)-rowed triangular array. For instance, a 5-rowed triangular array requires a minimum of a(4)=5 rearrangements (shown bracketed here) for it to be turned upside down.
.....{*}..................{*}*.*{*}{*}
.....*.*....................*.*.*.{*}
....*.*.*....---------\......*.*.*
..{*}*.*.*...---------/.......*.*
{*}{*}*.*{*}..................{*}
- Lekraj Beedassy, Oct 13 2003
Partial sums of 1,1,1,2,2,2,3,3,3,4,4,4,... - Jon Perry, Mar 01 2004
Sum of three successive terms is a triangular number in natural order starting with 3: a(n)+a(n+1)+a(n+2) = T(n+2) = (n+2)*(n+3)/2. - Amarnath Murthy, Apr 25 2004
Apply Riordan array (1/(1-x^3),x) to n. - Paul Barry, Apr 16 2005
Absolute values of numbers that appear in A145919. - Matthew Vandermast, Oct 28 2008
In the Moree definition, (-1)^n*a(n) is the 3rd Witt transform of A033999 and (-1)^n*A004524(n) with 2 leading zeros dropped is the 2nd Witt transform of A033999. - R. J. Mathar, Nov 08 2008
Column sums of:
1 2 3 4 5 6 7 8 9.....
1 2 3 4 5 6.....
1 2 3.....
........................
----------------------
1 2 3 5 7 9 12 15 18 - Jon Perry, Nov 16 2010
a(n) is the sum of the positive integers <= n that have the same residue modulo 3 as n. They are the additive counterpart of the triple factorial numbers. - Peter Luschny, Jul 06 2011
a(n+1) is the number of 3-tuples (w,x,y) with all terms in {0,...,n} and w=3*x+y. - Clark Kimberling, Jun 04 2012
a(n+1) is the number of pairs (x,y) with x and y in {0,...,n}, x-y = (1 mod 3), and x+y < n. - Clark Kimberling, Jul 02 2012
a(n+1) is the number of partitions of n into two sorts of part(s) 1 and one sort of (part) 3. - Joerg Arndt, Jun 10 2013
Arrange A004523 in rows successively shifted to the right two spaces and sum the columns:
1 2 2 3 4 4 5 6 6...
1 2 2 3 4 4 5...
1 2 2 3 4...
1 2 2...
1...
------------------------------
1 2 3 5 7 9 12 15 18... - L. Edson Jeffery, Jul 30 2014
a(n) = A258708(n+1,1) for n > 0. - Reinhard Zumkeller, Jun 23 2015
Also the number of triples of positive integers summing to n + 4, the first less than each of the other two. Also the number of triples of positive integers summing to n + 2, the first less than or equal to each of the other two. - Gus Wiseman, Oct 11 2020
Also the lower matching number of the (n+1)-triangular honeycomb king graph = n-triangular grid graph (West convention). - Eric W. Weisstein, Dec 14 2024

Examples

			G.f. = x + 2*x^2 + 3*x^3 + 5*x^4 + 7*x^5 + 9*x^6 + 12*x^7 + 15*x^8 + 18*x^9 + ...
1+2+3=6=t(3), 2+3+5=t(4), 5+7+9=t(5).
[n] a(n)
--------
[1] 1
[2] 2
[3] 3
[4] 1 + 4
[5] 2 + 5
[6] 3 + 6
[7] 1 + 4 + 7
[8] 2 + 5 + 8
[9] 3 + 6 + 9
a(7) = floor(2/3) +floor(3/3) +floor(4/3) +floor(5/3) +floor(6/3) +floor(7/3) +floor(8/3) +floor(9/3) = 12. - _Bruno Berselli_, Aug 29 2013

References

  • Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 73, problem 25.
  • Ulrich Faigle, Review of Gerhard Post and G.J. Woeginger, Sports tournaments, home-away assignments and the break minimization problem, MR2224983(2007b:90134), 2007.
  • Hansraj Gupta, Partitions of j-partite numbers into twelve or a smaller number of parts. Collection of articles dedicated to Professor P. L. Bhatnagar on his sixtieth birthday. Math. Student 40 (1972), 401-441 (1974).
  • Richard K. Guy, A problem of Zarankiewicz, in P. Erdős and G. Katona, editors, Theory of Graphs (Proceedings of the Colloquium, Tihany, Hungary), Academic Press, NY, 1968, pp. 119-150, (p. 126, divided by 2).
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A000031, A001037, A008748, A051168.
Ordered union of triangular matchstick numbers A045943 and generalized pentagonal numbers A001318.
Cf. A058937.
A column of triangle A011847.
Cf. A000217, A130205.
Cf. A258708.
A001399 counts 3-part partitions, ranked by A014612.
A337483 counts either weakly increasing or weakly decreasing triples.
A337484 counts neither strictly increasing nor strictly decreasing triples.
A014311 ranks 3-part compositions, with strict case A337453.
Cf. A007052, A007304, A011782, A069905, A156040, A218004.

Programs

  • Haskell
    a001840 n = a001840_list !! n
a001840_list = scanl (+) 0 a008620_list
-- Reinhard Zumkeller, Apr 16 2012
  • Magma
    [ n le 2 select n else n*(n+1)/2-Self(n-1)-Self(n-2): n in [1..58] ];  // Klaus Brockhaus, Oct 01 2009
  • Maple
    A001840 := n->floor((n+1)*(n+2)/6);
A001840:=-1/((z**2+z+1)*(z-1)**3); # conjectured (correctly) by Simon Plouffe in his 1992 dissertation
seq(floor(binomial(n-1,2)/3), n=3..61); # Zerinvary Lajos, Jan 12 2009
A001840 :=  n -> add(k, k = select(k -> k mod 3 = n mod 3, [$1 .. n])): seq(A001840(n), n = 0 .. 58); # Peter Luschny, Jul 06 2011
  • Mathematica
    a[0]=0; a[1]=1; a[n_]:= a[n]= n(n+1)/2 -a[n-1] -a[n-2]; Table[a[n], {n,0,100}]
f[n_] := Floor[(n + 1)(n + 2)/6]; Array[f, 59, 0] (* Or *)
CoefficientList[ Series[ x/((1 + x + x^2)*(1 - x)^3), {x, 0, 58}], x] (* Robert G. Wilson v *)
a[ n_] := With[{m = If[ n < 0, -3 - n, n]}, SeriesCoefficient[ x /((1 - x^3) (1 - x)^2), {x, 0, m}]]; (* Michael Somos, Jul 11 2011 *)
LinearRecurrence[{2,-1,1,-2,1},{0,1,2,3,5},60] (* Harvey P. Dale, Jul 25 2011 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n+4,{3}],#[[1]]<#[[2]]&&#[[1]]<#[[3]]&]],{n,0,15}] (* Gus Wiseman, Oct 05 2020 *)
  • PARI
    {a(n) = (n+1) * (n+2) \ 6}; /* Michael Somos, Feb 11 2004 */
  • Sage
    [binomial(n, 2) // 3 for n in range(2, 61)] # Zerinvary Lajos, Dec 01 2009

Formula

a(n) = (A000217(n+1) - A022003(n-1))/3;
a(n) = (A016754(n+1) - A010881(A016754(n+1)))/24;
a(n) = (A033996(n+1) - A010881(A033996(n+1)))/24.
Euler transform of length 3 sequence [2, 0, 1].
a(3*k-1) = k*(3*k + 1)/2;
a(3*k) = 3*k*(k + 1)/2;
a(3*k+1) = (k + 1)*(3*k + 2)/2.
a(n) = floor( (n+1)*(n+2)/6 ) = floor( A000217(n+1)/3 ).
a(n+1) = a(n) + A008620(n) = A002264(n+3). - Reinhard Zumkeller, Aug 01 2002
From Michael Somos, Feb 11 2004: (Start)
G.f.: x / ((1-x)^2 * (1-x^3)).
a(n) = 1 + a(n-1) + a(n-3) - a(n-4).
a(-3-n) = a(n). (End)
a(n) = a(n-3) + n for n > 2; a(0)=0, a(1)=1, a(2)=2. - Paul Barry, Jul 14 2004
a(n) = binomial(n+3, 3)/(n+3) + cos(2*Pi*(n-1)/3)/9 + sqrt(3)sin(2*Pi*(n-1)/3)/9 - 1/9. - Paul Barry, Jan 01 2005
From Paul Barry, Apr 16 2005: (Start)
a(n) = Sum_{k=0..n} k*(cos(2*Pi*(n-k)/3 + Pi/3)/3 + sqrt(3)*sin(2*Pi*(n-k)/3 + Pi/3)/3 + 1/3).
a(n) = Sum_{k=0..floor(n/3)} n-3*k. (End)
For n > 1, a(n) = A000217(n) - a(n-1) - a(n-2); a(0)=0, a(1)=1.
G.f.: x/(1 + x + x^2)/(1 - x)^3. - Maksym Voznyy (voznyy(AT)mail.ru), Jul 27 2009
a(n) = (4 + 3*n^2 + 9*n)/18 + ((n mod 3) - ((n-1) mod 3))/9. - Klaus Brockhaus, Oct 01 2009
a(n) = 2*a(n-1) - a(n-2) + a(n-3) - 2*a(n-4) + a(n-5), with n>4, a(0)=0, a(1)=1, a(2)=2, a(3)=3, a(4)=5. - Harvey P. Dale, Jul 25 2011
a(n) = A214734(n + 2, 1, 3). - Renzo Benedetti, Aug 27 2012
G.f.: x*G(0), where G(k) = 1 + x*(3*k+4)/(3*k + 2 - 3*x*(k+2)*(3*k+2)/(3*(1+x)*k + 6*x + 4 - x*(3*k+4)*(3*k+5)/(x*(3*k+5) + 3*(k+1)/G(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Jun 10 2013
Empirical: a(n) = floor((n+3)/(e^(6/(n+3))-1)). - Richard R. Forberg, Jul 24 2013
a(n) = Sum_{i=0..n} floor((i+2)/3). - Bruno Berselli, Aug 29 2013
0 = a(n)*(a(n+2) + a(n+3)) + a(n+1)*(-2*a(n+2) - a(n+3) + a(n+4)) + a(n+2)*(a(n+2) - 2*a(n+3) + a(n+4)) for all n in Z. - Michael Somos, Jan 22 2014
a(n) = n/2 + floor(n^2/3 + 2/3)/2. - Bruno Berselli, Jan 23 2017
a(n) + a(n+1) = A000212(n+2). - R. J. Mathar, Jan 14 2021
Sum_{n>=1} 1/a(n) = 20/3 - 2*Pi/sqrt(3). - Amiram Eldar, Sep 27 2022
E.g.f.: (exp(x)*(4 + 12*x + 3*x^2) - 4*exp(-x/2)*cos(sqrt(3)*x/2))/18. - Stefano Spezia, Apr 05 2023

A047996 Triangle read by rows: T(n,k) is the (n,k)-th circular binomial coefficient, where 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 4, 3, 1, 1, 1, 1, 3, 5, 5, 3, 1, 1, 1, 1, 4, 7, 10, 7, 4, 1, 1, 1, 1, 4, 10, 14, 14, 10, 4, 1, 1, 1, 1, 5, 12, 22, 26, 22, 12, 5, 1, 1, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 1, 1, 6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, 1, 1, 6, 22
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Equivalently, T(n,k) = number of necklaces with k black beads and n-k white beads (binary necklaces of weight k).
The same sequence arises if we take the table U(n,k) = number of necklaces with n black beads and k white beads and read it by antidiagonals (cf. A241926). - Franklin T. Adams-Watters, May 02 2014
U(n,k) is also equal to the number of ways to express 0 as a sum of k elements in Z/nZ. - Jens Voß, Franklin T. Adams-Watters, N. J. A. Sloane, Apr 30 2014 - May 05 2014. See link ("A Note on Modular Partitions and Necklaces") for proof.
The generating function for column k is given by the substitution x_j -> x^j/(1-x^j) in the cycle index of the Symmetric Group of order k. - R. J. Mathar, Nov 15 2018
From Petros Hadjicostas, Jul 12 2019: (Start)
Regarding the comments above by Voss, Adams-Watters, and Sloane, note that Fredman (1975) proved that the number S(n, k, v) of vectors (a_0, ..., a_{n-1}) of nonnegative integer components that satisfy a_0 + ... + a_{n-1} = k and Sum_{i=0..n-1} i*a_i = v (mod n) is given by S(n, k, v) = (1/(n + k)) * Sum_{d | gcd(n, k)} A054535(d, v) * binomial((n + k)/d, k/d) = S(k, n, v).
This result was also proved by Elashvili et al. (1999), who also proved that S(n, k, v) = Sum_{d | gcd(n, k, v)} S(n/d, k/d, 1). Here, S(n, k, 0) = A241926(n, k) = U(n, k) = T(n + k, k) (where T(n, k) is the current array). Also, S(n, k, 1) = A245558(n, k). See also Panyushev (2011) for more general results and for generating functions.
Finally, note that A054535(d, v) = c_d(v) = Sum_{s | gcd(d,v)} s*Moebius(d/s). These are the Ramanujan sums, which equal also the von Sterneck function c_d(v) = phi(d) * Moebius(d/gcd(d, v))/phi(d/gcd(d, v)). We have A054535(d, v) = A054534(v, d).
It would be interesting to see whether there is a proof of the results by Fredman (1975), Elashvili et al. (1999), and Panyushev (2011) for a general v using Molien series as it is done by Sloane (2014) for the case v = 0 (in which case, A054535(d, 0) = phi(d)). (Even though the columns of array A054535(d, v) start at v = 1, we may start the array at column v = 0 as well.)
(End)
U(n, k) is the number of equivalence classes of k-tuples of residues modulo n, identifying those that differ componentwise by a constant and those that differ by a permutation. - Álvar Ibeas, Sep 21 2021

Examples

			Triangle starts:
[ 0]  1,
[ 1]  1,  1,
[ 2]  1,  1,  1,
[ 3]  1,  1,  1,  1,
[ 4]  1,  1,  2,  1,  1,
[ 5]  1,  1,  2,  2,  1,  1,
[ 6]  1,  1,  3,  4,  3,  1,  1,
[ 7]  1,  1,  3,  5,  5,  3,  1,  1,
[ 8]  1,  1,  4,  7, 10,  7,  4,  1,  1,
[ 9]  1,  1,  4, 10, 14, 14, 10,  4,  1,  1,
[10]  1,  1,  5, 12, 22, 26, 22, 12,  5,  1, 1,
[11]  1,  1,  5, 15, 30, 42, 42, 30, 15,  5, 1, 1,
[12]  1,  1,  6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, ...

References

  • N. G. de Bruijn, Polya's theory of counting, in: Applied Combinatorial Mathematics (E. F. Beckenbach, ed.), John Wiley and Sons, New York, 1964, pp. 144-184 (implies g.f. for this triangle).
  • Richard Stanley, Enumerative Combinatorics, 2nd. ed., Vol 1, Chapter I, Problem 105, pp. 122 and 168, discusses the number of subsets of Z/nZ that add to 0. - N. J. A. Sloane, May 06 2014
  • J. Voß, Posting to Sequence Fans Mailing List, April 30, 2014.
  • H. S. Wilf, personal communication to N. J. A. Sloane, Nov., 1990.
  • See A000031 for many additional references and links.

Links

Crossrefs

Row sums: A000031. Columns 0-12: A000012, A000012, A004526, A007997(n+5), A008610, A008646, A032191-A032197.
Cf. A051168, A052307, A052311-A052313.
See A037306 and A241926 for essentially identical triangles.
See A245558, A245559 for a closely related array.

Programs

  • Maple
    A047996 := proc(n,k) local C,d; if k= 0 then return 1; end if; C := 0 ; for d in numtheory[divisors](igcd(n,k)) do C := C+numtheory[phi](d)*binomial(n/d,k/d) ; end do: C/n ; end proc:
seq(seq(A047996(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Apr 14 2011
  • Mathematica
    t[n_, k_] := Total[EulerPhi[#]*Binomial[n/#, k/#] & /@ Divisors[GCD[n, k]]]/n; t[0, 0] = 1; Flatten[Table[t[n, k], {n, 0, 13}, {k, 0, n}]] (* Jean-François Alcover, Jul 19 2011, after given formula *)
  • PARI
    p(n) = if(n<=0, n==0, 1/n * sum(i=0,n-1, (x^(n/gcd(i,n))+1)^gcd(i,n) ));
for (n=0,17, print(Vec(p(n)))); /* print triangle */
/* Joerg Arndt, Sep 28 2012 */
  • PARI
    T(n,k) = if(n<=0, n==0, 1/n * sumdiv(gcd(n,k), d, eulerphi(d)*binomial(n/d,k/d) ) );
/* print triangle: */
{ for (n=0, 17, for (k=0, n, print1(T(n,k),", "); ); print(); ); }
/* Joerg Arndt, Oct 21 2012 */

Formula

T(n, k) = (1/n) * Sum_{d | (n, k)} phi(d)*binomial(n/d, k/d).
T(2*n,n) = A003239(n); T(2*n+1,n) = A000108(n). - Philippe Deléham, Jul 25 2006
G.f. for row n (n>=1): (1/n) * Sum_{i=0..n-1} ( x^(n/gcd(i,n)) + 1 )^gcd(i,n). - Joerg Arndt, Sep 28 2012
G.f.: Sum_{n, k >= 0} T(n, k)*x^n*y^k = 1 - Sum_{s>=1} (phi(s)/s)*log(1-x^s*(1+y^s)). - Petros Hadjicostas, Oct 26 2017
Product_{d >= 1} (1 - x^d - y^d) = Product_{i,j >= 0} (1 - x^i*y^j)^T(i+j, j), where not both i and j are zero. (It follows from Somos' infinite product for array A051168.) - Petros Hadjicostas, Jul 12 2019

Extensions

Name edited by Petros Hadjicostas, Nov 16 2017

A022553 Number of binary Lyndon words containing n letters of each type; periodic binary sequences of period 2n with n zeros and n ones in each period.

Original entry on oeis.org

1, 1, 1, 3, 8, 25, 75, 245, 800, 2700, 9225, 32065, 112632, 400023, 1432613, 5170575, 18783360, 68635477, 252085716, 930138521, 3446158600, 12815663595, 47820414961, 178987624513, 671825020128, 2528212128750, 9536894664375, 36054433807398, 136583760011496
Offset: 0

Views

Author

David Broadhurst

Keywords

Comments

Also number of asymmetric rooted plane trees with n+1 nodes. - Christian G. Bower
Conjecturally, number of irreducible alternating Euler sums of depth n and weight 3n.
a(n+1) is inverse Euler transform of A000108. Inverse Witt transform of A006177.
Dimension of the degree n part of the primitive Lie algebra of the Hopf algebra CQSym (Catalan Quasi-Symmetric functions). - Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Oct 22 2006
For n>0, 2*a(n) is divisible by n (cf. A268619), 12*a(n) is divisible by n^2 (cf. A268592). - Max Alekseyev, Feb 09 2016

Examples

			a(3)=3 counts 6-periodic 000111, 001011 and 001101. a(4)=8 counts 00001111, 00010111, 00011011, 00011101, 00100111, 00101011, 00101101, and 00110101. - _R. J. Mathar_, Oct 20 2021

References

  • F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 336 (4.4.64)

Links

Crossrefs

Cf. A003239, A005354, A000740, A007727, A086655, A289978 (multiset trans.), A001037 (binary Lyndon wds.), A074655 (3 letters), A074656 (4 letters).
A diagonal of the square array described in A051168.

Programs

  • Maple
    with(numtheory):
a:= n-> `if`(n=0, 1,
        add(mobius(n/d)*binomial(2*d, d), d=divisors(n))/(2*n)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 21 2011
  • Mathematica
    a[n_] := Sum[MoebiusMu[n/d]*Binomial[2d, d], {d, Divisors[n]}]/(2n); a[0] = 1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 02 2015 *)
  • PARI
    a(n)=if(n<1,n==0,sumdiv(n,d,moebius(n/d)*binomial(2*d,d))/2/n)
  • Python
    from sympy import mobius, binomial, divisors
def a(n):
    return 1 if n == 0 else sum(mobius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 05 2017
  • Sage
    def a(n):
    return 1 if n ==0 else sum(moebius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
# F. Chapoton, Apr 23 2020

Formula

a(n) = A060165(n)/2 = A007727(n)/(2*n) = A045630(n)/n.
Product_n (1-x^n)^a(n) = 2/(1+sqrt(1-4*x)); a(n) = 1/(2*n) * Sum_{d|n} mu(n/d)*C(2*d,d). Also Moebius transform of A003239. - Christian G. Bower
a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 11 2014
G.f.: 1 + Sum_{k>=1} mu(k)*log((1 - sqrt(1 - 4*x^k))/(2*x^k))/k. - Ilya Gutkovskiy, May 18 2019

A052307 Triangle read by rows: T(n,k) = number of bracelets (reversible necklaces) with n beads, k of which are black and n - k are white.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3, 3, 1, 1, 1, 1, 3, 4, 4, 3, 1, 1, 1, 1, 4, 5, 8, 5, 4, 1, 1, 1, 1, 4, 7, 10, 10, 7, 4, 1, 1, 1, 1, 5, 8, 16, 16, 16, 8, 5, 1, 1, 1, 1, 5, 10, 20, 26, 26, 20, 10, 5, 1, 1, 1, 1, 6, 12, 29, 38, 50, 38, 29, 12, 6, 1, 1, 1, 1, 6, 14, 35, 57, 76, 76, 57, 35, 14, 6, 1, 1
Offset: 0

Views

Author

Christian G. Bower, Nov 15 1999

Keywords

Comments

Equivalently, T(n,k) is the number of orbits of k-element subsets of the vertices of a regular n-gon under the usual action of the dihedral group D_n, or under the action of Euclidean plane isometries. Note that each row of the table is symmetric and unimodal. - Austin Shapiro, Apr 20 2009
Also, the number of k-chords in n-tone equal temperament, up to (musical) transposition and inversion. Example: there are 29 tetrachords, 38 pentachords, 50 hexachords in the familiar 12-tone equal temperament. Called "Forte set-classes," after Allen Forte who first cataloged them. - Jon Wild, May 21 2004

Examples

			Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
   1;
   1,  1;
   1,  1,  1;
   1,  1,  1,  1;
   1,  1,  2,  1,  1;
   1,  1,  2,  2,  1,  1;
   1,  1,  3,  3,  3,  1,  1;
   1,  1,  3,  4,  4,  3,  1,  1;
   1,  1,  4,  5,  8,  5,  4,  1,  1;
   1,  1,  4,  7, 10, 10,  7,  4,  1,  1;
   1,  1,  5,  8, 16, 16, 16,  8,  5,  1,  1;
   1,  1,  5, 10, 20, 26, 26, 20, 10,  5,  1,  1;
   1,  1,  6, 12, 29, 38, 50, 38, 29, 12,  6,  1,  1;
   ...

References

  • Martin Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pages 245-246.
  • N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Links

Crossrefs

Row sums: A000029. Columns 0-12: A000012, A000012, A008619, A001399, A005232, A032279, A005513, A032280, A005514, A032281, A005515, A032282, A005516.
Cf. A047996, A051168, A052308, A052309, A052310.

Programs

  • Maple
    A052307 := proc(n,k)
        local hk,a,d;
        if k = 0 then
                return 1 ;
        end if;
        hk := k mod 2 ;
        a := 0 ;
        for d in numtheory[divisors](igcd(k,n)) do
                a := a+ numtheory[phi](d)*binomial(n/d-1,k/d-1) ;
        end do:
        %/k + binomial(floor((n-hk)/2),floor(k/2)) ;
        %/2 ;
end proc: # R. J. Mathar, Sep 04 2011
  • Mathematica
    Table[If[m*n===0,1,1/2*If[EvenQ[n], If[EvenQ[m], Binomial[n/2, m/2], Binomial[(n-2)/2, (m-1)/2 ]], If[EvenQ[m], Binomial[(n-1)/2, m/2], Binomial[(n-1)/2, (m-1)/2]]] + 1/2*Fold[ #1 +(EulerPhi[ #2]*Binomial[n/#2, m/#2])/n &, 0, Intersection[Divisors[n], Divisors[m]]]], {n,0,12}, {m,0,n}] (* Wouter Meeussen, Aug 05 2002, Jan 19 2009 *)
  • PARI
    B(n,k)={ if(n==0, return(1)); GCD = gcd(n, k); S = 0;
for(d = 1, GCD, if((k%d==0)&&(n%d==0), S+=eulerphi(d)*binomial(n/d,k/d)));
return (binomial(floor(n/2)- k%2*(1-n%2), floor(k/2))/2 + S/(2*n)); }
n=0;k=0; for(L=0, 8645, print(L, " ", B(n,k)); k++; if(k>n, k=0; n++))
/* Washington Bomfim, Jun 30 2012 */
  • Python
    from sympy import binomial as C, totient, divisors, gcd
def T(n, k): return 1 if n==0 else C((n//2) - k%2 * (1 - n%2), (k//2))/2 + sum(totient(d)*C(n//d, k//d) for d in divisors(gcd(n, k)))/(2*n)
for n in range(11): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Apr 23 2017

Formula

T(0,0) = 1. If n > 0, T(n,k) = binomial(floor(n/2) - (k mod 2) * (1 - (n mod 2)), floor(k/2)) / 2 + Sum_{d|n, d|k} (phi(d)*binomial(n/d, k/d)) / (2*n). - Washington Bomfim, Jun 30 2012 [edited by Petros Hadjicostas, May 29 2019]
From Freddy Barrera, Apr 21 2019: (Start)
T(n,k) = (1/2) * (A119963(n,k) + A047996(n,k)).
T(n,k) = T(n, n-k) for each k < n (Theorem 2 of H. Gupta). (End)
G.f. for column k >= 1: (x^k/2) * ((1/k) * Sum_{m|k} phi(m)/(1 - x^m)^(k/m) + (1 + x)/(1 - x^2)^floor((k/2) + 1)). (This formula is due to Herbert Kociemba.) - Petros Hadjicostas, May 25 2019
Bivariate o.g.f.: Sum_{n,k >= 0} T(n, k)*x^n*y^k = (1/2) * ((x + 1) * (x*y + 1) / (1 - x^2 * (y^2 + 1)) + 1 - Sum_{d >= 1} (phi(d)/d) * log(1 - x^d * (1 + y^d))). - Petros Hadjicostas, Jun 13 2019

A054533 Triangular array giving Ramanujan sum T(n,k) = c_n(k) = Sum_{m=1..n, (m,n)=1} exp(2 Pi i m k / n) for n >= 1 and 1 <= k <= n.

Original entry on oeis.org

1, -1, 1, -1, -1, 2, 0, -2, 0, 2, -1, -1, -1, -1, 4, 1, -1, -2, -1, 1, 2, -1, -1, -1, -1, -1, -1, 6, 0, 0, 0, -4, 0, 0, 0, 4, 0, 0, -3, 0, 0, -3, 0, 0, 6, 1, -1, 1, -1, -4, -1, 1, -1, 1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 0, 2, 0, -2, 0, -4, 0, -2, 0, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 12, 1
Offset: 1

Views

Author

N. J. A. Sloane, Apr 09 2000

Keywords

Comments

From Wolfdieter Lang, Jan 06 2017: (Start)
Periodicity: c_n(k+n) = c_n(k). See the Apostol reference p. 161.
Multiplicativity: c_n(k)*c_m(k) = c_{n*m}(k), if gcd(n,m) = 1. For the proof see the Hardy reference, p. 138.
Dirichlet g.f. for fixed k: D(n,s) := Sum_{n>=1} c_n(k)/n^s = sigma_{1-s}(k)/zeta(s) = sigma_{s-1}(k)/(k^(s-1)*zeta(s)) for s > 1, with sigma_m(k) the sum of the m-th power of the divisors of k. See the Hardy reference, eqs. (9.6.1) and (9.6.2), pp. 139-140, or Hardy-Wright, Theorem 292, p. 250.
Sum_{n>=1} c_n(k)/n = 0. See the Hardy reference, p. 141. (End)
Right border gives A000010. - Omar E. Pol, May 08 2018
Fredman (1975) proved that the number S(n, k, v) of vectors (a_0, ..., a_{n-1}) of nonnegative integer components that satisfy a_0 + ... + a_{n-1} = k and Sum_{i=0..n-1} i*a_i = v (mod n) is given by S(n, k, v) = (1/(n + k)) * Sum_{d | gcd(n, k)} T(d, v) * binomial((n + k)/d, k/d) = S(k, n, v). This was also proved by Elashvili et al. (1999), who also proved that S(n, k, v) = Sum_{d | gcd(n, k, v)} S(n/d, k/d, 1). Here, S(n, k, 1) = A051168(n + k, k). - Petros Hadjicostas, Jul 09 2019
We have T(n, k) = c_n(k) = Sum_{m=1..n, (m,n)=1} exp(2 Pi i m k / n) and A054532(n, k) = c_k(n) = Sum_{m=1..k, (m,k)=1} exp(2 Pi i m n / k) for n >= 1 and 1 <= k <= n. - Petros Hadjicostas, Jul 27 2019

Examples

			Triangle begins
   1;
  -1,  1;
  -1, -1,  2;
   0, -2,  0,  2;
  -1, -1, -1, -1,  4;
   1, -1, -2, -1,  1,  2;
  -1, -1, -1, -1, -1, -1,  6;
   0,  0,  0, -4,  0,  0,  0,  4;
   0,  0, -3,  0,  0, -3,  0,  0,  6;
   1, -1,  1, -1, -4, -1,  1, -1,  1,  4;
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10;
   0,  2,  0, -2,  0, -4,  0, -2,  0,  2,  0,  4;
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 12;
   ...
[Edited by _Jon E. Schoenfield_, Jan 03 2017]
Periodicity and multiplicativity: c_6(k) = c_2(k)*c_3(k), e.g.: 2 = c_6(6) = c_2(6)*c_3(6) = c_2(2)*c_3(3) = 1*2 = 2. - _Wolfdieter Lang_, Jan 05 2017

References

  • T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, pp. 160-161.
  • G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, AMS Chelsea Publishing, Providence, Rhode Island, 2002, pp. 137-139.
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. Fifth ed., Oxford Science Publications, Clarendon Press, Oxford, 2003, pp. 237-238.

Links

Crossrefs

Cf. A008683, A054532, A054534, A054535, A282634, A000010.

Programs

  • Mathematica
    c[k_, n_] := Sum[ If[GCD[m, k] == 1, Exp[2 Pi*I*m*n/k], 0], {m, 1, k}]; A054533 = Flatten[ Table[c[n, k] // FullSimplify, {n, 1, 14}, {k, 1, n}] ] (* Jean-François Alcover, Jun 27 2012 *)
(* to get the triangle in the example above *)
FormTable[Table[c[n, k] // FullSimplify, {n, 1, 13}, {k, 1, n}]]
(* Petros Hadjicostas, Jul 28 2019 *)
  • PARI
    T(n,k) = sumdiv(gcd(n,k), d, d*moebius(n/d));
tabl(nn) = {for(n=1, nn, for(k=1, n, print1(T(n,k), ", "); ); print(); ); }; \\ Michel Marcus, Jun 14 2018

Formula

T(n, k) = Sum_{m=1..n, gcd(m,n) = 1} exp(2*Pi*i*m*k / n), n >= 1, 1 <= k <= n, where i is the imaginary unit.
T(n, k) = Sum_{d | gcd(n,k)} d*Moebius(n/d), n >= 1, 1 <= k <= n.

Extensions

Name edited by Petros Hadjicostas, Jul 27 2019

A185700 The number of periods in a reshuffling operation for compositions of n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 3, 5, 5, 3, 1, 0, 1, 3, 7, 8, 7, 3, 1, 0, 1, 4, 9, 14, 14, 9, 4, 1, 0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 0, 1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1
Offset: 1

Views

Author

Paul Weisenhorn, Feb 10 2011

Keywords

Comments

n has 2^(n-1) compositions. For each composition remove the largest part and redistribute it by adding 1 to subsequently smaller parts (creating 1's if needed) to get a new composition of n. (This is reversing the operation in A188160.) Repeat. Eventually this sequence of compositions will cycle. We are interested in the length of the period.
Let the indices k and j be uniquely associated with n using the triangular numbers T=A000217: T(k-1) < n <= T(k) and n = T(k-1) + j with 0 < j <= k.
a(n) with T(k-1) < n <= T(k) is the number of periods with length k for 1 < k.
If k is prime then all periods of the numbers T(k-1) < n < T(k) have length k.
If k is not prime, then the length of the periods is k or a divisor of k.
n = T(k-1) + j has binomial(k,j) partitions in its periods with 0 < j < k.
n = T(k-1) + j has c(n) = Sum_{d|gcd(k,j)} (phi(d)*binomial(k/d,j/d))/k periods of length k or a divisor of k as tabulated in A047996; phi is Euler's totient function. If k is prime then a(n)=c(n) gives the number of periods with length k. If k is not prime, subtract all periods of length < k from c(n).
Obtained from A092964 by adding an initial column of 1's and appending a 1 and 0 to each row. Obtained from A051168 by reading the array downwards along antidiagonals. - R. J. Mathar, Apr 14 2011
As a regular triangle, T(n,k) is the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and length k. Row sums are A059966. - Gus Wiseman, Dec 19 2017

Examples

			For k=5: T(4)=10 < n < T(5)=15 and all periods are of length 5:
a(11)=1 period: [(4+3+2+1+1), (4+3+2+2), (4+3+3+1), (4+4+2+1), (5+3+2+1)];
a(12)=2 periods: [(4+3+2+2+1), (4+3+3+2), (4+4+3+1), (5+4+2+1), (5+3+2+1+1)]; and [(4+4+2+2), (5+3+3+1), (4+4+2+1+1), (5+3+2+2), (4+3+3+1+1)];
a(13)=2 periods: [(4+4+2+2+1), (5+3+3+2), (4+4+3+1+1), (5+4+2+2), (5+3+3+1+1)]; and [(5+4+3+1), (5+4+2+1+1), (5+3+2+2+1), (4+3+3+2+1), (4+4+3+2)];
a(14)=1 period: [(5+4+3+2), (5+4+3+1+1), (5+4+2+2+1), (5+3+3+2+1), (4+4+3+2+1)].
For k=16; j=8; n=T(k-1)+j=128; 1<q|(16,8) --> {2,4,8} a(128) = c(128) - a(T(7)+4) - a(T(3)+2) - a(T(1)+1) =  810 - 8 - 1 - 1 = 800.
  (binomial(16,8)-8*a(T(7)+4)-4*a(T(3)+2)-2*a(T(1)+1))/16 = (12870-64-4-2)/16 = 800 = a(128).
Triangular view, with a(n) distributed in rows k=1,2,3.. according to T(k-1)< n <= T(k):
1;     k=1, n=1
1, 0;    k=2, n=2..3
1, 1,  0;    k=3, n=4..6
1, 1,  1,  0;    k=4, n=7..10
1, 2,  2,  1,   0;    k=5, n=11..15
1, 2,  3,  2,   1,   0;    k=6, n=16..21
1, 3,  5,  5,   3,   1,   0;
1, 3,  7,  8,   7,   3,   1,   0;
1, 4,  9, 14,  14,   9,   4,   1,   0;
1, 4, 12, 20,  25,  20,  12,   4,   1,  0;
1, 5, 15, 30,  42,  42,  30,  15,   5,  1,  0;
1, 5, 18, 40,  66,  75,  66,  40,  18,  5,  1, 0;
1, 6, 22, 55,  99, 132, 132,  99,  55, 22,  6, 1, 0;
1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1, 0;

References

  • R. Baumann, Computer-Knobelei, LOGIN (1987), 483-486 (in German).

Links

Crossrefs

Cf. A000740, A001037, A008965, A051168, A059966, A060223, A245558, A294859, A296302, A296373, A092964, A245559, A245558.

Programs

  • Maple
    A000217 := proc(n) n*(n+1)/2 ; end proc:
A185700 := proc(n) local k,j,a,q; k := ceil( (-1+sqrt(1+8*n))/2 ) ; j := n-A000217(k-1) ; if n = 1 then return 1; elif j = k then return 0 ; end if; a := binomial(k,j) ; if not isprime(k) then for q in numtheory[divisors]( igcd(k,j)) minus {1} do a := a- procname(j/q+A000217(k/q-1))*k/q ; end do: end if; a/k ; end proc:
seq(A185700(n),n=1..80) ; # R. J. Mathar, Jun 11 2011
  • Mathematica
    LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length@Select[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]===k&],LyndonQ],{n,10},{k,n}] (* Gus Wiseman, Dec 19 2017 *)

Formula

a(T(k))=0 with k > 1. a(1)=1.
If k is a prime number and n = T(k-1) + j with 0 < j < k, then a(n) = binomial(k,j)/k.
If k is not prime, subtract the sum of partitions in all periods of n with length < k from the term binomial(k,j). The difference divided by k gives the number of periods for n=T(k-1)+j: a(n)=( binomial(k,j) -sum {a(T(k/q-1)+j/q) *k/q })/k summed over all 1 < q|gcd(k,j).
If k is not prime, subtract the sum of all periods of n with length < k from the term c(n) = sum{ phi(d)*binomial(k/d,j/d) }/k summed over d|gcd(k,j), namely
a(n) = c(n)-sum{a(T(k/q-1)+j))} summed over all 1 < q|gcd(k,j).

Extensions

I have added a comment and deleted a Jun 11 2011 question from R. J. Mathar. - Paul Weisenhorn, Jan 08 2017
Previous Showing 11-20 of 54 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.