cp's OEIS Frontend

Essentially the same as A052704. - R. J. Mathar, Nov 27 2008

From Joerg Arndt, Oct 22 2012: (Start)

Number of strings of length 2*n of four different types of balanced parentheses.

The number of strings of length 2*n of t different types of balanced parentheses is given by t^n * A000108(n): there are n opening parentheses in the strings, giving t^n choices for the type (the closing parentheses are chosen to match). (End)

Number of Dyck paths of length 2n in which the step U=(1,1) comes in 4 colors. - José Luis Ramírez Ramírez, Jan 31 2013

Number of walks of length 2n+5 in the path graph P_6 from one end to the other one. Example: a(1)=5 because in the path ABCDEF we have ABABCDEF, ABCBCDEF, ABCDCDEF, ABCDEDEF and ABCDEFEF. - Emeric Deutsch, Apr 02 2004

Since a(n) is the binomial transform of A006054 from formula (3.63) in the Witula-Slota-Warzynski paper, it follows that a(n)=A(n;1)*(B(n;-1)-C(n;-1))-B(n;1)*B(n;-1)+C(n;1)*(A(n;-1)-B(n;-1)+C(n;-1)), where A(n;1)=A077998(n), B(n;1)=A006054(n+1), C(n;1)=A006054(n), A(n;-1)=A121449(n), B(n+1;-1)=-A085810(n+1), C(n;-1)=A215404(n) and A(n;d), B(n;d), C(n;d), n in N, d in C, denote the quasi-Fibonacci numbers defined and discussed in comments in A121449 and in the cited paper. - Roman Witula, Aug 09 2012

From Wolfdieter Lang, Mar 30 2020: (Start)

With offset -4 this sequence 6, 1, 0, 0, 1, 5, ... appears in the formula for the n-th power of the 3 X 3 tridiagonal Matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602: (M_3)^n = a(n-2)*(M_3)^2 - (6*a(n-3) - a(n-4))*M_3 + a(n-3)*1_3, with the 3 X 3 unit matrix 1_3, for n >= 0. Proof from Cayley-Hamilton: (M_3)^n = 5*(M_3)^3 - 6*M_3 + 1_3 (see A332602 for the characteristic polynomial Phi(3, x)), and the recurrence (M_3)^n = M_3*(M_3)^(n-1). For (M_3)^n[1,1] = 2*a(n-2) - 5*a(n-3) + a(n-4), for n >= 0, see A080937(n).

The formula for a(n) in terms of r = rho(7) = A160389 given below shows that a(n)/a(n-1) converges to rho(7)^2 = A116425 = 3.2469796... for n -> infinity. This is because r - 2/r = 0.692..., and r - 1 - 1/r = 0.137... .

(End)

A(n,k) is also the number of (n*k-1)-step walks on k-dimensional cubic lattice from (1,0,...,0) to (n,n,...,n) with positive unit steps in all dimensions such that for each point (p_1,p_2,...,p_k) we have p_1<=p_2<=...<=p_k or p_1>=p_2>=...>=p_k.

This sequence is the complement to A330979; here only composite numbers can be stepped to, while in A330979 only prime numbers can be stepped to. Due to the existence of many more composite numbers than primes the walk here forms a much tigher spiral and generally stays as close as possible to the origin. However the primes occasionally block this preferred path and causes the walk to detour away from the origin, which leaves gaps in the visited squares with composite numbers. Some of these gaps are eventually visited by later steps in the walk.

The first term at which a step to a non-adjacent square is required is a(154) = 74, which steps to a(155) = 158, a distance of sqrt(8) units away. The square with number 74 is surrounded by three primes 43,73,113 and five composites 44,72,75,112,114, all of which have been previously visited.

In the first 1 million terms the longest required step is from a(149464) = 64666, which has coordinates (-127,-22) relative to the starting 1-square, to a(149465) = 67774 with coordinates (-130,-43), a step of length sqrt(450), approximately 21.2 units. See A330782 for the progression of step length records. If the maximum step distance between adjacent composite terms has a finite value or is unbounded as n increases is unknown. The largest difference between adjacent composite terms is for a(650382) = 863400 to a(650383) = 939342, a difference of 75942.

In the first 1 million terms the smallest unvisited composite is 12, which is at coordinates (2,1) relative to the starting square. This square is surrounded by four primes so the walk is never required to step to it during the initial walk steps. See the image in the links. Given the composites become more frequent relative to the primes as n increases it would require a very large detour from the spiral pattern for this square to be visited, so it is likely, although unknown, this square will never be visited. However the link image for 1 million steps shows the path can make detours toward the central square when it is trapped by surrounding paths, so the possibility remains the inner unvisited squares could eventually be visited, although the number of walk steps required before such a detour occurs could be extremely large.

a(n) is the number of involutions of length 2n which are invariant under the reverse-complement map and have no decreasing subsequences of length 5. - Eric S. Egge, Oct 21 2008

a(n) = 4n*A002931(n). There are (2n) choices for the starting point and 2 choices for the orientation, in order to produce self-avoiding closed paths from a polygon of perimeter 2n. - Philippe Flajolet, Nov 22 2003

1-dimensional and 3-dimensional analogs are A002420 and A049037.

Trajectories returning to the origin are prohibited, contrary to the situation in A094061.

The probability of returning to the origin for the first time after 2n steps is given by a(n)/4^(2*n). If A(x) is a generating function for this sequence, A(x/16) is a generating function for the sequence of probabilities. The sum of these probabilities for n > 0 is 1 unlike in dimensions > 2. - Shel Kaphan, Feb 13 2023

Fisher and Hiley give 396204 as their last term instead of 396172 (see A002932). Douglas McNeil confirms 396172 (see seqfan discussion).

Comment from N. J. A. Sloane, Nov 27 2010: Joseph Myers has discovered that several of the sequences listed by Fisher and Riley (1961) contained errors. R. J. Mathar comments that this article has 62 citations in http://adsabs.harvard.edu/abs/1961JChPh..34.1253F and that clicking through these with the "Citations to the Article (62)" button is one way to check the numbers by searching for corrections.

From Petros Hadjicostas, Jan 01 2019: (Start)

Nemirovsky et al. (1992), for a d-dimensional hypercubic lattice, define C_{n,m} to be "the number of configurations of an n-bond self-avoiding chain with m neighbor contacts." For d=2 (square lattice) and m=0 (no neighbor contacts), we have (for the current sequence) a(n) = C(n, m=0). These values (from n=1 to n=11) are listed in Table I (p. 1088) in the paper.

According to Eq. (5), p. 1090, in the above paper, for a general d, the partition number C_{n,m} satisfies C_{n,m} = Sum_{l=1..n} 2^l*l!*Bin(d,l)*p_{n,m}^{(l)}, where the coefficients p_{n,m}^{(l)} (l=1,2,...) are independent of d. For d=2 (square lattice), this becomes C_{n,m} = Sum_{l=1..n} 2^l*l!*Bin(2,l)*p_{n,m}^{(l)}.

According to Eq. (7a) and (7b), p. 1093, in the paper, p_{n,0}^{(1)} = 1 = p_{n,0}^{(n)}, p_{n,m}^{(1)} = 0 for m >= 1, and p_{n,m}^{(l)} = 0 for m >= 1 and n-m+1 <= l <= n.

Now, assume d=2. Since p_{n,0}^{(1)} = 1 for n >= 1, we have C_{1,0} = 2^1*1!*Bin(2,1)*1 = 4, while C_{n,0} = 4 + 2^2*2!*Bin(2,2)*p_{n,0}^{(2)} = 4 + 8*p_{n,0}^{(2)} for n >= 2. The partition numbers p_{n,0}^{(2)} appear in Table II, p. 1093, in the paper. We have p_{n,0}^{(2)} = A038746(n) (with p_{1,0}^{(2)} = 0 to make the formula C_{n,0} = 4 + 8*p_{n,0}^{(2)} valid even for n=1).

(End)

This sequence gives the number of completed steps for a knight before being trapped when moving on a square-spiral numbered board and at each step choosing an unvisited square one knight-leap away which has the lowest spiral number and has n or fewer visited neighboring squares. It will only move to a square with n+1 or more neighbors when no square with n or fewer neighbors is available. If it is forced to move to such squares and two or more are available, it will choose the square with the fewest neighbors. If two or more squares with the same number of neighbors exist then it will choose the square with the smallest spiral number.

For n = 8 the path is equivalent to that given in A316667. Every square will always have eight or fewer visited neighbors, thus all unvisited squares are available to move to and the one with the smallest spiral number will always be chosen. This is A316667.

The values are surprisingly diverse, and it is not immediately obvious that the smaller values of n will even have a finite path length. It seems reasonable to assume that with the knight always choosing squares with very few visited neighbors it would be constantly moving away from the origin and thus never be trapped. But the path taken shows that, with such a restrictive choice of neighboring squares, the path leaves large areas of unvisited squares as the knight moves around the board, some of these being relatively close to the origin. At some point the knight will have an open path and move to these squares, thus move toward the origin, due to its preference to choose the squares with the smallest spiral number. It is thus drawn inward where it will then be surrounded by previous visited squares and eventually trapped. This tendency to leave large areas of unvisited squares is most easily seen in the path for n = 2, see link below, which is trapped after only 225 steps.

On the other extreme the path for n = 6, see A329519, is such that very few open areas remain near the origin, but the knight is still cautious in its choice and will not move to a square where it will likely be trapped, unless no other choices exist. This leads to the knight performing an extremely long walk before eventually finding a gap in its previous paths, moving toward the origin and finally being trapped after 3935788 steps.