cp's OEIS Frontend

a(17)>75000. - Robert G. Wilson v, Feb 25 2007

Number of 4321-, (3412,2413)-, (3412,3142)- and 3412-avoiding involutions in S_n.

Number of sequences of length n-1 consisting of positive integers such that the first and last elements are 1 or 2 and the absolute difference between any 2 consecutive elements is 0 or 1. - Jon Perry, Sep 04 2003

From David Callan, Jul 15 2004: (Start)

Also number of Motzkin n-paths: paths from (0,0) to (n,0) in an n X n grid using only steps U = (1,1), F = (1,0) and D = (1,-1).

Number of Dyck n-paths with no UUU. (Given such a Dyck n-path, change each UUD to U, then change each remaining UD to F. This is a bijection to Motzkin n-paths. Example with n=5: U U D U D U U D D D -> U F U D D.)

Number of Dyck (n+1)-paths with no UDU. (Given such a Dyck (n+1)-path, mark each U that is followed by a D and each D that is not followed by a U. Then change each unmarked U whose matching D is marked to an F. Lastly, delete all the marked steps. This is a bijection to Motzkin n-paths. Example with n=6 and marked steps in small type: U U u d D U U u d d d D u d -> U U u d D F F u d d d D u d -> U U D F F D.) (End)

a(n) is the number of strings of length 2n+2 from the following recursively defined set: L contains the empty string and, for any strings a and b in L, we also find (ab) in L. The first few elements of L are e, (), (()), ((())), (()()), (((()))), ((()())), ((())()), (()(())) and so on. This proves that a(n) is less than or equal to C(n), the n-th Catalan number. See Orrick link (2024). - Saul Schleimer (saulsch(AT)math.rutgers.edu), Feb 23 2006 (Additional linked comment added by William P. Orrick, Jun 13 2024.)

a(n) = number of Dyck n-paths all of whose valleys have even x-coordinate (when path starts at origin). For example, T(4,2)=3 counts UDUDUUDD, UDUUDDUD, UUDDUDUD. Given such a path, split it into n subpaths of length 2 and transform UU->U, DD->D, UD->F (there will be no DUs for that would entail a valley with odd x-coordinate). This is a bijection to Motzkin n-paths. - David Callan, Jun 07 2006

Also the number of standard Young tableaux of height <= 3. - Mike Zabrocki, Mar 24 2007

a(n) is the number of RNA shapes of size 2n+2. RNA Shapes are essentially Dyck words without "directly nested" motifs of the form A[[B]]C, for A, B and C Dyck words. The first RNA Shapes are []; [][]; [][][], [[][]]; [][][][], [][[][]], [[][][]], [[][]][]; ... - Yann Ponty (ponty(AT)lri.fr), May 30 2007

The sequence is self-generated from top row A going to the left starting (1,1) and bottom row = B, the same sequence but starting (0,1) and going to the right. Take dot product of A and B and add the result to n-th term of A to get the (n+1)-th term of A. Example: a(5) = 21 as follows: Take dot product of A = (9, 4, 2, 1, 1) and (0, 1, 1, 2, 4) = (0, + 4 + 2 + 2 + 4) = 12; which is added to 9 = 21. - Gary W. Adamson, Oct 27 2008

Equals A005773 / A005773 shifted (i.e., (1,2,5,13,35,96,...) / (1,1,2,5,13,35,96,...)). - Gary W. Adamson, Dec 21 2008

Starting with offset 1 = iterates of M * [1,1,0,0,0,...], where M = a tridiagonal matrix with [0,1,1,1,...] in the main diagonal and [1,1,1,...] in the super and subdiagonals. - Gary W. Adamson, Jan 07 2009

