login
This site is supported by donations 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. 12
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

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

Tim Fernando, 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 thesis, 30 ECTS | Datateknik 2016 | LIU-IDA/LITH-EX-A--16/022--SE.

FORMULA

a(n) = Sum_(i = 2 to 2n) lambda(i, n), with lambda(p, 1) = if p = 2 then 1 else 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

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

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 15 16:12 EDT 2019. Contains 327078 sequences. (Running on oeis4.)