cp's OEIS Frontend

A003440 Number of binary vectors with restricted repetitions.

%I A003440 M2666 #50 Jul 06 2023 01:55:37
%S A003440 1,1,3,7,17,42,104,259,648,1627,4098,10350,26202,66471,168939,430071,
%T A003440 1096451,2799072,7154189,18305485,46885179,120195301,308393558,
%U A003440 791882862,2034836222,5232250537,13462265079,34657740889,89272680921,230069128392
%N A003440 Number of binary vectors with restricted repetitions.
%C A003440 The sum of squared terms in row n of A104402 = 2*a(n) for n>0. - _Paul D. Hanna_, Mar 06 2005
%C A003440 From _Jean-Pierre Levrel_, Nov 26 2014: (Start)
%C A003440 The title "Binary Sequences with Restricted Repetitions," given the A003440 series, does not specify the type of restrictions used. After reading the article by K. A. Post, "Binary Sequences with Restricted Repetitions," it appears that the A003440 series corresponds to the following cases:
%C A003440 - Number of repetitions limited to two,
%C A003440 - Each sequence must begin with a zero.
%C A003440 It is important to consider these two hypotheses to interpret the series. I also think that the second constraint is not useful and could usefully be deleted. In this case, the series should be doubled from the second term and would become 1, 2, 6, 14, 34, 84, ..., i.e., A177790.
%C A003440 (End)
%D A003440 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003440 Vincenzo Librandi, <a href="/A003440/b003440.txt">Table of n, a(n) for n = 0..1000</a>
%H A003440 Jean-Luc Baril and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/pathwall.pdf">Fibonacci and Catalan paths in a wall</a>, 2023.
%H A003440 K. A. Post, <a href="http://alexandria.tue.nl/repository/books/252858.pdf">Binary Sequences with Restricted Repetitions</a>, Report 74-WSK-02, Math. Dept., Tech. Univ. Eindhoven, May. 1974.
%F A003440 G.f.: {(1-x)^2 * sqrt[(1+x+x^2)/(1-3x+x^2)] + x^2 - 1}/(2x^2) (conjectured). - _Ralf Stephan_, Mar 28 2004
%F A003440 a(n) = Sum_{k=0..n} (C(k, n-k) + C(k+1, n-k-1))^2/2 for n>0, with a(0)=1. - _Paul D. Hanna_, Mar 06 2005
%F A003440 Conjecture: (n+2)*a(n) +3*(-n-1)*a(n-1) +(n-2)*a(n-2) +(-n+1)*a(n-3) +3*(n-4)*a(n-4) +(-n+5)*a(n-5)=0. - _R. J. Mathar_, Jun 07 2013
%F A003440 Recurrence: (n-2)*(n-1)*(n+2)*a(n) = 2*(n-2)*n*(n+1)*a(n-1) + (n-1)*(n^2 - 2*n - 4)*a(n-2) + 2*(n-3)*(n-2)*n*a(n-3) - (n-4)*(n-1)*n*a(n-4). - _Vaclav Kotesovec_, Feb 12 2014
%F A003440 a(n) ~ sqrt(6+14/sqrt(5)) * (3+sqrt(5))^n / (sqrt(Pi*n) * 2^(n+1)). - _Vaclav Kotesovec_, Feb 12 2014
%F A003440 Equivalently, a(n) ~ phi^(2*n + 2) / (5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - _Vaclav Kotesovec_, Dec 08 2021
%t A003440 Flatten[{1,Table[Sum[(Binomial[k,n-k]+Binomial[k+1,n-k-1])^2/2,{k,0,n}],{n,1,20}]}] (* _Vaclav Kotesovec_, Feb 12 2014 *)
%t A003440 a[r_, s_] /; r<0 || s<0 = 0; a[r_ /; 0 <= r <= 2, 0] = 1; a[r_ /; r>2, 0] = 0; a[0, s_ /; s >= 1] = 0; a[r_, s_] := a[r, s] = a[r-2, s-2] + a[r-2, s-1] + a[r-1, s-2] + a[r-1, s-1]; a[n_] := a[n, n]; Table[a[n], {n, 0, 29}] (* _Jean-François Alcover_, Jan 19 2015, after given recurrence *)
%o A003440 (PARI) {a(n)=polcoeff(((1-x)^2*sqrt((1+x+x^2)/(1-3*x+x^2))+x^2-1)/(2*x^2)+x*O(x^n),n)} \\ _Paul D. Hanna_, Mar 06 2005
%o A003440 (PARI) {a(n)=if(n==0,1,sum(k=0,n,(binomial(k,n-k)+binomial(k+1,n-k-1))^2)/2)} \\ _Paul D. Hanna_, Mar 06 2005
%Y A003440 Cf. A078678, A104402, A177790.
%K A003440 nonn
%O A003440 0,3
%A A003440 _N. J. A. Sloane_
%E A003440 Typo in second formula corrected by _Vaclav Kotesovec_, Feb 12 2014
%E A003440 More terms from _Vincenzo Librandi_, Feb 13 2014