%I #55 May 12 2022 18:46:54
%S 1,1,13,409,23917,2244361,308682013,58514835289,14623910308237,
%T 4659168491711401,1843200116875263613,886470355671907534969,
%U 509366445167037318008557,344630301458257894126724041,271188703889907190388528763613,245570692377888837925941696215449
%N Number of different relations between n intervals on a line.
%C From _Peter Bala_, Jan 30 2018: (Start)
%C Number of alignments of n strings of length 2 (see Slowinski).
%C 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)
%D S. R. Schwer, Dépendances temporelles: les mots pour le dire, Journées Intelligence Artificielle, 1998.
%D S. R. Schwer, Enumerating and generating Allen's algebra, in preparation.
%H T. D. Noe, <a href="/A055203/b055203.txt">Table of n, a(n) for n = 0..100</a>
%H Tim Fernando and Carl Vogel, <a href="https://www.scss.tcd.ie/Tim.Fernando/NLPinAI_2019.pdf">Prior Probabilities of Allen Interval Relations over Finite Orders</a>, 11th International Conference on Agents and Artificial Intelligence (NLPinAI 2019) Prague.
%H IBM Ponder This, <a href="http://domino.watson.ibm.com/Comm/wwwr_ponder.nsf/challenges/January2001.html">Jan 01 2001</a>
%H J. B. Slowinski, <a href="http://www.neurociencias.org.ve/cont-cursos-laboratorio-de-neurociencias-luz/Slowinski1998%20phylogenetics.pdf">The Number of Multiple Alignments</a>, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:<a href="http://dx.doi.org/10.1006/mpev.1998.0522">10.1006/mpev.1998.0522</a>
%H Peter Stockman, <a href="http://www.diva-portal.org/smash/get/diva2:943554/FULLTEXT01.pdf">Upper Bounds on the Time Complexity of Temporal CSPs</a>, Linköping University | Department of Computer science, Master's thesis, 30 ECTS | Datateknik 2016 | LIU-IDA/LITH-EX-A--16/022--SE.
%H David Adam Woods, <a href="http://www.tara.tcd.ie/bitstream/handle/2262/98534/DavidAdamWoods_Thesis.pdf">Strings for Temporal Annotation and Semantic Representation of Events</a>, Ph. D. Dissertation, Univ. of Dublin, Trinity College (Ireland, 2022).
%F 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)).
%F 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
%F Row sums of A122193. - _Vladeta Jovovic_, Aug 24 2006
%F a(n) = Sum_{k=0..n} k!*Stirling2(n,k)*A121251(k). - _Vladeta Jovovic_, Aug 25 2006
%F E.g.f.: Sum_{m>=0} exp(x*binomial(m,2))/2^(m+1). - _Vladeta Jovovic_, Sep 24 2006
%F a(n) = Sum_{m>=0} binomial(m,2)^n/2^(m+1). - _Vladeta Jovovic_, Aug 17 2006
%F a(n) = (1/2^n)*Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*A000670(n+k). - _Vladeta Jovovic_, Aug 17 2006
%F a(n) ~ n! * n^n * 2^(n-1) / (exp(n) * (log(2))^(2*n+1)). - _Vaclav Kotesovec_, Mar 15 2014
%F From _Peter Bala_, Jan 30 2018: (Start)
%F a(n) = Sum_{k = 2..2*n} Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)*(i*(i-1)/2)^n.
%F a(n) = (1/2^(n+1))*Sum_{k = 0..n} binomial(n,k)*A000670(n+k) for n >= 1. (End)
%e In case n = 2 this is the Delannoy number a(2) = D(2,2) = 13.
%e 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.
%p 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);
%p A055203 := proc(n) local k; add(A078739(n,k)*k!,k=0..2*n)/2^n end:
%p seq(A055203(n),n=0..15); # _Peter Luschny_, Mar 25 2011
%p # second Maple program:
%p b:= proc(n) option remember; `if`(n=0, 1,
%p add(b(n-j)*binomial(n, j), j=1..n))
%p end:
%p a:= n-> ceil(add(b(n+k)*binomial(n, k), k=0..n)/2^(n+1)):
%p seq(a(n), n=0..20); # _Alois P. Heinz_, Jul 10 2018
%t 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_ *)
%t 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 *)
%Y Cf. A035317, A055809, A055810, A078739, A122193, A062208.
%Y Row n=2 of A262809.
%K nonn,nice,easy
%O 0,3
%A Sylviane R. Schwer (schwer(AT)lipn.univ-paris13.fr), Jun 22 2000
%E More terms from Larry Reeves (larryr(AT)acm.org), Oct 04 2000
%E More terms from _N. J. A. Sloane_, Jan 03 2001