A113047 -id:A113047 - cp's OEIS frontend

A001764 a(n) = binomial(3n,n)/(2n+1) (enumerates ternary trees and also noncrossing trees).

1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, 1430715, 8414640, 50067108, 300830572, 1822766520, 11124755664, 68328754959, 422030545335, 2619631042665, 16332922290300, 102240109897695, 642312451217745, 4048514844039120, 25594403741131680, 162250238001816900

Offset: 0

N. J. A. Sloane

Smallest number of straight line crossing-free spanning trees on n points in the plane.
Number of dissections of some convex polygon by nonintersecting diagonals into polygons with an odd number of sides and having a total number of 2n+1 edges (sides and diagonals). - Emeric Deutsch, Mar 06 2002
Number of lattice paths of n East steps and 2n North steps from (0,0) to (n,2n) and lying weakly below the line y=2x. - David Callan, Mar 14 2004
With interpolated zeros, this has g.f. 2*sqrt(3)*sin(arcsin(3*sqrt(3)*x/2)/3)/(3*x) and a(n) = C(n+floor(n/2),floor(n/2))*C(floor(n/2),n-floor(n/2))/(n+1). This is the first column of the inverse of the Riordan array (1-x^2,x(1-x^2)) (essentially reversion of y-y^3). - Paul Barry, Feb 02 2005
Number of 12312-avoiding matchings on [2n].
Number of complete ternary trees with n internal nodes, or 3n edges.
Number of rooted plane trees with 2n edges, where every vertex has even outdegree ("even trees").
a(n) is the number of noncrossing partitions of [2n] with all blocks of even size. E.g.: a(2)=3 counts 12-34, 14-23, 1234. - David Callan, Mar 30 2007
Pfaff-Fuss-Catalan sequence C^{m}_n for m=3, see the Graham et al. reference, p. 347. eq. 7.66.
Also 3-Raney sequence, see the Graham et al. reference, p. 346-7.
The number of lattice paths from (0,0) to (2n,0) using an Up-step=(1,1) and a Down-step=(0,-2) and staying above the x-axis. E.g., a(2) = 3; UUUUDD, UUUDUD, UUDUUD. - Charles Moore (chamoore(AT)howard.edu), Jan 09 2008
a(n) is (conjecturally) the number of permutations of [n+1] that avoid the patterns 4-2-3-1 and 4-2-5-1-3 and end with an ascent. For example, a(4)=55 counts all 60 permutations of [5] that end with an ascent except 42315, 52314, 52413, 53412, all of which contain a 4-2-3-1 pattern and 42513. - David Callan, Jul 22 2008
Central terms of pendular triangle A167763. - Philippe Deléham, Nov 12 2009
With B(x,t)=x+t*x^3, the comp. inverse in x about 0 is A(x,t) = Sum_{j>=0} a(j) (-t)^j x^(2j+1). Let U(x,t)=(x-A(x,t))/t. Then DU(x,t)/Dt=dU/dt+U*dU/dx=0 and U(x,0)=x^3, i.e., U is a solution of the inviscid Burgers's, or Hopf, equation. Also U(x,t)=U(x-t*U(x,t),0) and dB(x,t)/dt = U(B(x,t),t) = x^3 = U(x,0). The characteristics for the Hopf equation are x(t) = x(0) + t*U(x(t),t) = x(0) + t*U(x(0),0) = x(0) + t*x(0)^3 = B(x(0),t). These results apply to all the Fuss-Catalan sequences with 3 replaced by n>0 and 2 by n-1 (e.g., A000108 with n=2 and A002293 with n=4), see also A086810, which can be generalized to A133437, for associahedra. - Tom Copeland, Feb 15 2014
Number of intervals (i.e., ordered pairs (x,y) such that x<=y) in the Kreweras lattice (noncrossing partitions ordered by refinement) of size n, see the Bernardi & Bonichon (2009) and Kreweras (1972) references. - Noam Zeilberger, Jun 01 2016
Number of sum-indecomposable (4231,42513)-avoiding permutations. Conjecturally, number of sum-indecomposable (2431,45231)-avoiding permutations. - Alexander Burstein, Oct 19 2017
a(n) is the number of topologically distinct endstates for the game Planted Brussels Sprouts on n vertices, see Ji and Propp link. - Caleb Ji, May 14 2018
Number of complete quadrillages of 2n+2-gons. See Baryshnikov p. 12. See also Nov 10 2014 comments in A134264. - Tom Copeland, Jun 04 2018
a(n) is the number of 2-regular words on the alphabet [n] that avoid the patterns 231 and 221. Equivalently, this is the number of 2-regular tortoise-sortable words on the alphabet [n] (see the Defant and Kravitz link). - Colin Defant, Sep 26 2018
a(n) is the number of Motzkin paths of length 3n with n steps of each type, with the condition that (1, 0) and (1, 1) steps alternate (starting with (1, 0)). - Helmut Prodinger, Apr 08 2019
a(n) is the number of uniquely sorted permutations of length 2n+1 that avoid the patterns 312 and 1342. - Colin Defant, Jun 08 2019
The compositional inverse o.g.f. pair in Copeland's comment above are related to a pair of quantum fields in Balduf's thesis by Theorem 4.2 on p. 92. - Tom Copeland, Dec 13 2019
The sequences of Fuss-Catalan numbers, of which this is the first after the Catalan numbers A000108 (the next is A002293), appear in articles on random matrices and quantum physics. See Banica et al., Collins et al., and Mlotkowski et al. Interpretations of these sequences in terms of the cardinality of specific sets of noncrossing partitions are provided by A134264. - Tom Copeland, Dec 21 2019
Call C(p, [alpha], g) the number of partitions of a cyclically ordered set with p elements, of cyclic type [alpha], and of genus g (the genus g Faa di Bruno coefficients of type [alpha]). This sequence counts the genus 0 partitions (non-crossing, or planar, partitions) of p = 3n into n parts of length 3: a(n) = C(3n, [3^n], 0). For genus 1 see A371250, for genus 2 see A371251. - Robert Coquereaux, Mar 16 2024
a(n) is the total number of down steps before the first up step in all 2_1-Dyck paths of length 3*n for n > 0. A 2_1-Dyck path is a lattice path with steps (1,2), (1,-1) that starts and ends at y = 0 and does not go below the line y = -1. - Sarah Selkirk, May 10 2020
a(n) is the number of pairs (A<=B) of noncrossing partitions of [n]. - Francesca Aicardi, May 28 2022
a(n) is the number of parking functions of size n avoiding the patterns 231 and 321. - Lara Pudwell, Apr 10 2023
Number of rooted polyominoes composed of n square cells of the hyperbolic regular tiling with Schläfli symbol {4,oo}. A rooted polyomino has one external edge identified, and chiral pairs are counted as two. A stereographic projection of the {4,oo} tiling on the Poincaré disk can be obtained via the Christensson link. - Robert A. Russell, Jan 27 2024
This is instance k = 3 of the family {C(k, n)}A130564.%20-%20_Wolfdieter%20Lang">{n>=0} given in a comment in A130564. - _Wolfdieter Lang, Feb 05 2024
The number of Apollonian networks (planar 3-trees) with n+3 vertices with a given base triangle. - Allan Bickle, Feb 20 2024
Number of rooted polyominoes composed of n tetrahedral cells of the hyperbolic regular tiling with Schläfli symbol {3,3,oo}. A rooted polyomino has one external face identified, and chiral pairs are counted as two. a(n) = T(n) in the second Beineke and Pippert link. - Robert A. Russell, Mar 20 2024

			a(2) = 3 because the only dissections with 5 edges are given by a square dissected by any of the two diagonals and the pentagon with no dissecting diagonal.
