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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 15 22:20 EST 2018. Contains 317252 sequences. (Running on oeis4.)