cp's OEIS Frontend

A076791 Triangle a(n,k) giving number of binary sequences of length n containing k subsequences 00.

%I A076791 #66 Jan 05 2025 19:51:37
%S A076791 1,2,3,1,5,2,1,8,5,2,1,13,10,6,2,1,21,20,13,7,2,1,34,38,29,16,8,2,1,
%T A076791 55,71,60,39,19,9,2,1,89,130,122,86,50,22,10,2,1,144,235,241,187,116,
%U A076791 62,25,11,2,1,233,420,468,392,267,150,75,28,12,2,1,377,744,894,806,588,363,188,89,31,13,2,1
%N A076791 Triangle a(n,k) giving number of binary sequences of length n containing k subsequences 00.
%C A076791 The triangle of numbers of n-sequences of 0,1 with k subsequences of consecutive 01 is A034867 because this number is C(n+1,2*k+1). I have not yet found a formula for subsequences 00.
%C A076791 The problem is equivalent to one encountered by David W. Wilson, Dept of Geography, University of Southampton, UK, in his work on Markov models for rainfall disaggregation. He asked for the number of ways in which there can be k instances of adjacent rainy days in a period of n consecutive days. Representing a rainy day by 0 and a fine day by 1, the problem is equivalent to that solved by this sequence. - E. Keith Lloyd (ekl(AT)soton.ac.uk), Nov 29 2004
%C A076791 Row n (n>=1) contains n terms.
%C A076791 Triangle, with zeros omitted, given by (2, -1/2, -1/2, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (0, 1/2, 1/2, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - _Philippe Deléham_, Dec 12 2011
%C A076791 a(n-1,k) is also the number of permutations avoiding both 132 and 213 with k double descents, i.e., positions with w[i]>w[i+1]>w[i+2]. - _Lara Pudwell_, Dec 19 2018
%H A076791 Alois P. Heinz, <a href="/A076791/b076791.txt">Rows n = 0..150, flattened</a>
%H A076791 M. Bukata, R. Kulwicki, N. Lewandowski, L. Pudwell, J. Roth, and T. Wheeland, <a href="https://arxiv.org/abs/1812.07112">Distributions of Statistics over Pattern-Avoiding Permutations</a>, arXiv preprint arXiv:1812.07112 [math.CO], 2018.
%H A076791 L. Carlitz and R. Scoville, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/15-3/carlitz1.pdf">Zero-one sequences and Fibonacci numbers</a>, Fibonacci Quarterly, 15 (1977), 246-254.
%H A076791 Toufik Mansour and Armend Sh. Shabani, <a href="https://doi.org/10.3906/mat-1803-113">Bargraphs in bargraphs</a>, Turkish Journal of Mathematics (2018) Vol. 42, Issue 5, 2763-2773.
%H A076791 Paul M. Rakotomamonjy, Sandrataniaina R. Andriantsoa, and Arthur Randrianarivony, <a href="https://arxiv.org/abs/1910.13809">Crossings over permutations avoiding some pairs of three length-patterns</a>, arXiv:1910.13809 [math.CO], 2019.
%F A076791 Recurrence: a(n, k) = (a(n-1, k) + a(n-2, k)) + (a(n-3, k-1) + a(n-4, k-2) + ... + a(n-k-2, 0)).
%F A076791 Special values: a(n, 0) = Fibonacci(n+1); a(n, n-1) = 1 for n >= 2; a(n, n-2) = 2 for n >= 3; a(n, n-3) = n + 1 for n >= 4, etc.
%F A076791 a(n, n-4) = 3*n - 5 for n >= 5, a(n, n-5) = (n^2 + 5*n - 26)/2 for n >= 6, a(n, n-6) = 2*n^2 - 8*n - 4, for n >= 7 etc.
%F A076791 Recurrence relation: a(n+1, k) = a(n, k) + a(n-1, k) + a(n, k-1) - a(n-1, k-1) for k >= 1, n >= 1.
%F A076791 Generating function: a(n, k) is coefficient of x^n in ((x^(k + 1))*((1 - x)^(k - 1)))/((1 - x - x^2)^(k + 1)) for k >= 1. - E. Keith Lloyd (ekl(AT)soton.ac.uk), Nov 29 2004
%F A076791 G.f.: (1 + (1 - t)*x)/(1 - (1 + t)*x - (1 - t)*x^2). [Carlitz-Scoville] - _Emeric Deutsch_, May 19 2006
%F A076791 A076791 is jointly generated with A053538 as an array of coefficients of polynomials u(n,x):  initially, u(1,x) = v(1,x) = 1; for n > 1, u(n,x) = x*u(n-1,x) + v(n-1)*x and v(n,x) = u(n-1,x) + v(n-1,x).  See the Mathematica section. - _Clark Kimberling_, Mar 08 2012
%e A076791 a(5,2) = 6 because the binary sequences of length 5 with 2 subsequences 00 are 10001, 11000, 01000, 00100, 00010, 00011.
%e A076791 Triangle begins
%e A076791    1;
%e A076791    2;
%e A076791    3,  1;
%e A076791    5,  2, 1;
%e A076791    8,  5, 2, 1;
%e A076791   13, 10, 6, 2, 1;
%e A076791   ...
%p A076791 b:= proc(n, l) option remember; `if`(n=0, 1,
%p A076791       expand(b(n-1, 1)*x^l)+b(n-1, 0))
%p A076791     end:
%p A076791 T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
%p A076791 seq(T(n), n=0..14);  # _Alois P. Heinz_, Sep 17 2019
%t A076791 f[list_] := Select[list, #>0&]; nn=10; a=1/(1-y x); b= x/(1-y x) +1; c=1/(1-x); Map[f, CoefficientList[Series[c b/(1-(a x^2 c)), {x,0,nn}], {x,y}]]//Flatten (* _Geoffrey Critzer_, Mar 05 2012 *)
%t A076791 u[1, x_] := 1; v[1, x_] := 1; z = 16;
%t A076791 u[n_, x_] := x*u[n - 1, x] + v[n - 1, x];
%t A076791 v[n_, x_] := u[n - 1, x] + v[n - 1, x];
%t A076791 Table[Expand[u[n, x]], {n, 1, z/2}]
%t A076791 Table[Expand[v[n, x]], {n, 1, z/2}]
%t A076791 cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
%t A076791 TableForm[cu]
%t A076791 Flatten[%]    (* A053538 *)
%t A076791 Table[Expand[v[n, x]], {n, 1, z}]
%t A076791 cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
%t A076791 TableForm[cv]
%t A076791 Flatten[%]    (* A076791 *)
%t A076791 (* _Clark Kimberling_, Mar 08 2012 *)
%t A076791 T[ n_, k_] := If[n<2, (n+1)*Boole[n > -1 && k == 0], T[n, k] = T[n-1, k] + T[n-1, k-1] + T[n-2, k] - T[n-2, k-1] ]; (* _Michael Somos_, Sep 21 2024 *)
%o A076791 (PARI) {T(n, k) = if(n<2, (n+1)*(n > -1 && k == 0), T(n-1, k) + T(n-1, k-1) + T(n-2, k) - T(n-2, k-1) )}; /* _Michael Somos_, Sep 21 2024 */
%Y A076791 Cf. a(n,1) = A001629, a(n,2) = A055243.
%K A076791 nonn,tabf
%O A076791 0,2
%A A076791 _Roger Cuculière_, Nov 16 2002
%E A076791 More terms from E. Keith Lloyd (ekl(AT)soton.ac.uk), Nov 29 2004