G.f. = 1 + x + 3*x^2 + 12*x^3 + 55*x^4 + 273*x^5 + 1428*x^6 + 7752*x^7 + 43263*x^8 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 23.
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.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 200, 347. See also the Pólya-Szegő reference.
W. Kuich, Languages and the enumeration of planted plane trees. Nederl. Akad. Wetensch. Proc. Ser. A 73 = Indag. Math. 32, (1970), 268-280.
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, p. 98.
G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, New York, Heidelberg, Berlin, 2 vols., 1972, Vol. 1, problem 211, p. 146 with solution on p. 348.
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).

G. C. Greubel, Table of n, a(n) for n = 0..1000 [Terms 0 to 100 computed by T. D. Noe; Terms 101 to 1000 by G. C. Greubel, Jan 13 2017]
V. E. Adler and A. B. Shabat, Volterra chain and Catalan numbers, arXiv:1810.13198 [nlin.SI], 2018.
Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
A. Aggarwal, Armstrong's Conjecture for (k, mk+1)-Core Partitions, arXiv:1407.5134 [math.CO], 2014.
O. Aichholzer and H. Krasser, The point set order type data base: a collection of applications and results, pp. 17-20 in Abstracts 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 13-15, 2001.
M. H. Albert, R. E. L. Allred, M. D. Atkinson, H. P. van Ditmarsch, C. C. Handley, and D. A. Holton, Restricted permutations and queue jumping, Discrete Math. 287 (2004), 129-133.
N. Alexeev and A. Tikhomirov, Singular Values Distribution of Squares of Elliptic Random Matrices and type-B Narayana Polynomials, arXiv:1501.04615 [math.PR], 2015.
N. V. Alexeev, Number of trees in a random graph, Probabilistic methods in discrete mathematics, Extended abstracts of the 10th International Petrozavodsk Conference (Russia, 2019), 12-13. (in Russian)
M. Almeida, N. Moreira, and R. Reis, Enumeration and generation with a string automata representation, Theor. Comp. Sci. 387 (2007), 93-102, Theorem 6.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 337-338.
Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014.
A. Asinowski, B. Hackl, and S. Selkirk, Down step statistics in generalized Dyck paths, arXiv:2007.15562 [math.CO], 2020.
Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906 [math.CO], 2007.
Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, Discrete Math., 308 (2008), 4660-4669.
I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765-785.
P. Balduf, The propagator and diffeomorphisms of an interacting field theory, Master's thesis, submitted to the Institut für Physik, Mathematisch-Naturwissenschaftliche Fakultät, Humboldt-Universtität, Berlin, 2018.
Christian Ballot, Lucasnomial Fuss-Catalan Numbers and Related Divisibility Questions, J. Int. Seq., 21 (2018), Article 18.6.5.
C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating functions for generating trees, Discrete Mathematics 246(1-3) (2002), 29-55.
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
T. Banica, S. Belinschi, M. Capitaine, and B. Collins, Free Bessel laws, arXiv:0710.5931 [math.PR], 2008.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016), 343-385.
Paul Barry, Chebyshev moments and Riordan involutions, arXiv:1912.11845 [math.CO], 2019.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See pp. 27, 29.
Y. Baryshnikov, On Stokes sets, New developments in singularity theory (Cambridge, 2000): 65-86. Kluwer Acad. Publ., Dordrecht, 2001.
L. W. Beineke and R. E. Pippert, Enumerating labeled k-dimensional trees and ball dissections, pp. 12-26 of Proceedings of Second Chapel Hill Conference on Combinatorial Mathematics and Its Applications, University of North Carolina, Chapel Hill, 1970. Reprinted in Math. Annalen, 191 (1971), 87-98.
L. W. Beineke and R. E. Pippert, Enumerating dissectable polyhedra by their automorphism groups, Canad. J. Math., 26 (1974), 50-67.
Francois Bergeron, Combinatorics of r-Dyck paths, r-Parking functions, and the r-Tamari lattices, arXiv:1202.6269 [math.CO], 2012.
Olivier Bernardi and Nicolas Bonichon, Intervals in Catalan lattices and realizers of triangulations, Journal of Combinatorial Theory, Series A 116:1 (2009), pp. 55-75. See also Bernardi's slides, Catalan lattices and realizers of triangulations (April 2007).
D. Bevan, D. Levin, P. Nugent, J. Pantone, and L. Pudwell, Pattern avoidance in forests of binary shrubs, arXiv:1510:08036 [math.CO], 2015.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
D. Birmajer, J. B. Gil and M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv:1503.05242 [math.CO], 2015.
Michel Bousquet and Cédric Lamathe, On symmetric structures of order two, Discrete Math. Theor. Comput. Sci. 10 (2008), 153-176.
M. Bousquet-Mélou and M. Petkovšek, Walks confined in a quadrant are not always D-finite, arXiv:math/0211432 [math.CO], 2002.
Włodzimierz Bryc, Raouf Fakhfakh, and Wojciech Młotkowski, Cauchy-Stieltjes families with polynomial variance functions and generalized orthogonality, arXiv:1708.05343 [math.PR], 2017-2019. Also in Probability and Mathematical Statistics 39(2) (2019), 237-258.
David Callan and Toufik Mansour, Ascent sequences avoiding a triple of length-3 patterns, The Electronic Journal of Combinatorics 32(1) (2025), #P1.40. See p. 16.
N. T. Cameron, Random walks, trees and extensions of Riordan group techniques, Dissertation, Howard University, 2002.
Naiomi Cameron and J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.
Peter J. Cameron and Liam Stott, Trees and cycles, arXiv:2010.14902 [math.CO], 2020. See p. 33.
L. Carlitz, Enumeration of two-line arrays, Fib. Quart., 11(2) (1973), 113-130.
F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).
Matteo Cervetti and Luca Ferrari, Pattern avoidance in the matching pattern poset, arXiv:2009.01024 [math.CO], 2020.
W. Y. C. Chen, T. Mansour and S. H. F. Yan, Matchings avoiding partial patterns, arXiv:math/0504342 [math.CO], 2005.
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
J. Cigler, Some remarks about q-Chebyshev polynomials and q-Catalan numbers and related results, arXiv:1312.2767 [math.CO], 2013.
B. Collins, I. Nechita, and K. Zyczkowski, Random graph states, maximal flow and Fuss-Catalan distributions, arXiv:1003.3075 [quant-ph], 2010.
T. C. Copeland, Compositional inverse pairs, the Burgers-Hopf equation, and the Stasheff associahedra, 2014.
T. C. Copeland, Discriminating Deltas, Depressed Equations, and Generalized Catalan Numbers, 2012.
S. J. Cyvin, Jianji Wang, J. Brunvoll, Shiming Cao, Ying Li, B. N. Cyvin, and Yugang Wang, Staggered conformers of alkanes: complete solution of the enumeration problem, J. Molec. Struct. 413-414 (1997), 227-239.
S. J. Cyvin et al., Enumeration of staggered conformers of alkanes and monocyclic cycloalkanes, J. Molec. Struct., 445 (1998), 127-13.
Colin Defant, Catalan Intervals and Uniquely Sorted Permutations, arXiv:1904.02627 [math.CO], 2019.
Colin Defant and N. Kravitz, Stack-sorting for words, arXiv:1809.09158 [math.CO], 2018.
E. Deutsch, S. Feretic and M. Noy, Diagonally convex directed polyominoes and even trees: a bijection and related issues, Discrete Math., 256 (2002), 645-654.
S. Dulucq, Etude combinatoire de problèmes d'énumération, d'algorithmique sur les arbres et de codage par des mots, a thesis presented to l'Université de Bordeaux I, 1987. (Annotated scanned copy)
Jins de Jong, Alexander Hock, and Raimar Wulkenhaar, Catalan tables and a recursion relation in noncommutative quantum field theory, arXiv:1904.11231 [math-ph], 2019.
Emeric Deutsch and M. Noy, Statistics on non-crossing trees, Discrete Math., 254 (2002), 75-87.
R. Dickau, Fuss-Catalan Numbers. Figures of various interpretations.
C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358.
C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358. (Annotated scanned copy)
C. Domb and A. J. Barrett, Notes on Table 2 in "Enumeration of ladder graphs", Discrete Math. 9 (1974), 55. (Annotated scanned copy)
J. A. Eidswick, Short factorizations of permutations into transpositions, Disc. Math. 73 (1989) 239-243
Bryan Ek, Lattice Walk Enumeration, arXiv:1803.10920 [math.CO], 2018.
Bryan Ek, Unimodal Polynomials and Lattice Walk Enumeration with Experimental Mathematics, arXiv:1804.05933 [math.CO], 2018.
I. M. H. Etherington, Non-associate powers and a functional equation, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
I. M. H. Etherington, Some problems of non-associative combinations, Edinburgh Math. Notes, 32 (1940), 1-6.
I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. [Annotated scanned copy]. Part II [not scanned] is by A. Erdelyi and I. M. H. Etherington, and it is on pages vii-xiv of the same issue.
Jishe Feng, The Hessenberg matrices and Catalan and its generalized numbers, arXiv:1810.09170 [math.CO], 2018. See p. 4.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 486.
N. Gabriel, K. Peske, L. Pudwell, and S. Tay, Pattern Avoidance in Ternary Trees, J. Int. Seq. 15 (2012), #12.1.5
I. Gessel and G. Xin, The generating function of ternary trees and continued fractions, arXiv:math/0505217 [math.CO], 2005.
S. Goldstein, J. L. Lebowitz, E. R. Speer, The Discrete-Time Facilitated Totally Asymmetric Simple Exclusion Process, arXiv:2003.04995 [math-ph], 2020.
N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Nancy S.S. Gu and Helmut Prodinger, A bijection between two subfamilies of Motzkin paths, arXiv:2007.02142 [math.CO], 2020.
F. Harary, E. M. Palmer, R. C. Read, On the cell-growth problem for arbitrary polygons, computer printout, circa 1974
Tian-Xiao He, The Vertical Recursive Relation of Riordan Arrays and Its Matrix Representation, J. Int. Seq., Vol. 25 (2022), Article 22.9.5.
T.-X. He, L. W. Shapiro, Fuss-Catalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group, Lin. Alg. Applic. 532 (2017) 25-41, Fuss-Catalan Number (F_3)_n
V. E. Hoggatt, Jr., Letters to N. J. A. Sloane, 1974-1975.
V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
V. E. Hoggatt, Jr. and M. Bicknell, Catalan and related sequences arising from inverses of Pascal's triangle matrices, Fib. Quart., 14 (1976), 395-405.
Vera M. Hur, M. A. Johnson, and J. L. Martin, Oscillation estimates of eigenfunctions via the combinatorics of noncrossing partitions, arXiv:1609.02189 [math.SP], 2016.
Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 53.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 285.
C. Ji and J. Propp, Brussels Sprouts, Noncrossing Trees, and Parking Functions, arXiv:1805.03608 [math.CO], 2018.
J. Jong, A. Hock, and R. Wulkenhaar Catalan tables and a recursion relation in noncommutative quantum field theory, arXiv:1904.11231 [math-ph], 2019.
A. V. Kitaev, Meromorphic Solution of the Degenerate Third Painlevé Equation Vanishing at the Origin, arXiv:1809.00122 [math.CA], 2018.
S. Kitaev and A. de Mier, Enumeration of fixed points of an involution on beta(1, 0)-trees, arXiv:1210.2618 [math.CO], 2012.
Don Knuth, 20th Anniversary Christmas Tree Lecture.
G. Kreweras, Sur les partitions non croisées d'un cycle, (French) Discrete Math. 1(4) (1972), 333-350. MR0309747 (46 #8852).
V. N. Krishnachandran, On the computation of the arcsin function in the Kerala school of astronomy and mathematics, arXiv:2411.08296 [math.HO], 2024. See pp. 3, 13, 25.
D. V. Kruchinin, On solving some functional equations, Advances in Difference Equations (2015), 2015:17.
Dmitry V. Kruchinin and Vladimir V. Kruchinin, A Generating Function for the Diagonal T_{2n,n} in Triangles, Journal of Integer Sequences, 18 (2015), Article 15.4.6.
Markus Kuba and Alois Panholzer, Enumeration formulas for pattern restricted Stirling permutations, Discrete Math. 312(21) (2012), 3179--3194. MR2957938. - From _N. J. A. Sloane_, Sep 25 2012
Wolfdieter Lang, Ternary trees with n = 1, 2, 3 and 4 vertices.
Ho-Hon Leung and Thotsaporn "Aek" Thanatipanonda, A Probabilistic Two-Pile Game, arXiv:1903.03274 [math.CO], 2019.
R. P. Loh, A. G. Shannon, and A. F. Horadam, Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients, preprint, 1980.
Lun Lv and Sabrina X.M. Pang, Reduced Decompositions of Matchings, Electronic Journal of Combinatorics 18 (2011), #P107.
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344, (T_n for s=3).
Hugo Mlodecki, Decompositions of packed words and self duality of Word Quasisymmetric Functions, arXiv:2205.13949 [math.CO], 2022. See Table 4 p. 20.
W. Mlotkowski, M. Nowak, K. Penson, and K. Zyczkowski, Spectral density of generalized Wishart matrices and free multiplicative convolution, arXiv preprint arXiv:1407.1282 [math-ph], 2015.
W. Mlotkowski and K. A. Penson, The probability measure corresponding to 2-plane trees, arXiv:1304.6544 [math.PR], 2013.
Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
Emanuele Munarini, Shifting Property for Riordan, Sheffer and Connection Constants Matrices, Journal of Integer Sequences, 20 (2017), Article 17.8.2.
H. Niederhausen, Catalan Traffic at the Beach, Electronic Journal of Combinatorics, 9 (2002), #R33.
J.-C. Novelli, J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv:1403.5962 [math.CO], 2014.
M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180 (1998), 301-313.
R. N. Onody and U. P. C. Neves, Series Expansion of the Directed Percolation Probability, J. Phys. A 25 (1992), 6609-6615.
A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195.
K. A. Penson and A. I. Solomon, Coherent states from combinatorial sequences, arXiv:quant-ph/0111151, 2001.
K. H. Pilehrood and T. H. Pilehrood, Jacobi Polynomials and Congruences Involving Some Higher-Order Catalan Numbers and Binomial Coefficients, J. Int. Seq. 18 (2015), #15.11.7.
Helmut Prodinger, A simple bijection between a subclass of 2-binary trees and ternary trees, Discrete Mathematics 309(4) (2009), 959-961.
Helmut Prodinger, Generating functions for a lattice path model introduced by Deutsch, arXiv:2004.04215 [math.CO], 2020.
H. Prodinger, S. J. Selkirk, and S. Wagner, On two subclasses of Motzkin paths and their relation to ternary trees, arXiv:1902.01681 [math.CO], 2019; in: Algorithmic Combinatorics - Enumerative Combinatorics, Special Functions and Computer Algebra, Springer. To appear.
Jocelyn Quaintance, Combinatoric Enumeration of Two-Dimensional Proper Arrays, Discrete Math., 307 (2007), 1844-1864.
J. Riordan, Letter, Jul 06 1978.
B. Rittaud, On the Average Growth of Random Fibonacci Sequences, Journal of Integer Sequences, 10 (2007), Article 07.2.4.
A. Schuetz and G. Whieldon, Polygonal Dissections and Reversions of Series, arXiv:1401.7194 [math.CO], 2014.
Makoto Sekiyama, Toshiya Ohtsuki, and Hiroshi Yamamoto, Analytical Solution of Smoluchowski Equations in Aggregation-Fragmentation Processes, Journal of the Physical Society of Japan, 86.10, id 104003 (2017).
Michael Somos, Number Walls in Combinatorics.
B. Sury, Generalized Catalan numbers: linear recursion and divisibility, JIS 12 (2009), #09.7.5
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (5).
N. J. Wildberger and Dean Rubine, A Hyper-Catalan Series Solution to Polynomial Equations, and the Geode, Amer. Math. Monthly (2025). See sections 11.3 and 12.
Aaron Williams, Pattern Avoidance for k-Catalan Sequences, Proc. 21st Int'l Conf. Permutation Patterns (2023).
S. Yakoubov, Pattern Avoidance in Extensions of Comb-Like Posets, arXiv:1310.2979 [math.CO], 2013.
Sheng-Liang Yang, L.-J. Wang, Taylor expansions for the m-Catalan numbers, Australasian Journal of Combinatorics, 64(3) (2016), 420-431.
Anssi Yli-Jyra, On Dependency Analysis via Contractions and Weighted FSTs, in Shall We Play the Festschrift Game?, Springer, 2012, pp. 133-158.
S.-n. Zheng and S.-l. Yang, On the-Shifted Central Coefficients of Riordan Matrices, Journal of Applied Mathematics, Volume 2014, Article ID 848374, 8 pages.
Jian Zhou, Fat and Thin Emergent Geometries of Hermitian One-Matrix Models, arXiv:1810.03883 [math-ph], 2018.
Index entries for "core" sequences
Index entries for sequences related to trees

