

A038746


Coefficients arising in the enumeration of configurations of linear chains.


7



0, 1, 3, 8, 20, 49, 117, 280, 665, 1583, 3742, 8876, 20933, 49521, 116578, 275204, 646908, 1524457, 3579100, 8421786, 19752217, 46419251, 108774693, 255351249, 597911623, 1402287934, 3281303692, 7689321700, 17982126657, 42108189097, 98421806690, 230322480772
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

This counts nonselfintersecting paths of length n on the square lattice, start and end points distinguished, straight line paths not counted, rotations and reflections of a path not counted as distinct from that path.
Nemirovsky et al. (1992), for a ddimensional hypercubic lattice, define C_{n,m} to be "the number of configurations of an nbond selfavoiding chain with m neighbor contacts." For d=2 (square lattice) and m=0 (no neighbor contacts), we have C(n, m=0) = A173380(n). 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 nm+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. For the current sequence, we have a(n) = p_{n,0}^{(2)} (with a(1) = p_{1,0}^{(2)} = 0 to make the formula A173380(n) = C_{n,0} = 4 + 8*p_{n,0}^{(2)} = 4 + 8*a(n) valid even for n=1).
Apparently, some of the numbers C_{n,m} (for d=2 and d=3) are calculated in Fisher and Hiley (1961); see Table II, p. 1261 (square and cubic). For d=2, they calculate C(n,0) for 1 <= n < 14, while for d=3, they calculate C(n,0) for 1 <= n <= 10. It seems, however, that there are some possible typos there. The typos (for both d=2 and d=3) become apparent if one compares their results with the numbers in Table I (p. 1088) in Nemirovsky et al. (1992). See the comments for the sequence A173380 for more details.
(End)
No adjacent points allowed unless consecutive in path  Bert Dobbelaere, Jan 02 2019


LINKS



CROSSREFS



KEYWORD

nonn,walk,more


AUTHOR



EXTENSIONS

Initial 0 added to match offset in reference, further explanation and terms a(12) = 8876 to a(22) = 46419251 by Joseph Myers, Nov 22 2010


STATUS

approved



