|
| |
|
|
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 non-self-intersecting 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 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 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 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. 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
|
| |
|
|