Cf. A001762, A001763, A002294 - A002296, A006013, A025174, A063548, A064017, A072247, A072248, A134264, A143603, A258708, A256311, A188687 (binomial transform), A346628 (inverse binomial transform).
A column of triangle A102537.
Bisection of A047749 and A047761.
Row sums of triangles A108410 and A108767.
Second column of triangle A062993.
Mod 3 = A113047.
2D Polyominoes: A005034 (oriented), A005036 (unoriented), A369315 (chiral), A047749 (achiral), A000108 {3,oo}, A002293 {5,oo}.
3D Polyominoes: A007173 (oriented), A027610 (unoriented), A371350 (chiral), A371351 (achiral).
Cf. A130564 (for C(k, n) cases).

List([0..25],n->Binomial(3*n,n)/(2*n+1)); # Muniru A Asiru, Oct 31 2018

a001764 n = a001764_list !! n
a001764_list = 1 : [a258708 (2 * n) n | n <- [1..]]
-- Reinhard Zumkeller, Jun 23 2015

[Binomial(3*n,n)/(2*n+1): n in [0..30]]; // Vincenzo Librandi, Sep 04 2014

A001764 := n->binomial(3*n,n)/(2*n+1): seq(A001764(n), n=0..25);
with(combstruct): BB:=[T,{T=Prod(Z,F),F=Sequence(B),B=Prod(F,Z,F)}, unlabeled]:seq(count(BB,size=i),i=0..22); # Zerinvary Lajos, Apr 22 2007
with(combstruct):BB:=[S, {B = Prod(S,S,Z), S = Sequence(B)}, labelled]: seq(count(BB, size=n)/n!, n=0..21); # Zerinvary Lajos, Apr 25 2008
n:=30:G:=series(RootOf(g = 1+x*g^3, g),x=0,n+1):seq(coeff(G,x,k),k=0..n); # Robert FERREOL, Apr 03 2015
alias(PS=ListTools:-PartialSums): A001764List := proc(m) local A, P, n;
A := [1,1]; P := [1]; for n from 1 to m - 2 do P := PS(PS([op(P), P[-1]]));
A := [op(A), P[-1]] od; A end: A001764List(25); # Peter Luschny, Mar 26 2022

InverseSeries[Series[y-y^3, {y, 0, 24}], x] (* then a(n)=y(2n+1)=ways to place non-crossing diagonals in convex (2n+4)-gon so as to create only quadrilateral tiles *) (* Len Smiley, Apr 08 2000 *)
Table[Binomial[3n,n]/(2n+1),{n,0,25}] (* Harvey P. Dale, Jul 24 2011 *)

{a(n) = if( n<0, 0, (3*n)! / n! / (2*n + 1)!)};

{a(n) = if( n<0, 0, polcoeff( serreverse( x - x^3 + O(x^(2*n + 2))), 2*n + 1))};

{a(n) = my(A); if( n<0, 0, A = 1 + O(x); for( m=1, n, A = 1 + x * A^3); polcoeff(A, n))};

b=vector(22);b[1]=1;for(n=2,22,for(i=1,n-1,for(j=1,n-1,for(k=1,n-1,if((i-1)+(j-1)+(k-1)-(n-2),NULL,b[n]=b[n]+b[i]*b[j]*b[k])))));a(n)=b[n+1]; print1(a(0));for(n=1,21,print1(", ",a(n))) \\ Gerald McGarvey, Oct 08 2008

Vec(1 + serreverse(x / (1+x)^3 + O(x^30))) \\ Gheorghe Coserea, Aug 05 2015

