The On-Line Encyclopedia of Integer Sequences (OEIS)

Revision History for A078678 (Bold, blue-underlined text is an addition; faded, red-underlined text is a ~~deletion~~.)
Showing entries 1-10 | older changes

A078678

Number of binary strings with n 1's and n 0's avoiding zigzags, that is avoiding the substrings 101 and 010.
(history; published version)

#37 by Alois P. Heinz at Thu Aug 27 19:33:02 EDT 2020

STATUS

proposed

approved

#36 by Michael De Vlieger at Thu Aug 27 19:14:01 EDT 2020

STATUS

editing

proposed

#35 by Michael De Vlieger at Thu Aug 27 19:14:00 EDT 2020

LINKS

Andrei Asinowski, Cyril Banderier, <a href="https://doi.org/10.4230/LIPIcs.AofA.2020.1">On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution</a>, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.

STATUS

approved

editing

#34 by Alois P. Heinz at Thu Feb 13 15:58:27 EST 2020

STATUS

editing

approved

#33 by Alois P. Heinz at Thu Feb 13 12:42:20 EST 2020

DATA

1, 2, 4, 8, 18, 42, 100, 242, 592, 1460, 3624, 9042, 22656, 56970, 143688, 363348, 920886, 2338566, 5949148, 15157874, 38674978, 98803052, 252701484, 646990518, 1658066668, 4252908542, 10917422860, 28046438252, 72099983802, 185469011130, 477383400300

#32 by Alois P. Heinz at Thu Feb 13 12:34:45 EST 2020

CROSSREFS

Cf. A078679, A128588.

#31 by Alois P. Heinz at Thu Feb 13 12:24:03 EST 2020

MAPLE

a:= proc(n) option remember; `if`(n<5, [1, 2, 4, 8, 18][n+1],

(2*n*a(n-1)+(n-2)*a(n-2)+(2*n-8)*a(n-3)-(n-4)*a(n-4))/n)

end:

seq(a(n), n=0..40); # Alois P. Heinz, Feb 13 2020

STATUS

reviewed

editing

#30 by Joerg Arndt at Thu Feb 13 06:54:07 EST 2020

STATUS

proposed

reviewed

Discussion

Thu Feb 13

11:54

Michel Marcus: for me it works ?

11:55

Michel Marcus: with pari: a(n) = sum(k=0, n+floor(n/2), binomial( n - k + 2*floor(k/3), floor(k/3) )^2) and then vector(50, n, (n+6)*a(n+6) - (n+7)*a(n+5) - 2*(n+5)*a(n+4) - 5*(n+3)*a(n+3) - 2*(n+1)*a(n+2) - (n-1)*a(n+1) + n*a(n))

12:22

Alois P. Heinz: first recurrence worked but the order was larger than needed, ...

#29 by Georg Fischer at Thu Feb 13 06:14:38 EST 2020

STATUS

editing

proposed

#28 by Georg Fischer at Thu Feb 13 06:13:40 EST 2020

FORMULA

Recurrence: 0 = (n+6)*a(n+6) - (n+7)*a(n+5) - 2*(n+5)*a(n+4) - 5*(n+3)*a(n+3) - 2*(n+1)*a(n+2) - (n-1)*a(n+1) + n*a(n).

D-finite with recurrence: n*a(n) -2*n*a(n-1) +(-n+2)*a(n-2) +2*(-n+4)*a(n-3) +(n-4)*a(n-4)=0. [Doslic] - R. J. Mathar, Jun 21 2018

STATUS

approved

editing

Discussion

Thu Feb 13

06:14

Georg Fischer: The first recurrence did not work.