login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
From Peter Bala, Jan 30 2018: (Start)
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
Tim Fernando and Carl Vogel, Prior Probabilities of Allen Interval Relations over Finite Orders, 11th International Conference on Agents and Artificial Intelligence (NLPinAI 2019) Prague.
IBM Ponder This, Jan 01 2001
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522
Peter Stockman, Upper Bounds on the Time Complexity of Temporal CSPs, Linköping University | Department of Computer science, Master's thesis, 30 ECTS | Datateknik 2016 | LIU-IDA/LITH-EX-A--16/022--SE.
David Adam Woods, Strings for Temporal Annotation and Semantic Representation of Events, Ph. D. Dissertation, Univ. of Dublin, Trinity College (Ireland, 2022).
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
Row sums of A122193. - Vladeta Jovovic, Aug 24 2006
a(n) = Sum_{k=0..n} k!*Stirling2(n,k)*A121251(k). - Vladeta Jovovic, Aug 25 2006
E.g.f.: Sum_{m>=0} exp(x*binomial(m,2))/2^(m+1). - Vladeta Jovovic, Sep 24 2006
a(n) = Sum_{m>=0} binomial(m,2)^n/2^(m+1). - Vladeta Jovovic, Aug 17 2006
a(n) = (1/2^n)*Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*A000670(n+k). - Vladeta Jovovic, Aug 17 2006
a(n) ~ n! * n^n * 2^(n-1) / (exp(n) * (log(2))^(2*n+1)). - Vaclav Kotesovec, Mar 15 2014
From Peter Bala, Jan 30 2018: (Start)
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);
A055203 := proc(n) local k; add(A078739(n, k)*k!, k=0..2*n)/2^n end:
seq(A055203(n), n=0..15); # Peter Luschny, Mar 25 2011
# 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)):
seq(a(n), n=0..20); # Alois P. Heinz, Jul 10 2018
MATHEMATICA
a[n_] := Sum[((m-1)*m)^n / 2^(m+n+1), {m, 0, Infinity}]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Oct 10 2011, after Vladeta Jovovic *)
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
Row n=2 of A262809.
Sequence in context: A075672 A069876 A126086 * A088919 A201537 A258178
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
More terms from N. J. A. Sloane, Jan 03 2001
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)