from math import comb
def A001764(n): return comb(3*n,n)//(2*n+1) # Chai Wah Wu, Nov 10 2022

def A001764_list(n) :
    D = [0]*(n+1); D[1] = 1
    R = []; b = false; h = 1
    for i in range(2*n) :
        for k in (1..h) : D[k] += D[k-1]
        if not b : R.append(D[h])
        else : h += 1
        b = not b
    return R
A001764_list(22) # Peter Luschny, May 03 2012

From Karol A. Penson, Nov 08 2001: (Start)
G.f.: (2/sqrt(3*x))*sin((1/3)*arcsin(sqrt(27*x/4))).
E.g.f.: hypergeom([1/3, 2/3], [1, 3/2], 27/4*x).
Integral representation as n-th moment of a positive function on [0, 27/4]: a(n) = Integral_{x=0..27/4} (x^n*((1/12) * 3^(1/2) * 2^(1/3) * (2^(1/3)*(27 + 3 * sqrt(81 - 12*x))^(2/3) - 6 * x^(1/3))/(Pi * x^(2/3)*(27 + 3 * sqrt(81 - 12*x))^(1/3)))), n >= 0. This representation is unique. (End)
G.f. A(x) satisfies A(x) = 1+x*A(x)^3 = 1/(1-x*A(x)^2) [Cyvin (1998)]. - Ralf Stephan, Jun 30 2003
a(n) = n-th coefficient in expansion of power series P(n), where P(0) = 1, P(k+1) = 1/(1 - x*P(k)^2).
G.f. Rev(x/c(x))/x, where c(x) is the g.f. of A000108 (Rev=reversion of). - Paul Barry, Mar 26 2010
From Gary W. Adamson, Jul 07 2011: (Start)
Let M = the production matrix:
  1, 1
  2, 2, 1
  3, 3, 2, 1
  4, 4, 3, 2, 1
  5, 5, 4, 3, 2, 1
  ...
a(n) = upper left term in M^n. Top row terms of M^n = (n+1)-th row of triangle A143603, with top row sums generating A006013: (1, 2, 7, 30, 143, 728, ...). (End)
Recurrence: a(0)=1; a(n) = Sum_{i=0..n-1, j=0..n-1-i} a(i)a(j)a(n-1-i-j) for n >= 1 (counts ternary trees by subtrees of the root). - David Callan, Nov 21 2011
G.f.: 1 + 6*x/(Q(0) - 6*x); Q(k) = 3*x*(3*k + 1)*(3*k + 2) + 2*(2*(k^2) + 5*k +3) - 6*x*(2*(k^2) + 5*k + 3)*(3*k + 4)*(3*k + 5)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 27 2011
D-finite with recurrence: 2*n*(2n+1)*a(n) - 3*(3n-1)*(3n-2)*a(n-1) = 0. - R. J. Mathar, Dec 14 2011
REVERT transform of A115140. BINOMIAL transform is A188687. SUMADJ transform of A188678. HANKEL transform is A051255. INVERT transform of A023053. INVERT transform is A098746. - Michael Somos, Apr 07 2012
(n + 1) * a(n) = A174687(n).
G.f.: F([2/3,4/3], [3/2], 27/4*x) / F([2/3,1/3], [1/2], (27/4)*x) where F() is the hypergeometric function. - Joerg Arndt, Sep 01 2012
a(n) = binomial(3*n+1, n)/(3*n+1) = A062993(n+1,1). - Robert FERREOL, Apr 03 2015
a(n) = A258708(2*n,n) for n > 0. - Reinhard Zumkeller, Jun 23 2015
0 = a(n)*(-3188646*a(n+2) + 20312856*a(n+3) - 11379609*a(n+4) + 1437501*a(n+5)) + a(n+1)*(177147*a(n+2) - 2247831*a(n+3) + 1638648*a(n+4) - 238604*a(n+5)) + a(n+2)*(243*a(n+2) + 31497*a(n+3) - 43732*a(n+4) + 8288*a(n+5)) for all integer n. - Michael Somos, Jun 03 2016
a(n) ~ 3^(3*n + 1/2)/(sqrt(Pi)*4^(n+1)*n^(3/2)). - Ilya Gutkovskiy, Nov 21 2016
Given g.f. A(x), then A(1/8) = -1 + sqrt(5), A(2/27) = (-1 + sqrt(3))*3/2, A(4/27) = 3/2, A(3/64) = -2 + 2*sqrt(7/3), A(5/64) = (-1 + sqrt(5))*2/sqrt(5), etc. A(n^2/(n+1)^3) = (n+1)/n if n > 1. - Michael Somos, Jul 17 2018
From Peter Bala, Sep 14 2021: (Start)
A(x) = exp( Sum_{n >= 1} (1/3)*binomial(3*n,n)*x^n/n ).
The sequence defined by b(n) := [x^n] A(x)^n = A224274(n) for n >= 1 and satisfies the congruence b(p) == b(1) (mod p^3) for prime p >= 3. Cf. A060941. (End)
G.f.: 1/sqrt(B(x)+(1-6*x)/(9*B(x))+1/3), with B(x):=((27*x^2-18*x+2)/54-(x*sqrt((-(4-27*x))*x))/(2*3^(3/2)))^(1/3). - Vladimir Kruchinin, Sep 28 2021
x*A'(x)/A(x) = (A(x) - 1)/(- 2*A(x) + 3) = x + 5*x^2 + 28*x^3 + 165*x^4 + ... is the o.g.f. of A025174. Cf. A002293 - A002296. - Peter Bala, Feb 04 2022
a(n) = hypergeom([1 - n, -2*n], [2], 1). Row sums of A108767. - Peter Bala, Aug 30 2023
G.f.: z*exp(3*z*hypergeom([1, 1, 4/3, 5/3], [3/2, 2, 2], (27*z)/4)) + 1.
 - Karol A. Penson, Dec 19 2023
G.f.: hypergeometric([1/3, 2/3], [3/2], (3^3/2^2)*x). See the e.g.f. above. - Wolfdieter Lang, Feb 04 2024
a(n) = (3*n)! / (n!*(2*n+1)!). - Allan Bickle, Feb 20 2024
Sum_{n >= 0} a(n)*x^n/(1 + x)^(3*n+1) = 1. See A316371 and A346627. - Peter Bala, Jun 02 2024
G.f. A(x) satisfies A(x) = 1/A(-x*A(x)^5). - Seiichi Manyama, Jun 16 2025

A003462 a(n) = (3^n - 1)/2.

Original entry on oeis.org

0, 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200, 5230176601, 15690529804, 47071589413, 141214768240, 423644304721, 1270932914164

Offset: 0

N. J. A. Sloane

Partial sums of A000244. Values of base 3 strings of 1's.
a(n) = (3^n-1)/2 is also the number of different nonparallel lines determined by pair of vertices in the n dimensional hypercube. Example: when n = 2 the square has 4 vertices and then the relevant lines are: x = 0, y = 0, x = 1, y = 1, y = x, y = 1-x and when we identify parallel lines only 4 remain: x = 0, y = 0, y = x, y = 1 - x so a(2) = 4. - Noam Katz (noamkj(AT)hotmail.com), Feb 11 2001
Also number of 3-block bicoverings of an n-set (if offset is 1, cf. A059443). - Vladeta Jovovic, Feb 14 2001
3^a(n) is the highest power of 3 dividing (3^n)!. - Benoit Cloitre, Feb 04 2002
Apart from the a(0) and a(1) terms, maximum number of coins among which a lighter or heavier counterfeit coin can be identified (but not necessarily labeled as heavier or lighter) by n weighings. - Tom Verhoeff, Jun 22 2002, updated Mar 23 2017
n such that A001764(n) is not divisible by 3. - Benoit Cloitre, Jan 14 2003
Consider the mapping f(a/b) = (a + 2b)/(2a + b). Taking a = 1, b = 2 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the sequence 1/2, 4/5, 13/14, 40/41, ... converging to 1. Sequence contains the numerators = (3^n-1)/2. The same mapping for N, i.e., f(a/b) = (a + Nb)/(a+b) gives fractions converging to N^(1/2). - Amarnath Murthy, Mar 22 2003
Binomial transform of A000079 (with leading zero). - Paul Barry, Apr 11 2003
With leading zero, inverse binomial transform of A006095. - Paul Barry, Aug 19 2003
Number of walks of length 2*n + 2 in the path graph P_5 from one end to the other one. Example: a(2) = 4 because in the path ABCDE we have ABABCDE, ABCBCDE, ABCDCDE and ABCDEDE. - Emeric Deutsch, Apr 02 2004
The number of triangles of all sizes (not counting holes) in Sierpiński's triangle after n inscriptions. - Lee Reeves (leereeves(AT)fastmail.fm), May 10 2004
Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| = 1 for i = 1, 2, ..., 2*n + 1, s(0) = 1, s(2n+1) = 4. - Herbert Kociemba, Jun 10 2004
Number of non-degenerate right-angled incongruent integer-edged Heron triangles whose circumdiameter is the product of n distinct primes of shape 4k + 1. - Alex Fink and R. K. Guy, Aug 18 2005
Also numerator of the sum of the reciprocals of the first n powers of 3, with A000244 being the sequence of denominators. With the exception of n < 2, the base 10 digital root of a(n) is always 4. In base 3 the digital root of a(n) is the same as the digital root of n. - Alonso del Arte, Jan 24 2006
The sequence 3*a(n), n >= 1, gives the number of edges of the Hanoi graph H_3^{n} with 3 pegs and n >= 1 discs. - Daniele Parisse, Jul 28 2006
Numbers n such that a(n) is prime are listed in A028491 = {3, 7, 13, 71, 103, 541, 1091, ...}. 2^(m+1) divides a(2^m*k) for m > 0. 5 divides a(4k). 5^2 divides a(20k). 7 divides a(6k). 7^2 divides a(42k). 11^2 divides a(5k). 13 divides a(3k). 17 divides a(16k). 19 divides a(18k). 1093 divides a(7k). 41 divides a(8k). p divides a((p-1)/5) for prime p = {41, 431, 491, 661, 761, 1021, 1051, 1091, 1171, ...}. p divides a((p-1)/4) for prime p = {13, 109, 181, 193, 229, 277, 313, 421, 433, 541, ...}. p divides a((p-1)/3) for prime p = {61, 67, 73, 103, 151, 193, 271, 307, 367, ...} = A014753, 3 and -3 are both cubes (one implies other) mod these primes p = 1 mod 6. p divides a((p-1)/2) for prime p = {11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, ...} = A097933(n). p divides a(p-1) for prime p > 7. p^2 divides a(p*(p-1)k) for all prime p except p = 3. p^3 divides a(p*(p-1)*(p-2)k) for prime p = 11. - Alexander Adamchuk, Jan 22 2007
Let P(A) be the power set of an n-element set A. Then a(n) = the number of [unordered] pairs of elements {x,y} of P(A) for which x and y are disjoint [and both nonempty]. Wieder calls these "disjoint usual 2-combinations". - Ross La Haye, Jan 10 2008 [This is because each of the elements of {1, 2, ..., n} can be in the first subset, in the second or in neither. Because there are three options for each, the total number of options is 3^n. However, since the sets being empty is not an option we subtract 1 and since the subsets are unordered we then divide by 2! (The number of ways two objects can be arranged.) Thus we obtain (3^n-1)/2 = a(n). - Chayim Lowen, Mar 03 2015]
Also, still with P(A) being the power set of a n-element set A, a(n) is the number of 2-element subsets {x,y} of P(A) such that the union of x and y is equal to A. Cf. A341590. - Fabio Visonà, Feb 20 2021
Starting with offset 1 = binomial transform of A003945: (1, 3, 6, 12, 24, ...) and double bt of (1, 2, 1, 2, 1, 2, ...); equals polcoeff inverse of (1, -4, 3, 0, 0, 0, ...). - Gary W. Adamson, May 28 2009
Also the constant of the polynomials C(x) = 3x + 1 that form a sequence by performing this operation repeatedly and taking the result at each step as the input at the next. - Nishant Shukla (n.shukla722(AT)gmail.com), Jul 11 2009
It appears that this is A120444(3^n-1) = A004125(3^n) - A004125(3^n-1), where A004125 is the sum of remainders of n mod k for k = 1, 2, 3, ..., n. - John W. Layman, Jul 29 2009
Subsequence of A134025; A171960(a(n)) = a(n). - Reinhard Zumkeller, Jan 20 2010
Let A be the Hessenberg matrix of order n, defined by: A[1,j] = 1, A[i, i] := 3, (i > 1), A[i, i-1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n) = det(A). - Milan Janjic, Jan 27 2010
This is the sequence A(0, 1; 2, 3; 2) = A(0, 1; 4, -3; 0) of the family of sequences [a, b:c, d:k] considered by Gary Detlefs, and treated as A(a, b; c, d; k) in the Wolfdieter Lang link given below. - Wolfdieter Lang, Oct 18 2010
It appears that if s(n) is a first order rational sequence of the form s(0) = 0, s(n) = (2*s(n-1)+1)/(s(n-1)+2), n > 0, then s(n)= a(n)/(a(n)+1). - Gary Detlefs, Nov 16 2010
This sequence also describes the total number of moves to solve the [RED ; BLUE ; BLUE] or [RED ; RED ; BLUE] pre-colored Magnetic Towers of Hanoi puzzle (cf. A183111 - A183125).
From Adi Dani, Jun 08 2011: (Start)
a(n) is number of compositions of odd numbers into n parts less than 3. For example, a(3) = 13 and there are 13 compositions odd numbers into 3 parts < 3:
   1: (0, 0, 1), (0, 1, 0), (1, 0, 0);
   3: (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0), (1, 1, 1);
   5: (1, 2, 2), (2, 1, 2), (2, 2, 1).
