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

Author

David Callan, Aug 01 2004

Keywords

• nonn
• tabl

Comments

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

Examples

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

Links

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

Crossrefs

Row sums give A005251(n+2).

Cf. A180177 (same sequence with rows reversed).

Cf. A259966, A332863.

Programs

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

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)