A097230 Triangle read by rows: number of binary sequences with no isolated 1's.

1, 1, 0, 1, 0, 1, 1, 0, 2, 1, 1, 0, 3, 2, 1, 1, 0, 4, 3, 3, 1, 1, 0, 5, 4, 6, 4, 1, 1, 0, 6, 5, 10, 9, 5, 1, 1, 0, 7, 6, 15, 16, 13, 6, 1, 1, 0, 8, 7, 21, 25, 26, 18, 7, 1, 1, 0, 9, 8, 28, 36, 45, 40, 24, 8, 1, 1, 0, 10, 9, 36, 49, 71, 75, 59, 31, 9, 1, 1, 0, 11, 10, 45, 64, 105, 126, 120, 84, 39, 10, 1

Offset

0,9

Comments

T(n,k) = number of 0-1 sequences of length n with exactly k 1's, none of which is isolated.

Links

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

Formula

G.f.: (1-x*y+x^2*y^2)/( (1-x)*(1-x*y) -x^3*y^2 ) = Sum_{n>=0, k>=0} T(n,k) x^n y^k.

From Alois P. Heinz, Mar 03 2020: (Start)

Sum_{k=1..n} k * T(n,k) = A259966(n).

Sum_{k=1..n} k^2 * T(n,k) = A332863(n). (End)

Example

T(6,4) = 6 counts 001111, 011011, 011110, 110011, 110110, 111100.
Table begins:
\ k 0, 1, 2,
n
0 | 1;
1 | 1, 0;
2 | 1, 0, 1;
3 | 1, 0, 2, 1;
4 | 1, 0, 3, 2,  1;
5 | 1, 0, 4, 3,  3,  1;
6 | 1, 0, 5, 4,  6,  4,  1;
7 | 1, 0, 6, 5, 10,  9,  5, 1;
8 | 1, 0, 7, 6, 15, 16, 13, 6, 1;
    ...

Maple

b:= proc(n, w, s) option remember; `if`(n=0,
      `if`(s in [1, 21], 0, x^w), `if`(s in [1, 21], 0,
       b(n-1, w, irem(s, 10)*10))+b(n-1, w+1, irem(s, 10)*10+1))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0, 22)):
seq(T(n), n=0..14);  # Alois P. Heinz, Mar 03 2020

Mathematica

a[n_, 0]/; n>=0 := 1; a[n_, k_]/; k>n || k<0 :=0; a[n_, 1]:=0; a[2, 2]=1; a[n_, k_]/; n>=3 && 2 <= k <= n := a[n, k] = 1 + Sum[a[n-(r+1), k-j], {r, 2, n-1}, {j, Max[2, r-1-(n-k)], Min[r, k]}] (* This recurrence counts a(n, k) by r = location of first 1 followed by a 0, j = length of run which this first 1 terminates. *)

Crossrefs

Row sums give A005251(n+2).

Cf. A180177 (same sequence with rows reversed).

Cf. A259966, A332863.

Sequence in context: A085144 A156578 A171846 * A144789 A285097 A279209

Adjacent sequences: A097227 A097228 A097229 * A097231 A097232 A097233

Keyword

nonn,tabl

Author

David Callan, Aug 01 2004

Status

approved