(End)
Pisano period lengths:  1, 2, 1, 2, 4, 2, 6, 4, 1, 4, 5, 2, 3, 6, 4, 8, 16, 2, 18, 4, ... . - R. J. Mathar, Aug 10 2012
a(n) is the total number of holes (triangles removed) after the n-th step of a Sierpiński triangle production. - Ivan N. Ianakiev, Oct 29 2013
a(n) solves Sum_{j = a(n) + 1 .. a(n+1)} j = k^2 for some integer k, given a(0) = 0 and requiring smallest a(n+1) > a(n). Corresponding k = 3^n. - Richard R. Forberg, Mar 11 2015
a(n+1) equals the number of words of length n over {0, 1, 2, 3} avoiding 01, 02 and 03. - Milan Janjic, Dec 17 2015
For n >= 1, a(n) is also the total number of words of length n, over an alphabet of three letters, such that one of the letters appears an odd number of times (See A006516 for 4 letter words, and the Balakrishnan reference there). - Wolfdieter Lang, Jul 16 2017
Also, the number of maximal cliques, maximum cliques, and cliques of size 4 in the n-Apollonian network. - Andrew Howroyd, Sep 02 2017
For n > 1, the number of triangles (cliques of size 3) in the (n-1)-Apollonian network. - Andrew Howroyd, Sep 02 2017
a(n) is the largest number that can be represented with n trits in balanced ternary. Correspondingly, -a(n) is the smallest number that can be represented with n trits in balanced ternary. - Thomas König, Apr 26 2020
These form Sierpinski nesting-stars, which alternate pattern on 3^n+1/2 star numbers A003154, based on the square configurations of 9^n. The partial sums of 3^n are delineated according to the geometry of a hexagram, see illustrations in links. (3*a(n-1) + 1) create Sierpinski-anti-triangles, representing the number of holes in a (n+1) Sierpinski triangle (see illustrations). - John Elias, Oct 18 2021
For n > 1, a(n) is the number of iterations necessary to calculate the hyperbolic functions with CORDIC. - Mathias Zechmeister, Jul 26 2022
a(n) is the least number k such that A065363(k) = n. - Amiram Eldar, Sep 03 2022
For all n >= 0, Sum_{k=a(n)+1..a(n+1)} 1/k < Sum_{j=a(n+1)+1..a(n+2)} 1/j. These are the minimal points which partition the infinite harmonic series into a monotonically increasing sequence. Each partition approximates log(3) from below as n tends to infinity. - Joseph Wheat, Apr 15 2023
a(n) is also the number of 3-cycles in the n-Dorogovtsev-Goltsev-Mendes graph (using the convention the 0-Dorogovtsev-Goltsev-Mendes graph is P_2). - Eric W. Weisstein, Dec 06 2023

			There are 4 3-block bicoverings of a 3-set: {{1, 2, 3}, {1, 2}, {3}}, {{1, 2, 3}, {1, 3}, {2}}, {{1, 2, 3}, {1}, {2, 3}} and {{1, 2}, {1, 3}, {2, 3}}.
Ternary........Decimal
0.................0
1.................1
11................4
111..............13
1111.............40 etc. - _Zerinvary Lajos_, Jan 14 2007
There are altogether a(3) = 13 three letter words over {A,B,C} with say, A, appearing an odd number of times: AAA; ABC, ACB, ABB, ACC; BAC, CAB, BAB, CAC; BCA, CBA, BBA, CCA. - _Wolfdieter Lang_, Jul 16 2017

