|
|
A055203
|
|
Number of different relations between n intervals on a line.
|
|
13
|
|
|
1, 1, 13, 409, 23917, 2244361, 308682013, 58514835289, 14623910308237, 4659168491711401, 1843200116875263613, 886470355671907534969, 509366445167037318008557, 344630301458257894126724041, 271188703889907190388528763613, 245570692377888837925941696215449
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Number of alignments of n strings of length 2 (see Slowinski).
Conjectures: a(n) == 1 (mod 12); for fixed k, the sequence a(n) (mod k) eventually becomes periodic with exact period a divisor of phi(k), where phi(k) is Euler's totient function A000010. (End)
|
|
REFERENCES
|
S. R. Schwer, Dépendances temporelles: les mots pour le dire, Journées Intelligence Artificielle, 1998.
S. R. Schwer, Enumerating and generating Allen's algebra, in preparation.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{i=2..2n} lambda(i, n), with lambda(p, 1) = 1 if p = 2, otherwise 0; lambda(p, n) = (p*(p-1)/2)*(lambda(p, n-1) + 2*lambda(p-1, n-1) + lambda(p-2, n-1)).
lambda(p, n) = Sum_k[( - 1)^(p + k) * C(p, k) * ((k - 1)*k/2)^n]. So if T(m, 0), T(m, 1), ..., T(m, m) is any row of A035317 with m >= 2n - 1 then a(n) = Sum_j[(-1)^j * T(m, j) * ((m - j + 1)*(m - j)/2)^n]; e.g., a(2) = 13 = 1*6^2 - 3*3^2 + 4*1^2 - 2*0^2 = 1*10^2 - 4*6^2 + 7*3^2 - 6*1^2 + 3*0^2 = 1*15^2 - 5*10^2 + 11*6^2 - 13*3^2 + 9*1^2 - 3*0^2 etc. while a(3) = 409 = 1*15^3 - 5*10^3 + 11*6^3 - 13*3^3 + 9*1^3 - 3*0^3 etc. - Henry Bottomley, Jan 03 2001
E.g.f.: Sum_{m>=0} exp(x*binomial(m,2))/2^(m+1). - Vladeta Jovovic, Sep 24 2006
a(n) ~ n! * n^n * 2^(n-1) / (exp(n) * (log(2))^(2*n+1)). - Vaclav Kotesovec, Mar 15 2014
a(n) = Sum_{k = 2..2*n} Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)*(i*(i-1)/2)^n.
a(n) = (1/2^(n+1))*Sum_{k = 0..n} binomial(n,k)*A000670(n+k) for n >= 1. (End)
|
|
EXAMPLE
|
In case n = 2 this is the Delannoy number a(2) = D(2,2) = 13.
a(2) = 13 because if you have two intervals [a1,a2] and [b1,b2], using a for a1 or a2 and b for b1 or b2 and writing c if an a is at the same place as a b, we get the following possibilities: aabb, acb, abab, cab, abc, baab, abba, cc, bac, cba, baba, bca, bbaa.
|
|
MAPLE
|
lambda := proc(p, n) option remember; if n = 1 then if p = 2 then RETURN(1) else RETURN(0) fi; else RETURN((p*(p-1)/2)*(lambda(p, n-1)+2*lambda(p-1, n-1)+lambda(p-2, n-1))) fi; end; A055203 := n->add(lambda(i, n), i=2..2*n);
# second Maple program:
b:= proc(n) option remember; `if`(n=0, 1,
add(b(n-j)*binomial(n, j), j=1..n))
end:
a:= n-> ceil(add(b(n+k)*binomial(n, k), k=0..n)/2^(n+1)):
|
|
MATHEMATICA
|
With[{r = 2}, Flatten[{1, Table[Sum[Sum[(-1)^i*Binomial[j, i]*Binomial[j - i, r]^k, {i, 0, j}], {j, 0, k*r}], {k, 1, 15}]}]] (* Vaclav Kotesovec, Mar 22 2016 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
Sylviane R. Schwer (schwer(AT)lipn.univ-paris13.fr), Jun 22 2000
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Oct 04 2000
|
|
STATUS
|
approved
|
|
|
|