a(n) is the number of involutions of {1,2,...,n} having genus 0. The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q. Example: a(4)=9; indeed, p=3412=(13)(24) is the only involution of {1,2,3,4} with genus > 0. This follows easily from the fact that a permutation p of {1,2,...,n} has genus 0 if and only if the cycle decomposition of p gives a noncrossing partition of {1,2,...,n} and each cycle of p is increasing (see Lemma 2.1 of the Dulucq-Simion reference). [Also, redundantly, for p=3412=(13)(24) we have cp'=2341*3412=4123=(1432) and so g(p)=(1/2)(4+1-2-1)=1.] - Emeric Deutsch, May 29 2010

Let w(i,j,n) denote walks in N^2 which satisfy the multivariate recurrence w(i,j,n) = w(i, j + 1, n - 1) + w(i - 1, j, n - 1) + w(i + 1, j - 1, n - 1) with boundary conditions w(0,0,0) = 1 and w(i,j,n) = 0 if i or j or n is < 0. Then a(n) = Sum_{i = 0..n, j = 0..n} w(i,j,n) is the number of such walks of length n. - Peter Luschny, May 21 2011

a(n)/a(n-1) tends to 3.0 as N->infinity: (1+2*cos(2*Pi/N)) relating to longest odd N regular polygon diagonals, by way of example, N=7: Using the tridiagonal generator [cf. comment of Jan 07 2009], for polygon N=7, we extract an (N-1)/2 = 3 X 3 matrix, [0,1,0; 1,1,1; 0,1,1] with an e-val of 2.24697...; the longest Heptagon diagonal with edge = 1. As N tends to infinity, the diagonal lengths tend to 3.0, the convergent of the sequence. - Gary W. Adamson, Jun 08 2011

Number of (n+1)-length permutations avoiding the pattern 132 and the dotted pattern 23\dot{1}. - Jean-Luc Baril, Mar 07 2012

Number of n-length words w over alphabet {a,b,c} such that for every prefix z of w we have #(z,a) >= #(z,b) >= #(z,c), where #(z,x) counts the letters x in word z. The a(4) = 9 words are: aaaa, aaab, aaba, abaa, aabb, abab, aabc, abac, abca. - Alois P. Heinz, May 26 2012

Number of length-n restricted growth strings (RGS) [r(1), r(2), ..., r(n)] such that r(1)=1, r(k)<=k, and r(k)!=r(k-1); for example, the 9 RGS for n=4 are 1010, 1012, 1201, 1210, 1212, 1230, 1231, 1232, 1234. - Joerg Arndt, Apr 16 2013

Number of length-n restricted growth strings (RGS) [r(1), r(2), ..., r(n)] such that r(1)=0, r(k)<=k and r(k)-r(k-1) != 1; for example, the 9 RGS for n=4 are 0000, 0002, 0003, 0004, 0022, 0024, 0033, 0222, 0224. - Joerg Arndt, Apr 17 2013

Number of (4231,5276143)-avoiding involutions in S_n. - Alexander Burstein, Mar 05 2014

a(n) is the number of increasing unary-binary trees with n nodes that have an associated permutation that avoids 132. For more information about unary-binary trees with associated permutations, see A245888. - Manda Riehl, Aug 07 2014

a(n) is the number of involutions on [n] avoiding the single pattern p, where p is any one of the 8 (classical) patterns 1234, 1243, 1432, 2134, 2143, 3214, 3412, 4321. Also, number of (3412,2413)-, (3412,3142)-, (3412,2413,3142)-avoiding involutions on [n] because each of these 3 sets actually coincides with the 3412-avoiding involutions on [n]. This is a complete list of the 8 singles, 2 pairs, and 1 triple of 4-letter classical patterns whose involution avoiders are counted by the Motzkin numbers. (See Barnabei et al. 2011 reference.) - David Callan, Aug 27 2014

From Tony Foster III, Jul 28 2016: (Start)

A series created using 2*a(n) + a(n+1) has Hankel transform of F(2n), offset 3, F being the Fibonacci bisection, A001906 (empirical observation).

A series created using 2*a(n) + 3*a(n+1) + a(n+2) gives the Hankel transform of Sum_{k=0..n} k*Fibonacci(2*k), offset 3, A197649 (empirical observation). (End)

Conjecture: (2/n)*Sum_{k=1..n} (2k+1)*a(k)^2 is an integer for each positive integer n. - Zhi-Wei Sun, Nov 16 2017

The Rubey and Stump reference proves a refinement of a conjecture of René Marczinzik, which they state as: "The number of 2-Gorenstein algebras which are Nakayama algebras with n simple modules and have an oriented line as associated quiver equals the number of Motzkin paths of length n." - Eric M. Schmidt, Dec 16 2017

Number of U_{k}-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths. - Sergey Kirgizov, Apr 08 2018

If tau_1 and tau_2 are two distinct permutation patterns chosen from the set {132,231,312}, then a(n) is the number of valid hook configurations of permutations of [n+1] that avoid the patterns tau_1 and tau_2. - Colin Defant, Apr 28 2019

Number of permutations of length n that are sorted to the identity by a consecutive-321-avoiding stack followed by a classical-21-avoiding stack. - Colin Defant, Aug 29 2020

From Helmut Prodinger, Dec 13 2020: (Start)

a(n) is the number of paths in the first quadrant starting at (0,0) and consisting of n steps from the infinite set {(1,1), (1,-1), (1,-2), (1,-3), ...}.

For example, denoting U=(1,1), D=(1,-1), D_ j=(1,-j) for j >= 2, a(4) counts UUUU, UUUD, UUUD_2, UUUD_3, UUDU, UUDD, UUD_2U, UDUU, UDUD.

This step set is inspired by {(1,1), (1,-1), (1,-3), (1,-5), ...}, suggested by Emeric Deutsch around 2000.

See Prodinger link that contains a bijection to Motzkin paths. (End)

Named by Donaghey (1977) after the Israeli-American mathematician Theodore Motzkin (1908-1970). In Sloane's "A Handbook of Integer Sequences" (1973) they were called "generalized ballot numbers". - Amiram Eldar, Apr 15 2021

Number of Motzkin n-paths a(n) is split into A107587(n), number of even Motzkin n-paths, and A343386(n), number of odd Motzkin n-paths. The value A107587(n) - A343386(n) can be called the "shadow" of a(n) (see A343773). - Gennady Eremin, May 17 2021

Conjecture: If p is a prime of the form 6m+1 (A002476), then a(p-2) is divisible by p. Currently, no counterexample exists for p < 10^7. Personal communication from Robert Gerbicz: mod such p this is equivalent to A066796 with comment: "Every A066796(n) from A066796((p-1)/2) to A066796(p-1) is divisible by prime p of form 6m+1". - Serge Batalov, Feb 08 2022

From Rob Burns, Nov 11 2024: (Start)

The conjecture is proved in the 2017 paper by Rob Burns in the Links below. The result is contained in Tables 4 and 5 of the paper, which show that a(p-2) == 0 (mod p) when p == 1 (mod 6) and a(p-2) == -1 (mod p) when p == -1 (mod 6).

In fact, the 2017 paper by Burns establishes more general congruences for a(p^k - 2) where k >= 1.

If p == 1 (mod 6) then a(p^k - 2) == 0 (mod p) for k >= 1.

If p == -1 (mod 6) then a(p^k - 2) == -1 (mod p) when k is odd and a(p^k - 2) == 0 (mod p) when k is even.

These are consequences of the transitions provided in Tables 4, 5 and 6 of the paper.

The 2024 paper by Nadav Kohen also proves the conjecture. Proposition 6 of the paper states that a prime p divides a(p-2) if and only if p = (1 mod 3). (End)

From Peter Bala, Feb 10 2022: (Start)

Conjectures:

(1) For prime p == 1 (mod 6) and n, r >= 1, a(n*p^r - 2) == -A005717(n-1) (mod p), where we take A005717(0) = 0 to match Batalov's conjecture above.

(2) For prime p == 5 (mod 6) and n >= 1, a(n*p - 2) == -A005773(n) (mod p).

(3) For prime p >= 3 and k >= 1, a(n + p^k) == a(n) (mod p) for 0 <= n <= (p^k - 3).

(4) For prime p >= 5 and k >= 2, a(n + p^k) == a(n) (mod p^2) for 0 <= n <= (p^(k-1) - 3). (End)

The Hankel transform of this sequence with a(0) omitted gives the period-6 sequence [1, 0, -1, -1, 0, 1, ...] which is A010892 with its first term omitted, while the Hankel transform of the current sequence is the all-ones sequence A000012, and also it is the unique sequence with this property which is similar to the unique Hankel transform property of the Catalan numbers. - Michael Somos, Apr 17 2022

The number of terms in which the exponent of any variable x_i is not greater than 2 in the expansion of Product_{j=1..n} Sum_{i=1..j} x_i. E.g.: a(4) = 9: 3*x1^2*x2^2, 4*x1^2*x2*x3, 2*x1^2*x2*x4, x1^2*x3^2, x1^2*x3*x4, 2*x1*x2^2*x3, x1*x2^2*x4, x1*x2*x3^2, x1*x2*x3*x4. - Elif Baser, Dec 20 2024

The expression a(n) = B^n*Sum_{ k=0..n } binomial(2*k,k)/B^k gives A006134 for B=1, A082590 (B=2), A132310 (B=3), A002457 (B=4), A144635 (B=5). - N. J. A. Sloane, Jan 21 2009

T(n+1,1) from table A045912 of characteristic polynomial of negative Pascal matrix. - Michael Somos, Jul 24 2002

p divides a((p-3)/2) for p=11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, 107, 109, 131, 157, 167, ...: A097933. Also primes congruent to {1, 2, 3, 11} mod 12 or primes p such that 3 is a square mod p (excluding 2 and 3) A038874. - Alexander Adamchuk, Jul 05 2006

Partial sums of the even central binomial coefficients. For p prime >=5, a(p-1) = 1 or -1 (mod p) according as p = 1 or -1 (mod 3) (see Pan and Sun link). - David Callan, Nov 29 2007

First column of triangle A187887. - Michel Marcus, Jun 23 2013

From Gus Wiseman, Apr 20 2023: (Start)

Also the number of nonempty subsets of {1,...,2n+1} with median n+1, where the median of a multiset is either the middle part (for odd length), or the average of the two middle parts (for even length). The odd/even-length cases are A000984 and A006134(n-1). For example, the a(0) = 1 through a(2) = 9 subsets are:

{1} {2} {3}

{1,3} {1,5}

{1,2,3} {2,4}

{1,3,4}

{1,3,5}

{2,3,4}

{2,3,5}

{1,2,4,5}

{1,2,3,4,5}

Alternatively, a(n-1) is the number of nonempty subsets of {1,...,2n-1} with median n.

(End)

a(n) is the sum of pyramid weights of all Dyck paths of length 2n (for pyramid weight see Denise and Simion). Equivalently, a(n) is the sum of the total lengths of end branches of an ordered tree, summation being over all ordered trees with n edges. For example, the five ordered trees with 3 edges have total lengths of endbranches 3,2,3,3 and 3. - Emeric Deutsch, May 30 2003

a(n) is the number of Motzkin paths of length 2n with exactly one level segment. (A level segment is a maximal sequence of contiguous flatsteps.) Example: for n=2, the paths counted are FFFF, FFUD, UDFF, UFFD. The formula for a(n) below counts these paths by length of the level segment. - David Callan, Jul 15 2004

The inverse Catalan transform yields A024495, shifted once left. - R. J. Mathar, Jul 07 2009

From Paul Barry, Mar 29 2010: (Start)

Hankel transform is A138341.

The aerated sequence 0, 0, 1, 0, 4, 0, 14, 0, 49, ... has e.g.f. int(cosh(x-t)*Bessel_I(1,2t), t = 0..x). (End)

a(n) is the number of terms of A031443 not exceeding 4^n. - Vladimir Shevelev, Oct 01 2010

Also the number of nonempty subsets of {1..2n} with median n, bisection of A361801. The version containing n is A001700 (bisected). Replacing 2n with 2n+1 and n with n+1 gives A006134. For mean instead of median we have A212352. - Gus Wiseman, Apr 16 2023

p divides a((p-3)/2) for p in A045468 (primes congruent to {1, 4} mod 5). - Alexander Adamchuk, Jul 05 2006

The sequence 1,1,5,15,55,... has general term sum{k=0..n, (-1)^(n-k)*C(2k,k)}. Its Hankel transform is A082761. - Paul Barry, Apr 10 2007

From Paul Barry, Mar 29 2010: (Start)

The sequence 1,1,5,15,... has g.f. 1/((1+x)*sqrt(1-4x)).

The doubled sequence 1,1,1,1,5,5,... has e.g.f. dif(int((sin(x-t)+cos(x-t))*Bessel_I(0,2t),t,0,x),x). (End)

Apparently a(n)/3 (mod 3) = A010060(n-1), the Thue-Morse sequence.

p^2 divides a((p-3)/2) for prime p of the form p = 6k + 1 (A002476).

The expression a(n) = B^n*Sum_{k=0..n} binomial(2*k,k)/B^k gives A006134 for B=1, A082590 (B=2), A132310 (B=3), A002457 (B=4), A144635 (B=5), a(n) = A167713 (B=16).

Every a(n) from a((p-1)/2) to a(p-1) is divisible by prime p for p = {7, 47, 191, 383, 439, 1151, 1399, 2351, 2879, 3119, 3511, 3559, ...} = A167860, apparently a subset of primes of the form 8n+7 (A007522).

7^3 divides a(13) and 7^2 divides a(10)-a(13).

Every a(n) from a(kp-1 - (p-1)/2) to a(kp-1) is divisible by prime p from A167860.

Every a(n) from a((p^2-1)/2) to a(p^2-1) is divisible by prime p from A167860. For p=7 every a(n) from a((p^3-1)/2) to a(p^3-1) and from a((p^4-1)/2) to a(p^4-1)is divisible by p^2.

The expression a(n) = B^n*Sum_{ k=0..n } binomial(2*k,k)/B^k gives A006134 for B=1, A082590 (B=2), A132310 (B=3), A002457 (B=4), A144635 (B=5), A167713 (B=16).

The expression a(n) = B^n*Sum_{ k=0..n } binomial(2*k,k)^3/B^k gives A079727 for B=1, A167867 (B=2), A167868 (B=3), A167869 (B=4), A167870 (B=16), A167871 (B=64).

The expression a(n) = B^n*Sum_{k=0..n} binomial(2*k,k)/B^k gives A006134 for B=1, A082590 (B=2), A132310 (B=3), A002457 (B=4), A144635 (B=5), A167713 (B=16).

The expression a(n) = B^n*Sum_{k=0..n} binomial(2*k,k)^3/B^k gives A079727 for B=1, A167867 (B=2), A167868 (B=3), A167869 (B=4), A167870 (B=16), A167871 (B=64).