J. G. Mauldon, Strong solutions for the counterfeit coin problem, IBM Research Report RC 7476 (#31437) 9/15/78, IBM Thomas J. Watson Research Center, P. O. Box 218, Yorktown Heights, N. Y. 10598.
Paulo Ribenboim, The Book of Prime Number Records, Springer-Verlag, NY, 2nd ed., 1989, p. 60.
Paulo Ribenboim, The Little Book of Big Primes, Springer-Verlag, NY, 1991, p. 53.
Amir Sapir, The Tower of Hanoi with Forbidden Moves, The Computer J. 47 (1) (2004) 20, case three-in-a row, sequence a(n).
Robert Sedgewick, Algorithms, 1992, pp. 109.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Paolo Xausa, Table of n, a(n) for n = 0..2000 (terms 0..200 from T. D. Noe)
A. Abdurrahman, CM Method and Expansion of Numbers, arXiv:1909.10889 [math.NT], 2019.
Max A. Alekseyev and Toby Berger, Solving the Tower of Hanoi with Random Moves. In: J. Beineke, J. Rosenhouse (eds.) The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Princeton University Press, 2016, pp. 65-79. ISBN 978-0-691-16403-8
Arcytech, The Sierpinski Triangle Fractal.
Andrei Asinowski and Michaela A. Polley, Patterns in rectangulations. Part I: T-like patterns, inversion sequence classes I(010, 101, 120, 201) and I(011, 201), and rushed Dyck paths, arXiv:2501.11781 [math.CO], 2025. See p. 26.
Jean-Luc Baril and Helmut Prodinger, Enumeration of partial Lukasiewicz paths, arXiv:2205.01383 [math.CO], 2022.
Beáta Bényi and Toshiki Matsusaka, Extensions of the combinatorics of poly-Bernoulli numbers, arXiv:2106.05585 [math.CO], 2021.
Göksal Bilgici and Tuncay Deniz Şentürk, Some Addition Formulas for Fibonacci, Pell and Jacobsthal Numbers, Annales Mathematicae Silesianae (2019) Vol. 33, 55-65.
Carlos M. da Fonseca and Anthony G. Shannon, A formal operator involving Fermatian numbers, Notes Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 491-498.
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012
Shaoshi Chen, Hanqian Fang, Sergey Kitaev, and Candice X.T. Zhang, Patterns in Multi-dimensional Permutations, arXiv:2411.02897 [math.CO], 2024. See pp. 17, 26.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
Roger B. Eggleton, Maximal Midpoint-Free Subsets of Integers, International Journal of Combinatorics Volume 2015, Article ID 216475, 14 pages.
John Elias, Sierpinski Nesting Stars, Stars of 3*9^n-1/2, Stars of 9^n-1/2, Sierpinski Anti-Triangles.
Graham Everest, Shaun Stevens, Duncan Tamsett and Tom Ward, Primes generated by recurrence sequences, Amer. Math. Monthly, Vol. 114, No. 5 (2007), pp. 417-431.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 372.
Takao Komatsu, Some recurrence relations of poly-Cauchy numbers, J. Nonlinear Sci. Appl., (2019) Vol. 12, Issue 12, 829-845.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
H. V. Krishna and N. J. A. Sloane, Correspondence, 1975.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
László Németh, The trinomial transform triangle, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also arXiv:1807.07109 [math.NT], 2018.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
D. C. Santos, E. A. Costa, and P. M. M. C. Catarino, On Gersenne Sequence: A Study of One Family in the Horadam-Type Sequence, Axioms 14, 203, (2025). See p. 4.
A. G. Shannon, Letter to N. J. A. Sloane, Dec 06 1974.
Morgan Ward, Note on divisibility sequences, Bull. Amer. Math. Soc., 42 (1936), 843-845.
Eric Weisstein's World of Mathematics, Apollonian Network.
Eric Weisstein's World of Mathematics, Dorogovtsev-Goltsev-Mendes Graph.
Eric Weisstein's World of Mathematics, Graph Cycle.
Eric Weisstein's World of Mathematics, Maximal Clique.
Eric Weisstein's World of Mathematics, Maximum Clique.
Eric Weisstein's World of Mathematics, Mephisto Waltz Sequence.
Eric Weisstein's World of Mathematics, Repunit.
Eric Weisstein's World of Mathematics, Weighing.
Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, Vol. 8 (2008).
K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math., Vol. 3 (1892), 265-284.
Index entries for sequences related to sorting
Index entries for linear recurrences with constant coefficients, signature (4,-3)

Sequences used for Shell sort: A033622, A003462, A036562, A036564, A036569, A055875.
Cf. A179526 (repeats), A113047 (characteristic function).
Cf. A000225, A000392, A004125, A014753, A028491 (indices of primes), A059443 (column k = 3), A065363, A097933, A120444, A321872 (sum reciprocals).
Cf. A064099 (minimal number of weightings to detect lighter or heavier coin among n coins).
Cf. A039755 (column k = 1).
Cf. A006516 (binomial transform, and special 4 letter words).
Cf. A341590.
Cf. A003462(n) (3-cycles), A367967(n) (5-cycles), A367968(n) (6-cycles).

A003462:=List([0..30],n->(3^n-1)/2); # Muniru A Asiru, Sep 27 2017

a003462 = (`div` 2) . (subtract 1) . (3 ^)
a003462_list = iterate ((+ 1) . (* 3)) 0  -- Reinhard Zumkeller, May 09 2012

[(3^n-1)/2: n in [0..30]]; // Vincenzo Librandi, Feb 21 2015

A003462 := n-> (3^n - 1)/2: seq(A003462(n), n=0..30);
A003462:=1/(3*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation

(3^Range[0, 30] - 1)/2 (* Harvey P. Dale, Jul 13 2011 *)
LinearRecurrence[{4, -3}, {0, 1}, 30] (* Harvey P. Dale, Jul 13 2011 *)
Accumulate[3^Range[0, 30]] (* Alonso del Arte, Sep 10 2017 *)
CoefficientList[Series[x/(1 - 4x + 3x^2), {x, 0, 30}], x] (* Eric W. Weisstein, Sep 28 2017 *)
Table[FromDigits[PadRight[{},n,1],3],{n,0,30}] (* Harvey P. Dale, Jun 01 2022 *)

A003462(n):=(3^n - 1)/2$
makelist(A003462(n),n,0,30); /* Martin Ettl, Nov 05 2012 */

PARI
```
a(n)=(3^n-1)/2
```

concat(0, Vec(x/((1-x)*(1-3*x)) + O(x^30))) \\ Altug Alkan, Nov 01 2015

[(3^n - 1)/2 for n in range(0,30)] # Zerinvary Lajos, Jun 05 2009

G.f.: x/((1-x)*(1-3*x)).
a(n) = 4*a(n-1) - 3*a(n-2), n > 1. a(0) = 0, a(1) = 1.
a(n) = 3*a(n-1) + 1, a(0) = 0.
E.g.f.: (exp(3*x) - exp(x))/2. - Paul Barry, Apr 11 2003
a(n+1) = Sum_{k = 0..n} binomial(n+1, k+1)*2^k. - Paul Barry, Aug 20 2004
a(n) = Sum_{i = 0..n-1} 3^i, for n > 0; a(0) = 0.
a(n) = A125118(n, 2) for n > 1. - Reinhard Zumkeller, Nov 21 2006
a(n) = StirlingS2(n+1, 3) + StirlingS2(n+1, 2). - Ross La Haye, Jan 10 2008
a(n) = Sum_{k = 0..n} A106566(n, k)*A106233(k). - Philippe Deléham, Oct 30 2008
a(n) = 2*a(n-1) + 3*a(n-2) + 2, n > 1. - Gary Detlefs, Jun 21 2010
a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3) = 5*a(n-1) - 7*a(n-2) + 3*a(n-3), a(0) = 0, a(1) = 1, a(2) = 4. Observation by G. Detlefs. See the W. Lang comment and link. - Wolfdieter Lang, Oct 18 2010
A008344(a(n)) = 0, for n > 1. - Reinhard Zumkeller, May 09 2012
A085059(a(n)) = 1 for n > 0. - Reinhard Zumkeller, Jan 31 2013
G.f.: Q(0)/2 where Q(k) = 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - 1/(1 - 1/(3*9^k - 27*x*81^k/(9*x*9^k - 1/Q(k+1)))))); (continued fraction ). - Sergei N. Gladkovskii, Apr 12 2013
a(n) = A001065(3^n) where A001065(m) is the sum of the proper divisors of m for positive integer m. - Chayim Lowen, Mar 03 2015
a(n) = A000244(n) - A007051(n) = A007051(n)-1. - Yuchun Ji, Oct 23 2018
Sum_{n>=1} 1/a(n) = A321872. - Amiram Eldar, Nov 18 2020

More terms from Michael Somos
Corrected my comment of Jan 10 2008. - Ross La Haye, Oct 29 2008
Removed comment that duplicated a formula. - Joerg Arndt, Mar 11 2010

cp's OEIS Frontend

A001764 a(n) = binomial(3*n,n)/(2*n+1) (enumerates ternary trees and also noncrossing trees).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Python

Sage

Formula

A003462 a(n) = (3^n - 1)/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

Sage

Formula

Extensions

A113048 Binomial(4n,n)/(3n+1) mod 4.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A253189 Triangle T(n, m)=Sum_{k=1..(n-m)/3} C(m, k)*T((n-m)/3, k), T(n,n)=1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maxima

Formula

A001764 a(n) = binomial(3n,n)/(2n+1) (enumerates ternary trees and also noncrossing trees).