0,3

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)

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.

T. D. Noe, Table of n, a(n) for n = 0..100

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).

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)

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.

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

# Alternative:

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

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 *)

Cf. A035317, A055809, A055810, A078739, A122193, A062208.

Row n=2 of A262809.

Sequence in context: A075672 A069876 A126086 * A088919 A201537 A258178

Adjacent sequences: A055200 A055201 A055202 * A055204 A055205 A055206

nonn,nice,easy

Sylviane R. Schwer (schwer(AT)lipn.univ-paris13.fr), Jun 22 2000

More terms from Larry Reeves (larryr(AT)acm.org), Oct 04 2000

More terms from N. J. A. Sloane, Jan 03 2001

approved