A007123 -id:A007123 - cp's OEIS frontend

A001405 a(n) = binomial(n, floor(n/2)).

1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924, 1716, 3432, 6435, 12870, 24310, 48620, 92378, 184756, 352716, 705432, 1352078, 2704156, 5200300, 10400600, 20058300, 40116600, 77558760, 155117520, 300540195, 601080390, 1166803110

Offset: 0

N. J. A. Sloane

Sperner's theorem says that this is the maximal number of subsets of an n-set such that no one contains another.
When computed from index -1, [seq(binomial(n,floor(n/2)), n = -1..30)]; -> [1,1,1,2,3,6,10,20,35,70,126,...] and convolved with aerated Catalan numbers [seq(((n+1) mod 2)*binomial(n,n/2)/((n/2)+1), n = 0..30)]; -> [1,0,1,0,2,0,5,0,14,0,42,0,132,0,...] shifts left by one: [1,1,2,3,6,10,20,35,70,126,252,...] and if again convolved with aerated Catalan numbers, gives A037952 apart from the initial term. - Antti Karttunen, Jun 05 2001 [This is correct because the g.f.'s satisfy (1+x*g001405(x))*g126120(x) = g001405(x) and g001405(x)*g126120(x) = g037952(x)/x. - R. J. Mathar, Sep 23 2021]
Number of ordered trees with n+1 edges, having nonroot nodes of outdegree 0 or 2. - Emeric Deutsch, Aug 02 2002
Gives for n >= 1 the maximum absolute column sum norm of the inverse of the Vandermonde matrix (a_ij) i=0..n-1, j=0..n-1 with a_00=1 and a_ij=i^j for (i,j) != (0,0). - Torsten Muetze, Feb 06 2004
Image of Catalan numbers A000108 under the Riordan array (1/(1-2x),-x/(1-2x)) or A065109. - Paul Barry, Jan 27 2005
Number of left factors of Dyck paths, consisting of n steps. Example: a(4)=6 because we have UDUD, UDUU, UUDD, UUDU, UUUD and UUUU, where U=(1,1) and D=(1,-1). - Emeric Deutsch, Apr 23 2005
Number of dispersed Dyck paths of length n; they are defined as concatenations of Dyck paths and (1,0)-steps on the x-axis; equivalently, Motzkin paths with no (1,0)-steps at positive height. Example: a(4)=6 because we have HHHH, HHUD, HUDH, UDHH, UDUD, and UUDD, where U=(1,1), H=(1,0), and D=(1,-1). - Emeric Deutsch, Jun 04 2011
a(n) is odd iff n=2^k-1. - Jon Perry, May 05 2005
An inverse Chebyshev transform of binomial(1,n)=(1,1,0,0,0,...) where g(x)->(1/sqrt(1-4*x^2))*g(x*c(x^2)), with c(x) the g.f. of A000108. - Paul Barry, May 13 2005
In a random walk on the number line, starting at 0 and with 0 absorbing after the first step, number of ways of ending up at a positive integer after n steps. - Joshua Zucker, Jul 31 2005
Maximum number of sums of the form Sum_{i=1..n} e(i)*a(i) that are congruent to 0 mod q, where e_i=0 or 1 and gcd(a_i,q)=1, provided that q > ceiling(n/2). - Ralf Stephan, Apr 27 2003
Also the number of standard tableaux of height <= 2. - Mike Zabrocki, Mar 24 2007
Hankel transform of this sequence forms A000012 = [1,1,1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
A001263 * [1, -2, 3, -4, 5, ...] = [1, -1, -2, 3, 6, -10, -20, 35, 70, -126, ...]. - Gary W. Adamson, Jan 02 2008
Equals right border of triangle A153585. - Gary W. Adamson, Dec 28 2008
Second binomial transform of A168491. - Philippe Deléham, Nov 27 2009
a(n) is also the number of distinct strings of length n, each of which is a prefix of a string of balanced parentheses; see example. - Lee A. Newberg, Apr 26 2010
Number of symmetric balanced strings of n pairs of parentheses; see example. - Joerg Arndt, Jul 25 2011
a(n) is the number of permutation patterns modulo 2. - Olivier Gérard, Feb 25 2011
For n >= 2, a(n-1) is the number of incongruent two-color bracelets of 2*n-1 beads, n of which are black (A007123), having a diameter of symmetry. - Vladimir Shevelev, May 03 2011
The number of permutations of n elements where p(k-2) < p(k) for all k. - Joerg Arndt, Jul 23 2011
Also size of the equivalence class of S_{n+1} containing the identity permutation under transformations of positionally adjacent elements of the form abc <--> cba where a < b < c, cf. A210668. - Tom Roby, May 15 2012
a(n) is the number of symmetric Dyck paths of length 2n. - Matt Watson, Sep 26 2012
a(n) is divisible by A000108(floor(n/2)) = abs(A129996(n-2)). - Paul Curtz, Oct 23 2012
a(n) is the number of permutations of length n avoiding both 213 and 231 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014
Number of symmetric standard Young tableaux of shape (n,n). - Ran Pan, Apr 10 2015
From Luciano Ancora, May 09 2015: (Start)
Also "stepped path" in the array formed by partial sums of the all 1's sequence (or a Pascal's triangle displayed as a square). Example:
  [1], [1],  1,    1,    1,     1,    1, ... A000012
   1,  [2], [3],   4,    5,     6,    7, ...
   1,   3,  [6], [10],  15,    21,   28, ...
   1,   4,  10,  [20], [35],   56,   84, ...
   1,   5,  15,   35,  [70], [126], 210, ...
Sequences in second formula are the mixed diagonals shown in this array. (End)
a(n) = A265848(n,n). - Reinhard Zumkeller, Dec 24 2015
The constant Sum_{n >= 0} a(n)/n! is 1 + A130820. - Peter Bala, Jul 02 2016
Number of meanders (walks starting at the origin and ending at any altitude >= 0 that may touch but never go below the x-axis) with n steps from {-1,1}. - David Nguyen, Dec 20 2016
a(n) is also the number of paths of n steps (either up or down by 1) that end at the maximal value achieved along the path. - Winston Luo, Jun 01 2017
Number of binary n-tuples such that the number of 1's in the even positions is the same as the number of 1's in the odd positions. - Juan A. Olmos, Dec 21 2017
Equivalently, a(n) is the number of subsets of {1,...,n} containing as many even numbers as odd numbers. - Gus Wiseman, Mar 17 2018
a(n) is the number of Dyck paths with semilength = n+1, returns to the x-axis = floor((n+3)/2) and up movements in odd positions = floor((n+3)/2).  Example: a(4)=6, U=up movement in odd position, u=up movement in even position, d=down movement, -=return to x-axis: Uududd-Ud-Ud-, Ud-Uudd-Uudd-, Uudd-Uudd-Ud-, Ud-Ud-Uududd-, Uudd-Ud-Uudd-, Ud-Uududd-Ud-. - Roger Ford, Dec 29 2017
Let C_n(R, H) denote the transition matrix from the ribbon basis to the homogeneous basis of the graded component of the algebra of noncommutative symmetric functions of order n. Letting I(2^(n-1)) denote the identity matrix of order 2^(n-1), it has been conjectured that the dimension of the kernel of C_n(R, H) - I(2^(n-1)) is always equal to a(n-1). - John M. Campbell, Mar 30 2018
The number of U-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are U-equivalent iff the positions of pattern U are identical in these paths. - Sergey Kirgizov, Apr 08 2018
All binary self-dual codes of length 2n, for n > 0, must contain at least a(n) codewords of weight n. More to the point, there will always be at least one, perhaps unique, binary self-dual code of length 2n that will contain exactly a(n) codewords that have a hamming weight equal to half the length of the code (n). This code can be constructed by direct summing the unique binary self-dual code of length 2 (up to permutation equivalence) to itself n times. A permutation equivalent code can be constructed by augmenting two identity matrices of length n together. - Nathan J. Russell, Nov 25 2018
Closed under addition. - Torlach Rush, Apr 18 2019
The sequence starting (1, 2, 3, 6, ...) is the invert transform of A097331: (1, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, ...). - Gary W. Adamson, Feb 22 2020
From Gary W. Adamson, Feb 24 2020: (Start)
The sequence is the culminating limit of an infinite set of sequences with convergents of 2*cos(Pi/N), N = (3, 5, 7, 9, ...).
The first few such sequences are:
N = 3: (1,  1,  1,  1,  1,  1,  1,  1, ...)
N = 5: (1,  1,  2,  3,  5,  8, 13, 21, ...) = A000045
N = 7: (1,  1,  2,  3,  6, 10, 19, 33, ...) = A028495, a(n)/a(n-1) tends to 1.801937...
N = 9  (1,  1,  2,  3,  6, 10, 20, 35, ...) = A061551, a(n)/a(n_1) tends to 1.879385...
...
In the limit one gets the current sequence with ratio 2. (End)
a(n) is also the number of monotone lattice paths from (0,0) to (floor(n/2),ceiling(n/2)). These are the number of Grand Dyck paths when n is even. - Nachum Dershowitz, Aug 12 2020
The maximum number of preimages that a permutation of length n+1 can have under the consecutive-132-avoiding stack-sorting map. - Colin Defant, Aug 28 2020
Counts faro permutations of length n. Faro permutations are permutations avoiding the three consecutive patterns 231, 321 and 312. They are obtained by a perfect faro shuffle of two nondecreasing words of lengths differing by at most one. - Sergey Kirgizov, Jan 12 2021
Per "Sperner's Theorem", the largest possible familes of finite sets none of which contain any other sets in the family. - Renzo Benedetti, May 26 2021
a(n-1) are the incomplete, primitive Dyck paths of n steps without a first return: paths of U and D steps starting at the origin, never touching the horizontal axis later on, and ending above the horizontal axis. n=1: {U}, n=2: {UU}, n=3: {UUU, UUD}, n=4: {UUUU, UUUD, UUDU}, n=5: {UUUUU, UUUUD, UUUDD, UUDUU, UUUDU, UUDUD}. For comparison: A037952 counts incomplete Dyck paths with n steps with any number of intermediate returns to the horizontal axis, ending above the horizontal axis. - R. J. Mathar, Sep 24 2021
a(n) is the number of noncrossing partitions of [n] whose nontrivial blocks are of type {a,b}, with a <= n/2, b > n/2. - Francesca Aicardi, May 29 2022
Maximal coefficient of (1+x)^n. - Vaclav Kotesovec, Dec 30 2022
Sums of lower-left-to-upper-right diagonals of the Catalan Triangle A001263. - Howard A. Landman, Sep 16 2024

			For n = 4, the a(4) = 6 distinct strings of length 4, each of which is a prefix of a string of balanced parentheses, are ((((, (((), (()(, ()((, ()(), and (()). - _Lee A. Newberg_, Apr 26 2010
There are a(5)=10 symmetric balanced strings of 5 pairs of parentheses:
[ 1] ((((()))))
[ 2] (((()())))
[ 3] ((()()()))
[ 4] ((())(()))
[ 5] (()()()())
[ 6] (()(())())
[ 7] (())()(())
[ 8] ()()()()()
[ 9] ()((()))()
[10] ()(()())() - _Joerg Arndt_, Jul 25 2011
G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 20*x^6 + 35*x^7 + 70*x^8 + ...
The a(4)=6 binary 4-tuples such that the number of 1's in the even positions is the same as the number of 1's in the odd positions are 0000, 1100, 1001, 0110, 0011, 1111. - _Juan A. Olmos_, Dec 21 2017

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999; see p. 135.
K. Engel, Sperner Theory, Camb. Univ. Press, 1997; Theorem 1.1.1.
P. Frankl, Extremal sets systems, Chap. 24 of R. L. Graham et al., eds, Handbook of Combinatorics, North-Holland.
J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.16(b), p. 452.

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0 to 200 computed by T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math., Series 55, Tenth Printing, 1972.
M. Aigner, Enumeration via ballot numbers, Discrete Math., Vol. 308 (2008), pp. 2544-2563.
A. Asinowski and G. Rote, Point sets with many non-crossing matchings, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics, Volume 332 (October 2014), Pages 45-54.
Axel Bacher, Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths, arXiv:1802.06030 [cs.DS], 2018.
Armen G. Bagdasaryan and Ovidiu Bagdasar, On some results concerning generalized arithmetic triangles, Electronic Notes in Discrete Mathematics, Vol. 67 (2018), pp. 71-77.
Taylor Ball, David Galvin, Katie Hyry, and Kyle Weingartner, Independent set and matching permutations, arXiv:1901.06579 [math.CO], 2019.
C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv preprint arXiv:1609.06473 [math.CO], 2016.
Elena Barcucci, Antonio Bernini, and Renzo Pinzani, Exhaustive generation of positive lattice paths, Semantic Sensor Networks Workshop 2018, CEUR Workshop Proceedings (2018) Vol. 2113.
Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
Jean-Luc Baril and A. Petrossian, Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two, J. Int. Seq., Vol. 18 (2015), Article 15.7.1.
Jean-Luc Baril, Alexander Burstein, and Sergey Kirgizov, Pattern statistics in faro words and permutations, arXiv:2010.06270 [math.CO], 2020. See Table 1.
Paul Barry, A Note on a One-Parameter Family of Catalan-Like Numbers, JIS, Vol. 12 (2009), Article 09.5.4.
Paul Barry, The Central Coefficients of a Family of Pascal-like Triangles and Colored Lattice Paths, J. Int. Seq., Vol. 22 (2019), Article 19.1.3.
Paul Barry and A. Hennessy, Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays, Journal of Integer Sequences, Vol. 15 (2012), Article 12.4.2. - From _N. J. A. Sloane_, Sep 21 2012
F. Bergeron, L. Favreau and D. Krob, Conjectures on the enumeration of tableaux of bounded height, Discrete Math, Vol. 139, No. 1-3 (1995), pp. 463-468.
Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003 [math.CO], 2013.
A. Bostan, Computer Algebra for Lattice Path Combinatorics, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.
Alin Bostan and Manuel Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2009.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
Henry Bottomley, Illustration of initial terms.
J. M. Campbell, The expansion of immaculate functions in the ribbon basis, Discrete Math., Vol. 340 (2017), pp. 1716-1726.
Colin Defant and Kai Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
F. Disanto, A. Frosini, and S. Rinaldi, Square involutions, J. Int. Seq. 14 (2011) # 11.3.5.
F. Disanto and S. Rinaldi, Symmetric convex permutominoes and involutions, PU. M. A., Vol. 22, No. 1 (2011), pp. 39-60.
Justine Falque, Jean-Christophe Novelli, and Jean-Yves Thibon, Pinnacle sets revisited, arXiv:2106.05248 [math.CO], 2021.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 77.
J. R. Griggs, On the distribution of sums of residues, arXiv:math/9304211 [math.NT], 1993.
O. Guibert and T. Mansour, Restricted 132-involutions, Séminaire Lotharingien de Combinatoire, B48a, 23 pp, 2002.
H. Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., Vol. 10, No. 8 (1979), pp. 964-999.
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seq., Vol. 3 (2000), Article 00.1.6.
Zachary Hamaker and Eric Marberg, Atoms for signed permutations, arXiv:1802.09805 [math.CO], 2018.
F. Harary and R. W. Robinson, The number of achiral trees, Jnl. Reine Angewandte Mathematik, Vol. 278 (1975), pp. 322-335. (Annotated scanned copy)
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct 2011.
Zoe M. Himwich and Noah A. Rosenberg, Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees, arXiv:1901.04465 [q-bio.pE] (2019); Adv. Appl. Math. 113 (2020), 101939.
Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657 [math.CO], 2014.
W. Cary Huffman and Vera Pless, Fundamentals of Error Correcting Codes, Cambridge University Press, 2003, Pages 7, 252-282, 338-393.
Christian Krattenthaler and Daniel Yaqubi, Some determinants of path generating functions, II, Adv. Appl. Math., Vol. 101 (2018), pp. 232-265.
Jean-Philippe Labbé and Carsten Lange, Cambrian acyclic domains: counting c-singletons, arXiv:1802.07978 [math.CO], 2018.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
P. Leroux and E. Rassart, Enumeration of Symmetry Classes of Parallelogram Polyominoes, arXiv:math/9901135 [math.CO], 1999.
Steven Linton, James Propp, Tom Roby, and Julian West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, Journal of Integer Sequences, Vol. 15 (2012), Article 12.9.1.
D. Lubell, A short proof of Sperner's lemma, J. Combin. Theory, Vol. 1 (1966), p. 299.
Piera Manara and Claudio Perelli Cippo, The fine structure of 4321 avoiding involutions and 321 avoiding involutions, PU. M. A. Vol. 22 (2011), pp. 227-238.
Eric Marberg and Brendan Pawlowski, Stanley symmetric functions for signed involutions, arXiv:1806.11208 [math.CO], 2018.
Victor Meally, Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.
D. Merlini, Generating functions for the area below some lattice paths, Discrete Mathematics and Theoretical Computer Science AC, 2003, 217-228.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
M. A. Narcowich, Problem 73-6, SIAM Review, Vol. 16, No. 1, 1974, p. 97.
Ran Pan, Exercise P, Project P.
Saulo Queiroz, João Vilela, and Edmundo Monteiro, What is the Cost of the Index Selector Task for OFDM with Index Modulation?, 2019 Wireless Days (WD).
Saulo Queiroz, João P. Vilela, and Edmundo Monteiro, Optimal Mapper for OFDM with Index Modulation: A Spectro-Computational Analysis, arXiv:2002.09382 [eess.SP], 2020. See also IEEE Access (2020) Vol. 8, 68365-68378.
Alon Regev, Amitai Regev, and Doron Zeilberger, Identities in character tables of S_n, arXiv preprint arXiv:1507.03499 [math.CO], 2015.
R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron, Vol. 32, No. 3 (1976), pp. 355-361. (Annotated scanned copy)
Arnold Saunders, A Class of Random Recursive Tree Algorithms with Deletion, arXiv:1906.02720 [math.PR], 2019.
V. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., Vol. 35, No. 5 (2004), pp. 629-638.
V. Shevelev, A problem of enumeration of two-color bracelets with several variations, arXiv:0710.1370 [math.CO], May 05 2011.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
Emanuel Sperner, Ein Satz über Untermengen einer endlichen Menge, Mathematische Zeitschrift (in German), Vol. 27, No. 1 (1928), pp. 544-548.
P. K. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
P. J. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974. [Scanned annotated and corrected copy]
I. Tasoulas, K. Manes, A. Sapounakis, and P. Tsikouras, Chains with Small Intervals in the Lattice of Binary Paths, arXiv:1911.10883 [math.CO], 2019.
C. G. Wagner, Letter to N. J. A. Sloane, Sep 30 1974.
Eric Weisstein's World of Mathematics, Central Binomial Coefficient.
Eric Weisstein's World of Mathematics, Quota System.
W. H. W. Wong and E. G. Tay, On Cross-intersecting Sperner Families, arXiv:2001.01910 [math.CO], 2020.
Index entries for sequences of k-nomial coefficients
Index entries for "core" sequences.

Row sums of Catalan triangle A053121 and of symmetric Dyck paths A088855.
Enumerates the structures encoded by A061854 and A061855.
First differences are in A037952.
Apparently a(n) = lim_{k->infinity} A094718(k, n).
Partial sums are in A036256. Column k=2 of A182172. Column k=1 of A335570.
Bisections: A000984 (even part), A001700 (odd part).
Cf. A000712, A001006, A001700, A005773, A005817, A007578, A007579, A022916, A022917 (permutation patterns mod k), A049401, A051920, A063886, A130820, A132815, A153585, A239241, A265848.
Cf. A097331.
Cf. A000045, A028495, A061551
Cf. A107373, A340567, A340568, A340569 (popularity of certain patterns in faro permutations).

List([0..40],n->Binomial(n,Int(n/2))); # Muniru A Asiru, Apr 08 2018

a001405 n = a007318_row n !! (n `div` 2) -- Reinhard Zumkeller, Nov 09 2011

[Binomial(n, Floor(n/2)): n in [0..40]]; // Vincenzo Librandi, Nov 16 2014

A001405 := n->binomial(n, floor(n/2)): seq(A001405(n), n=0..33);

Table[Binomial[n, Floor[n/2]], {n, 0, 40}] (* Stefan Steinerberger, Apr 08 2006 *)
Table[DifferenceRoot[Function[{a,n},{-4 n a[n]-2 a[1+n]+(2+n) a[2+n] == 0,a[1] == 1,a[2] == 1}]][n], {n, 30}] (* Luciano Ancora, Jul 08 2015 *)
Array[Binomial[#,Floor[#/2]]&,40,0] (* Harvey P. Dale, Mar 05 2018 *)

A001405(n):=binomial(n,floor(n/2))$
makelist(A001405(n),n,0,30); /* Martin Ettl, Nov 01 2012 */

PARI
```
a(n) = binomial(n, n\2);
```

first(n) = x='x+O('x^n); Vec((-1+2*x+sqrt(1-4*x^2))/(2*x-4*x^2)) \\ Iain Fox, Dec 20 2017 (edited by Iain Fox, May 07 2018)

from math import comb
def A001405(n): return comb(n,n//2) # Chai Wah Wu, Jun 07 2022

a(n) = max_{k=0..n} binomial(n, k).
a(2*n) = A000984(n), a(2*n+1) = A001700(n).
By symmetry, a(n) = binomial(n, ceiling(n/2)). - Labos Elemer, Mar 20 2003
P-recursive with recurrence: a(0) = 1, a(1) = 1, and for n >= 2, (n+1)*a(n) = 2*a(n-1) + 4*(n-1)*a(n-2). - Peter Bala, Feb 28 2011
G.f.: (1+x*c(x^2))/sqrt(1-4*x^2) = 1/(1 - x - x^2*c(x^2)); where c(x) = g.f. for Catalan numbers A000108.
G.f.: (-1 + 2*x + sqrt(1-4*x^2))/(2*x - 4*x^2). - Lee A. Newberg, Apr 26 2010
G.f.: 1/(1 - x - x^2/(1 - x^2/(1 - x^2/(1 - x^2/(1 - ... (continued fraction). - Paul Barry, Aug 12 2009
a(0) = 1; a(2*m+2) = 2*a(2*m+1); a(2*m+1) = Sum_{k = 0..2*m} (-1)^k*a(k)*a(2*m-k). - Len Smiley, Dec 09 2001
G.f.: (sqrt((1+2*x)/(1-2*x)) - 1)/(2*x). - Vladeta Jovovic, Apr 28 2003
The o.g.f. A(x) satisfies A(x) + x*A^2(x) = 1/(1-2*x). - Peter Bala, Feb 28 2011
E.g.f.: BesselI(0, 2*x) + BesselI(1, 2*x). - Vladeta Jovovic, Apr 28 2003
a(0) = 1; a(2*m+2) = 2*a(2*m+1); a(2*m+1) = 2*a(2*m) - c(m), where c(m)=A000108(m) are the Catalan numbers. - Christopher Hanusa (chanusa(AT)washington.edu), Nov 25 2003
a(n) = Sum_{k=0..n} (-1)^k*2^(n-k)*binomial(n, k)*A000108(k). - Paul Barry, Jan 27 2005
a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)*binomial(1, n-2*k). - Paul Barry, May 13 2005
From Paul Barry, Nov 02 2004: (Start)
a(n) = Sum_{k=0..floor((n+1)/2)} (binomial(n+1, k)*(cos((n-2*k+1)*Pi/2) + sin((n-2*k+1)*Pi/2))).
a(n) = Sum_{k=0..n+1}, (binomial(n+1, (n-k+1)/2)*(1-(-1)^(n-k))*(cos(k*Pi/2) + sin(k*Pi))/2). (End)
a(n) = Sum_{k=floor(n/2)..n} (binomial(n,n-k) - binomial(n,n-k-1)). - Paul Barry, Sep 06 2007
Inverse binomial transform of A005773 starting (1, 2, 5, 13, 35, 96, ...) and double inverse binomial transform of A001700. Row sums of triangle A132815. - Gary W. Adamson, Aug 31 2007
a(n) = Sum_{k=0..n} A120730(n,k). - Philippe Deléham, Oct 16 2008
a(n) = Sum_{k = 0..floor(n/2)} (binomial(n,k) - binomial(n,k-1)). - Nishant Doshi (doshinikki2004(AT)gmail.com), Apr 06 2009
Sum_{n>=0} a(n)/10^(n+1) = 0.1123724... = (sqrt(3)-sqrt(2))/(2*sqrt(2)); Sum_{n>=0} a(n)/100^(n+1) = 0.0101020306102035... = (sqrt(51)-sqrt(49))/(2*sqrt(49)). - Mark Dols, Jul 15 2010
Conjectured: a(n) = 2^n*2F1(1/2,-n;2;2), useful for number of paths in 1-d for which the coordinate is never negative. - Benjamin Phillabaum, Feb 20 2011
a(2*m+1) = (2*m+1)*a(2*m)/(m+1), e.g., a(7) = (7/4)*a(6) = (7/4)*20 = 35. - Jon Perry, Jan 20 2011
From Peter Bala, Feb 28 2011: (Start)
Let F(x) be the logarithmic derivative of the o.g.f. A(x). Then 1+x*F(x) is the o.g.f. for A027306.
Let G(x) be the logarithmic derivative of 1+x*A(x). Then x*G(x) is the o.g.f. for A058622. (End)
Let M = an infinite tridiagonal matrix with 1's in the super and subdiagonals and [1,0,0,0,...] in the main diagonal; and V = the vector [1,0,0,0,...]. a(n) = M^n*V, leftmost term. - Gary W. Adamson, Jun 13 2011
Let M = an infinite tridiagonal matrix with 1's in the super and subdiagonals and [1,0,0,0,...] in the main diagonal. a(n) = M^n_{1,1}. - Corrected by Gary W. Adamson, Jan 30 2012
a(n) = A007318(n, floor(n/2)). - Reinhard Zumkeller, Nov 09 2011
a(n+1) = Sum_{k=0..n} a(n-k)*A097331(k) = a(n) + Sum_{k=0..(n-1)/2} A000108(k)*a(n-2*k-1). - Philippe Deléham, Nov 27 2011
a(n) = A214282(n) - A214283(n), for n > 0. - Reinhard Zumkeller, Jul 14 2012
a(n) = Sum_{k=0..n} A168511(n,k)*(-1)^(n-k). - Philippe Deléham, Mar 19 2013
a(n+2*p-2) = Sum_{k=0..floor(n/2)} A009766(n-k+p-1, k+p-1) + binomial(n+2*p-2, p-2), for p >= 1. - Johannes W. Meijer, Aug 02 2013
O.g.f.: (1-x*c(x^2))/(1-2*x), with the o.g.f. c(x) of Catalan numbers A000108. See the rewritten formula given by Lee A. Newberg above. This is the o.g.f. for the row sums the Riordan triangle A053121. - Wolfdieter Lang, Sep 22 2013
a(n) ~ 2^n / sqrt(Pi * n/2). - Charles R Greathouse IV, Oct 23 2015
a(n) = 2^n*hypergeom([1/2,-n], [2], 2). - Vladimir Reshetnikov, Nov 02 2015
a(2*k) = Sum_{i=0..k} binomial(k, i)*binomial(k, i), a(2*k+1) = Sum_{i=0..k} binomial(k+1, i)*binomial(k, i). - Juan A. Olmos, Dec 21 2017
a(0) = 1, a(n) = 2 * a(n-1) for even n, a(n) = (2*n/(n+1)) * a(n-1) for odd n. - James East, Sep 25 2019
a(n) = A037952(n) + A000108(n/2) where A(.)=0 for non-integer argument. - R. J. Mathar, Sep 23 2021
From Amiram Eldar, Mar 10 2022: (Start)
Sum_{n>=0} 1/a(n) = 2*Pi/(3*sqrt(3)) + 2.
Sum_{n>=0} (-1)^n/a(n) = 2/3 - 2*Pi/(9*sqrt(3)). (End)
For k>2, Sum_{n>=0} a(n)/k^n = (sqrt((k+2)/(k-2)) - 1)*k/2. - Vaclav Kotesovec, May 13 2022
From Peter Bala, Mar 24 2023: (Start)
a(n) = Sum_{k = 0..n+1} (-1)^(k+binomial(n+2,2)) * k/(n+1) * binomial(n+1,k)^2.
(n + 1)*(2*n - 1)*a(n) = (-1)^(n+1)*2*a(n-1) + 4*(n - 1)*(2*n + 1)*a(n-2) with a(0) = a(1) = 1. (End)
a(n) = Integral_{x=-2..2} x^n*W(x)*dx, n>=0, where W(x) = sqrt((2+x)/(2-x))/(2*Pi) is a positive function on x=(-2,2) and is singular at x = 2. Therefore a(n) is a positive definite sequence. - Karol A. Penson, May 12 2025

A007595 a(n) = C_n / 2 if n is even or ( C_n + C_((n-1)/2) ) / 2 if n is odd, where C = Catalan numbers (A000108).

Original entry on oeis.org

1, 1, 3, 7, 22, 66, 217, 715, 2438, 8398, 29414, 104006, 371516, 1337220, 4847637, 17678835, 64823110, 238819350, 883634026, 3282060210, 12233141908, 45741281820, 171529836218, 644952073662, 2430973304732, 9183676536076, 34766775829452, 131873975875180

Offset: 1

N. J. A. Sloane

Number of necklaces of 2 colors with 2n beads and n-1 black ones. - Wouter Meeussen, Aug 03 2002
Number of rooted planar binary trees up to reflection (trees with n internal nodes, or a total of 2n+1 nodes). - Antti Karttunen, Aug 19 2002
Number of even permutations avoiding 132.
Number of Dyck paths of length 2n having an even number of peaks at even height. Example: a(3)=3 because we have UDUDUD, U(UD)(UD)D and UUUDDD, where U=(1,1), D=(1,-1) and the peaks at even height are shown between parentheses. - Emeric Deutsch, Nov 13 2004
Number of planar trees (A002995) on n edges with one distinguished edge. - David Callan, Oct 08 2005
Assuming offset 0 this is an analog of A275165: pairs of two Catalan nestings with index sum n. - R. J. Mathar, Jul 19 2016

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..200
Peter J. Cameron, Some treelike objects Quart. J. Math. Oxford Ser., Vol. 38, No. 2 (1987), pp. 155-183. Note that line 3 on p. 163 has a typo. - _N. J. A. Sloane_, Apr 18 2014
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seq., Vol. 3 (2000), Article 00.1.5.
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), Article 16.2.4.
Andrew Gainer-Dewar, Pólya theory for species with an equivariant group action, arXiv preprint arXiv:1401.6202 [math.CO], 2014.
Toufik Mansour, Counting occurrences of 132 in an even permutation, arXiv:math/0211205 [math.CO], 2002.
Krishna Menon and Anurag Singh, Grassmannian permutations avoiding identity, arXiv:2212.13794 [math.CO], 2022.

a(n) = A047996(2*n, n-1) for n >= 1 and a(n) = A072506(n, n-1) for n >= 2.
Occurs in A073201 as rows 0, 2, 4, etc. (with a(0)=1 included).
Cf. also A003444, A007123.
Cf. A000108, A000150, A334843.

A007595 := n -> (1/2)*(Cat(n) + (`mod`(n,2)*Cat((n-1)/2))); Cat := n -> binomial(2*n,n)/(n+1);

Table[(Plus@@(EulerPhi[ # ]Binomial[2n/#, (n-1)/# ] &)/@Intersection[Divisors[2n], Divisors[n-1]])/(2n), {n, 2, 32}] (* or *) Table[If[EvenQ[n], CatalanNumber[n]/2, (CatalanNumber[n] + CatalanNumber[(n-1)/2])/2], {n, 24}]
Table[(CatalanNumber[n] + 2^n Binomial[1/2, (n + 1)/2] Sin[Pi n/2])/2, {n, 1, 20}] (* Vladimir Reshetnikov, Oct 03 2016 *)
Table[If[EvenQ[n],CatalanNumber[n]/2,(CatalanNumber[n]+CatalanNumber[(n-1)/2])/2],{n,30}] (* Harvey P. Dale, Sep 06 2021 *)

catalan(n) = binomial(2*n, n)/(n+1);
a(n) = if (n % 2, (catalan(n) + catalan((n-1)/2))/2, catalan(n)/2); \\ Michel Marcus, Jan 23 2016

G.f.: (2-2*x-sqrt(1-4*x)-sqrt(1-4*x^2))/x/4. - Vladeta Jovovic, Sep 26 2003
D-finite with recurrence: n*(n+1)*a(n) -6*n*(n-1)*a(n-1) +4*(2*n^2-10*n+9)*a(n-2) +8*(n^2+n-9)*a(n-3) -48*(n-3)*(n-4)*a(n-4) +32*(2*n-9)*(n-5)*a(n-5)=0. - R. J. Mathar, Jun 03 2014, adapted to offset Feb 20 2020
a(n) ~ 4^n /(2*sqrt(Pi)*n^(3/2)). - Ilya Gutkovskiy, Jul 19 2016
a(2n) = A000150(2n). - R. J. Mathar, Jul 19 2016
a(n) = (A000108(n) + 2^n * binomial(1/2, (n+1)/2) * sin(Pi*n/2))/2. - Vladimir Reshetnikov, Oct 03 2016
Sum_{n>=1} a(n)/4^n = (3-sqrt(3))/2 (A334843). - Amiram Eldar, Mar 20 2022

Description corrected by Reiner Martin and Wouter Meeussen, Aug 04 2002

A073201 Array of cycle count sequences for the table A073200.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 7, 4, 1, 1, 1, 22, 11, 3, 1, 1, 1, 66, 31, 7, 2, 1, 1, 1, 217, 96, 22, 4, 3, 1, 1, 1, 715, 305, 66, 11, 7, 2, 1, 1, 1, 2438, 1007, 217, 30, 22, 4, 2, 2, 1, 1, 8398, 3389, 715, 93, 66, 11, 3, 5, 1, 1, 1, 29414, 11636, 2438, 292, 217, 30, 6, 14, 2, 2, 1, 1

Offset: 0

Antti Karttunen, Jun 25 2002

Each row of this table gives the counts of separate orbits/cycles to which the Catalan bijection given in the corresponding row of A073200 partitions each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Note that for involutions (self-inverse Catalan bijections) this is always (A000108(n)+Affffff(n))/2, where Affffff is the corresponding "fix-count sequence" from the table A073202.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Only the first known occurrence(s) given (marked with ? if not yet proved/unclear): rows 0, 2, 4, etc.: A007595, Row 1: A073191, Rows 6 (& 8): A073431, Row 7: A000108, Rows 12, 14, 20, ...: A057513, Rows 16, 18, ...: A003239, Row 57, ..., 164: A007123, Row 168: A073193, Row 261: A002995, Row 2614: A057507, Row 2618 (?), row 17517: A001683.

A085161 Involution of natural numbers induced by Catalan Automorphism *A085161 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 6, 5, 8, 9, 17, 14, 12, 21, 11, 20, 16, 10, 18, 19, 15, 13, 22, 23, 45, 37, 31, 58, 28, 54, 42, 26, 49, 51, 40, 35, 63, 25, 48, 39, 34, 62, 30, 57, 44, 24, 46, 56, 38, 32, 59, 33, 61, 53, 29, 55, 47, 43, 27, 50, 60, 52, 41, 36, 64, 65, 129, 107, 87, 170

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This automorphism reflects the interpretations (pp)-(rr) of Stanley, obtained from the Dyck paths with the "rising slope mapping" illustrated on the example lines.

			Map the Dyck paths (Stanley's interpretation (i)) to noncrossing Murasaki-diagrams (Stanley's interpretation (rr)) by drawing a vertical line above each rising slope / and connect those vertical lines that originate from the same height without any lower valleys between, as in illustration below:
..................................................
...._____..___....................................
...|.|...||...|...................................
...|.||..|||..|...................._.___...___....
...|.||..|||..|...................|.|...|.|...|...
...|.||..||/\.|....i.e..equal.to..|.|.|.|.|.|.|...
...|.|/\.|/..\/\..................|.|.|.|.|.|.|...
.../\/..\/......\.................|.|.|.|.|.|.|...
...10110011100100=11492=A014486(250)..............
...()(())((())()).................................
Now this automorphism gives the parenthesization such that the corresponding Murasaki-diagram is a reflection of the original one:
....___.._____....................................
...|...||...|.|...................................
...||..|||..|.|....................___..._____....
...||..|||..|.|...................|...|.|...|.|...
...||..||/\.|.|....i.e..equal.to..|.|.|.|.|.|.|...
...|/\.|/..\/\/\..................|.|.|.|.|.|.|...
.../..\/........\.................|.|.|.|.|.|.|...
...11001110010100=13204=A014486(360)..............
...(())((())()()).................................
So we have A085161(250)=360 and A085161(360)=250.

A. Karttunen, Catalan Automorphisms
R. P. Stanley, Exercises on Catalan and Related Numbers (including 66 combinatorial interpretations)
Index entries for signature-permutations induced by Catalan automorphisms

a(n) = A085163(A057508(n)) = A074684(A057164(A074683(n))). Occurs in A073200. Cf. also A085159, A085160, A085162, A085175. Alternative mappings illustrated in A086431 & A085169.

Number of cycles: A007123. Number of fixed points: A001405 (in each range limited by A014137 and A014138).

A291883 Number T(n,k) of symmetrically unique Dyck paths of semilength n and height k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 3, 1, 0, 1, 9, 11, 4, 1, 0, 1, 19, 31, 19, 5, 1, 0, 1, 35, 91, 69, 29, 6, 1, 0, 1, 71, 250, 252, 127, 41, 7, 1, 0, 1, 135, 690, 855, 540, 209, 55, 8, 1, 0, 1, 271, 1863, 2867, 2117, 1005, 319, 71, 9, 1, 0, 1, 527, 5017, 9339, 8063, 4411, 1705, 461, 89, 10, 1

Offset: 0

Alois P. Heinz, Sep 05 2017

			: T(4,2) = 5:       /\      /\        /\/\    /\  /\    /\/\/\
:              /\/\/  \  /\/  \/\  /\/    \  /  \/  \  /      \
:
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,   1;
  0, 1,   2,   1;
  0, 1,   5,   3,   1;
  0, 1,   9,  11,   4,   1;
  0, 1,  19,  31,  19,   5,   1;
  0, 1,  35,  91,  69,  29,   6,  1;
  0, 1,  71, 250, 252, 127,  41,  7, 1;
  0, 1, 135, 690, 855, 540, 209, 55, 8, 1;
  ...

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000007, A057427, A056326, A291887, A291888, A291889, A291890, A291891, A291892, A291893, A291894.
Main and first two lower diagonals give A000012, A001477, A028387(n-1) for n>0.
Row sums give A007123(n+1).
T(2n,n) give A291885.
Cf. A080936, A132890, A291886.

b:= proc(x, y, k) option remember; `if`(x=0, z^k, `if`(y0, b(x-1, y-1, k), 0))
    end:
g:= proc(x, y, k) option remember; `if`(x=0, z^k, `if`(y>0,
      g(x-2, y-1, k), 0)+ g(x-2, y+1, max(y+1, k)))
    end:
T:= n-> (p-> seq(coeff(p, z, i)/2, i=0..n))(b(2*n, 0$2)+g(2*n, 0$2)):
seq(T(n), n=0..14);

b[x_, y_, k_] := b[x, y, k] = If[x == 0, z^k, If[y < x - 1, b[x - 1, y + 1, Max[y + 1, k]], 0] + If[y > 0, b[x - 1, y - 1, k], 0]];
g[x_, y_, k_] := g[x, y, k] = If[x == 0, z^k, If[y > 0, g[x - 2, y - 1, k], 0] + g[x - 2, y + 1, Max[y + 1, k]]];
T[n_] := Function[p, Table[Coefficient[p, z, i]/2, {i, 0, n}]][b[2*n, 0, 0] + g[2*n, 0, 0]];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Jun 03 2018, from Maple *)

from sympy.core.cache import cacheit
from sympy import Poly, Symbol, flatten
z=Symbol('z')
@cacheit
def b(x, y, k): return z**k if x==0 else (b(x - 1, y + 1, max(y + 1, k)) if y0 else 0)
@cacheit
def g(x, y, k): return z**k if x==0 else (g(x - 2, y - 1, k) if y>0 else 0) + g(x - 2, y + 1, max(y + 1, k))
def T(n): return 1 if n==0 else [i//2 for i in Poly(b(2*n, 0, 0) + g(2*n, 0, 0)).all_coeffs()[::-1]]
print(flatten(map(T, range(15)))) # Indranil Ghosh, Sep 06 2017

T(n,k) = (A080936(n,k) + A132890(n,k))/2.

Sum_{k=1..n} k * T(n,k) = A291886(n).

A086431 Involution of natural numbers induced by the Catalan bijection gma086431 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 6, 8, 9, 11, 10, 12, 13, 17, 18, 16, 14, 15, 21, 20, 19, 22, 23, 28, 25, 30, 33, 24, 29, 26, 31, 32, 27, 35, 34, 36, 45, 48, 46, 49, 50, 44, 47, 42, 37, 39, 43, 38, 40, 41, 58, 59, 57, 54, 55, 56, 53, 51, 52, 63, 62, 61, 60, 64, 65, 79, 70, 84, 93

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection reflects the interpretations (pp)-(rr) of Stanley, obtained with the "descending slope mapping" from the Dyck paths encoded by A014486.

			Map the Dyck paths (Stanley's interpretation (i)) to noncrossing Murasaki-diagrams (Stanley's interpretation (rr)) by drawing a vertical line above each descending slope \ and connect those vertical lines that originate from the same height without any lower valleys between, as in illustration below:
..................................................
.....___________..................................
....|...|....._.|.................................
....|..||...||.||..................___________....
....|..||...||.||.................|...|...._..|...
....|..||../\|.||..i.e..equal.to..|.|.|.|.|.|.|...
....|./\|./..\/\|.................|.|.|.|.|.|.|...
.../\/..\/......\.................|.|.|.|.|.|.|...
...10110011100100=11492=A014486(250)
Now the Catalan bijection gma086431 gives the parenthesization such that the corresponding Murasaki-diagram is a reflection of the original one:
.....___________..................................
....|...._..|...|.................................
....|...|.|||..||..................___________....
....|...|.|||..||.................|.._....|...|...
....|../\/\||..||..i.e..equal.to..|.|.|.|.|.|.|...
....|./....\|./\|.................|.|.|.|.|.|.|...
.../\/......\/..\.................|.|.|.|.|.|.|...
...10111010001100=11916=A014486(296)
So we have A086431(250)=296 and A086431(296)=250.

A. Karttunen, Noncrossing Murasaki diagrams obtained via descending slope mapping illustrated up to seven sticks
A. Karttunen, Gatomorphisms (With the complete Scheme source)
R. P. Stanley, Exercises on Catalan and Related Numbers (including 66 combinatorial interpretations)
Index entries for signature-permutations induced by Catalan automorphisms

a(n) = A057164(A085161(A057164(n))) = A086425(A057164(A086426(n))). Occurs in A073200. Cf. also A086427, A086430.

Number of cycles: A007123. Number of fixed points: A001405. (In range [A014137(n-1)..A014138(n-1)] of this permutation.).

A082313 Involution of natural numbers: A057501-conjugate of A057164.

Original entry on oeis.org

0, 1, 2, 3, 4, 8, 6, 7, 5, 9, 21, 14, 18, 13, 11, 22, 16, 17, 12, 19, 20, 10, 15, 23, 58, 37, 49, 35, 28, 62, 42, 46, 32, 51, 55, 27, 41, 25, 59, 39, 50, 36, 30, 63, 44, 45, 31, 53, 54, 26, 40, 33, 64, 47, 48, 34, 56, 57, 24, 38, 60, 61, 29, 43, 52, 65, 170, 107, 142, 100

Offset: 0

Antti Karttunen, Apr 17 2003. Proposed by Wouter Meeussen in Dec 15 2001

nonn

Note: This is isomorphic with Meeussen's "skewcatacycleft" operation acting on the interpretation (gg) of the exercise 19 by Stanley.

a(n) = A069888(A057502(n)). Occurs in A073200 as row 604463486276865131809167. Cf. also A082314, A082315, A082333, A082334.

Number of cycles: A007123. Number of fixed-points: A001405. Max. cycle size: A046698. LCM of cycle sizes: A046698. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

a(n) = A057501(A057164(A057502(n)))

A085162 Permutation of natural numbers induced by Catalan Automorphism *A085162.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 6, 5, 8, 9, 17, 16, 12, 21, 14, 15, 11, 10, 18, 20, 19, 13, 22, 23, 45, 44, 31, 58, 42, 43, 30, 26, 49, 57, 56, 35, 63, 37, 40, 39, 38, 41, 28, 29, 25, 24, 46, 48, 47, 32, 59, 54, 55, 53, 51, 52, 34, 33, 27, 50, 62, 61, 60, 36, 64, 65, 129, 128, 87, 170

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

a(n) = A057163(A085161(A057163(n))). Cf. also A085165, A085166, A086431. Occurs in A073200.

Number of cycles: A007123. Number of fixed points: A001405 (in each range limited by A014137 and A014138).

A378941 Number of Motzkin paths of length n up to reversal.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 32, 70, 179, 435, 1142, 2947, 7889, 21051, 57192, 155661, 427795, 1179451, 3271214, 9102665, 25434661, 71282431, 200406472, 564905068, 1596435581, 4521772933, 12835116530, 36504093693, 104012240063, 296871993373, 848694481664, 2429882584254, 6966789756243

Offset: 0

Andrew Howroyd, Dec 17 2024

nonn

A Motzkin path of length n is a path from (0,0) to (n,0) using only steps U = (1,1), H = (1,0) and D = (1,-1). This sequence considers a path and its reversal to be the same. The number of symmetric paths of length 2n (and also 2n+1) is given by A005773(n+1).

a(n) + 1 is an upper bound on the order of the linear recurrence of column n-1 of A287151. At least for columns up to 7, this bound gives the actual order of the recurrence. For example, a(5) = 13 and the order of the recurrence of column 4 (=A059524) is 14.

			The Motzkin paths for a(1)..a(5) are:
a(1) = 1: H;
a(2) = 2: HH, UD;
a(3) = 3: HHH, UHD, HUD=UDH;
a(4) = 7: HHHH, HUDH, UHHD, UUDD, UDUD, HHUD=UDHH, HUHD=UHDH.
a(5) = 13: HHHHH, HUHDH, UHHHD, UUHDD, UDHUD, HHHUD=UDHHH, HHUHD=UHDHH, HHUDH=HUDHH, HUHHD=UHHDH, HUUDD=UUDDH, HUDUD=UDUDH, UHUDD=UUHDD, UHDUD=UPUHD.

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A001006, A005773, A007123 (similar for Dyck paths), A175954, A185100, A287151, A292357.

Vec(-3/(4*x)-(1+sqrt(1-2*x-3*x^2+O(x^40)))/(4*x^2)+(1+x)/(-1+3*x^2+sqrt(1-2*x^2-3*x^4+O(x^40)))) \\ Thomas Scheuerle, Dec 18 2024

a(n) = (A001006(n) + A005773(floor(1 + n/2))) / 2.

A005217 Number of unlabeled unit interval graphs with n nodes.

Original entry on oeis.org

1, 2, 4, 9, 21, 55, 151, 447, 1389, 4502, 15046, 51505, 179463, 634086, 2265014, 8163125, 29637903, 108282989, 397761507, 1468063369, 5441174511, 20242989728, 75566702558, 282959337159, 1062523000005, 4000108867555, 15095081362907, 57088782570433

Offset: 1

N. J. A. Sloane

nonn

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.7.
R. W. Robinson, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.

R. W. Robinson, Table of n, a(n) for n = 1..190
Phil Hanlon, Counting interval graphs, Trans. Amer. Math. Soc. 272 (1982), no. 2, 383-426.

m = 30;
A[x_] = (-1 + Exp[Sum[psi[x^k]/k, {k, 1, m}]] /. psi[x_] -> (1 + 2 x - Sqrt[1 - 4 x] Sqrt[1 - 4 x^2])/(4 Sqrt[1 - 4 x^2])) + O[x]^m;
CoefficientList[A[x], x] // Rest (* Jean-François Alcover, Oct 24 2019 *)

G.f. A(x) = x + 2x^2 + 4x^3 + 9x^4 + 21x^5 + ... satisfies 1 + A(x) = exp( Sum_{k >= 1} psi(x^k)/k ), where psi(x) = (1+2*x-sqrt(1-4*x)*sqrt(1-4*x^2))/(4*sqrt(1-4*x^2)) is the g.f. for A007123.

For asymptotics, see for example Finch.

cp's OEIS Frontend

A001405 a(n) = binomial(n, floor(n/2)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

Python

Formula

A007595 a(n) = C_n / 2 if n is even or ( C_n + C_((n-1)/2) ) / 2 if n is odd, where C = Catalan numbers (A000108).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A073201 Array of cycle count sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

A085161 Involution of natural numbers induced by Catalan Automorphism *A085161 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A291883 Number T(n,k) of symmetrically unique Dyck paths of semilength n and height k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A086431 Involution of natural numbers induced by the Catalan bijection gma086431 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A082313 Involution of natural numbers: A057501-conjugate of A057164.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A085162 Permutation of natural numbers induced by Catalan Automorphism *A085162.

Views