Alexander Malkis - cp's OEIS frontend

User: Alexander Malkis

Alexander Malkis has authored 3 sequences.

A290642 a(n) is the maximum diameter for an n-threaded binary program. In other words, a(n) is the maximal finite distance in the transition graph of an n-threaded binary program.

3, 7, 13, 14, 15, 18

Offset: 1

Alexander Malkis, Aug 08 2017

Here, a binary n-threaded program is a multithreaded program with n threads, two local states per thread, and 2 shared states.

Conjecture: a(n) = 3*n for all n >= 5.

Alexander Malkis, Reachability in Multithreaded Programs Is Polynomial in the Number of Threads (Version with Proofs), Technical University of Munich (Germany, 2019).
Alexander Malkis and Steffen Borgwardt, Reachability in Binary Multithreaded Programs Is Polynomial, ICDCS'17, IEEE, 2017, pages 2083-2088.

A008585(n) <= a(n) for all n >= 1.

a(n) >= 3*n for all n >= 1.

a(n) <= n^{2^{13}} for all n >= 2.

Name edited by Michel Marcus, Jan 02 2020

A097472 Number of different candle trees having a total of m edges.

Original entry on oeis.org

1, 3, 10, 31, 96, 296, 912, 2809, 8651, 26642, 82047, 252672, 778128, 2396320, 7379697, 22726483, 69988378, 215535903, 663763424, 2044122936, 6295072048, 19386276329, 59701891739, 183857684514, 566207320575, 1743689586432

Offset: 0

Alexander Malkis, Sep 18 2004

A candle tree is a graph on the plane square lattice Z X Z whose edges have length one with the following properties: (a) It contains a line segment ("trunk") of length from 0 to m on the vertical axis, its lowest node is at the origin. (b) It contains horizontal line segments ("branches"); each of them intersects the trunk. (c) Each branch is allowed to have "candles", which are vertical edges of length 1, whose lower node is on a branch.

Row sums of triangle in A238241. - Philippe Deléham, Feb 21 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Alexander Malkis, Polyedges, polyominoes and the 'Digit' game, diploma thesis in computer science, Universität des Saarlandes, 2003, Saarbrücken.
Index entries for linear recurrences with constant coefficients, signature (3,1,-2,-1).

Bisection of A060945 and |A077930|.

CoefficientList[Series[1/(x^4+2x^3-x^2-3x+1),{x,0,30}],x] (* or *) LinearRecurrence[{3,1,-2,-1},{1,3,10,31},30] (* Harvey P. Dale, Jun 14 2011 *)

a(n):=sum(sum(binomial(k,n-m-k+1)*binomial(k+2*m-1,2*m-1),k,1,n-m+1),m,1,n)+1; /* Vladimir Kruchinin, May 12 2011 */

a(n)=sum(m=1,n,sum(k=1,n-m+1,binomial(k,n-m-k+1)*binomial(k+2*m-1,2*m-1))) \\ Charles R Greathouse IV, Jun 17 2013

a(n) = Sum_{s, d, k>=0 with s+d+k=m} binomial(s+2d+1, s)*binomial(s, k);
generating function = 1/((1-x)*(1-2*x-3*x^2-x^3)).
a(n) = 3*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4);
a(n) = 1 + Sum_{m=1..n} Sum_{k=1..n-m+1} binomial(k, n-m-k+1)*binomial(k+2*m-1,2*m-1). - Vladimir Kruchinin, May 12 2011
a(n) = Sum_{k=0..n} A238241(n,k). - Philippe Deléham, Feb 21 2014
a(n) - a(n-1) = A218836(n). - R. J. Mathar, Jun 17 2020

A096267 Number of fixed polyedges with n edges (number of ways of embedding connected undirected graphs with n edges into the plane square lattice, inequivalent up to translation).

Original entry on oeis.org

2, 6, 22, 88, 372, 1628, 7312, 33466, 155446, 730534, 3466170, 16576874, 79810756, 386458826, 1880580352, 9190830700, 45088727820, 221945045488, 1095798917674, 5424898610958, 26922433371778, 133906343014110, 667370905196930, 3332257266746004

Offset: 1

Alexander Malkis, Jun 22 2004

nonn

Found using the rooted method (also known as Redelmeier's algorithm).

			_|_|_ is a polyedge with 5 edges

Alexander Malkis, Polyedges, polyominoes and the 'Digit' game, diploma thesis in computer science, Universität des Saarlandes, 2003, Saarbrücken.
Stephan Mertens and Cristopher Moore, Series expansion of the percolation threshold on hypercubic lattices, J. Phys. A: Math. Theor., 51 (2018), 475001. See Table 1.

Cf. A019988 for "free" polyedges, A348096.

6th row of A366767.

a(22)-a(24) from Mertens & Moore added by Andrey Zabolotskiy, Feb 01 2022

cp's OEIS Frontend

User: Alexander Malkis

A290642 a(n) is the maximum diameter for an n-threaded binary program. In other words, a(n) is the maximal finite distance in the transition graph of an n-threaded binary program.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A097472 Number of different candle trees having a total of m edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

A096267 Number of fixed polyedges with n edges (number of ways of embedding connected undirected graphs with n edges into the plane square lattice, inequivalent up to translation).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions