login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A076791 Triangle a(n,k) giving number of binary sequences of length n containing k subsequences 00. 7
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, 55, 71, 60, 39, 19, 9, 2, 1, 89, 130, 122, 86, 50, 22, 10, 2, 1, 144, 235, 241, 187, 116, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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.

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

Row n (n>=1) contains n terms.

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

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

LINKS

Alois P. Heinz, Rows n = 0..150, flattened

M. Bukata, R. Kulwicki, N. Lewandowski, L. Pudwell, J. Roth, and T. Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv preprint arXiv:1812.07112 [math.CO], 2018.

L. Carlitz and R. Scoville, Zero-one sequences and Fibonacci numbers, Fibonacci Quarterly, 15 (1977), 246-254.

Toufik Mansour, Armend Sh. Shabani, Bargraphs in bargraphs, Turkish Journal of Mathematics (2018) Vol. 42, Issue 5, 2763-2773.

FORMULA

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)).

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.

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.

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.

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

G.f.: (1 + (1 - t)*x)/(1 - (1 + t)*x - (1 - t)*x^2). [Carlitz-Scoville] - Emeric Deutsch, May 19 2006

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

EXAMPLE

a(5,2) = 6 because the binary sequences of length 5 with 2 subsequences 00 are 10001, 11000, 01000, 00100, 00010, 00011.

Triangle begins

   1;

   2;

   3,  1;

   5,  2, 1;

   8,  5, 2, 1;

  13, 10, 6, 2, 1;

  ...

MAPLE

b:= proc(n, l) option remember; `if`(n=0, 1,

      expand(b(n-1, 1)*x^l)+b(n-1, 0))

    end:

T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):

seq(T(n), n=0..14);  # Alois P. Heinz, Sep 17 2019

MATHEMATICA

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 *)

u[1, x_] := 1; v[1, x_] := 1; z = 16;

u[n_, x_] := x*u[n - 1, x] + v[n - 1, x];

v[n_, x_] := u[n - 1, x] + v[n - 1, x];

Table[Expand[u[n, x]], {n, 1, z/2}]

Table[Expand[v[n, x]], {n, 1, z/2}]

cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];

TableForm[cu]

Flatten[%]    (* A053538 *)

Table[Expand[v[n, x]], {n, 1, z}]

cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];

TableForm[cv]

Flatten[%]    (* A076791 *)

(* Clark Kimberling, Mar 08 2012 *)

CROSSREFS

Cf. a(n,1) = A001629, a(n,2) = A055243.

Sequence in context: A189074 A255973 A169615 * A246177 A246185 A247469

Adjacent sequences:  A076788 A076789 A076790 * A076792 A076793 A076794

KEYWORD

nonn,tabf,changed

AUTHOR

Roger Cuculière, Nov 16 2002

EXTENSIONS

More terms from E. Keith Lloyd (ekl(AT)soton.ac.uk), Nov 29 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 14 12:02 EDT 2019. Contains 328004 sequences. (Running on oeis4.)