|
%I #56 Jan 21 2020 00:03:41
%S 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 55,71,60,39,19,9,2,1,89,130,122,86,50,22,10,2,1,144,235,241,187,116,
%U 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 Triangle a(n,k) giving number of binary sequences of length n containing k subsequences 00.
%C 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 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 Row n (n>=1) contains n terms.
%C 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 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 Alois P. Heinz, <a href="/A076791/b076791.txt">Rows n = 0..150, flattened</a>
%H 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 L. Carlitz and R. Scoville, <a href="http://www.fq.math.ca/Scanned/15-3/carlitz1.pdf">Zero-one sequences and Fibonacci numbers</a>, Fibonacci Quarterly, 15 (1977), 246-254.
%H Toufik Mansour, 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 Paul M. Rakotomamonjy, Sandrataniaina R. Andriantsoa, 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 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 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 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 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 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 G.f.: (1 + (1 - t)*x)/(1 - (1 + t)*x - (1 - t)*x^2). [Carlitz-Scoville] - _Emeric Deutsch_, May 19 2006
%F 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 a(5,2) = 6 because the binary sequences of length 5 with 2 subsequences 00 are 10001, 11000, 01000, 00100, 00010, 00011.
%e Triangle begins
%e 1;
%e 2;
%e 3, 1;
%e 5, 2, 1;
%e 8, 5, 2, 1;
%e 13, 10, 6, 2, 1;
%e ...
%p b:= proc(n, l) option remember; `if`(n=0, 1,
%p expand(b(n-1, 1)*x^l)+b(n-1, 0))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
%p seq(T(n), n=0..14); # _Alois P. Heinz_, Sep 17 2019
%t 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 u[1, x_] := 1; v[1, x_] := 1; z = 16;
%t u[n_, x_] := x*u[n - 1, x] + v[n - 1, x];
%t v[n_, x_] := u[n - 1, x] + v[n - 1, x];
%t Table[Expand[u[n, x]], {n, 1, z/2}]
%t Table[Expand[v[n, x]], {n, 1, z/2}]
%t cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
%t TableForm[cu]
%t Flatten[%] (* A053538 *)
%t Table[Expand[v[n, x]], {n, 1, z}]
%t cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
%t TableForm[cv]
%t Flatten[%] (* A076791 *)
%t (* _Clark Kimberling_, Mar 08 2012 *)
%Y Cf. a(n,1) = A001629, a(n,2) = A055243.
%K nonn,tabf
%O 0,2
%A _Roger Cuculière_, Nov 16 2002
%E More terms from E. Keith Lloyd (ekl(AT)soton.ac.uk), Nov 29 2004
|
