A259966 -id:A259966 - cp's OEIS frontend

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

David Callan, Aug 01 2004

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

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

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

Row sums give A005251(n+2).
Cf. A180177 (same sequence with rows reversed).
Cf. A259966, A332863.

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

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

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)

A332863 Total binary weight squared of all A005251(n) binary sequences of length n not containing any isolated 1's.

Original entry on oeis.org

0, 0, 4, 17, 46, 116, 288, 683, 1548, 3403, 7320, 15461, 32146, 65954, 133800, 268804, 535434, 1058533, 2078732, 4057858, 7878814, 15223495, 29285368, 56109673, 107108104, 203766859, 386443052, 730768044, 1378180568, 2592664120, 4866008208, 9112796113

Offset: 0

Steven Finch, Feb 27 2020

			The only two 2-bitstrings without isolated 1's are 00 and 11.  The bitsums squared of these are 0 and 4.  Adding these give a(2)=4.
The only four 3-bitstrings without isolated 1's are 000, 011, 110 and 111.  The bitsums squared of these are 0, 4, 4 and 9.  Adding these give a(3)=17.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
Index entries for linear recurrences with constant coefficients, signature (6,-15,23,-27,24,-16,9,-3,1).

Cf. A005251, A097230, A259966.

R:=PowerSeriesRing(Integers(), 40); [0,0] cat Coefficients(R!( x^2*(4-7*x+4*x^2+3*x^3-x^4)/(1-2*x+x^2-x^3)^3 )); // G. C. Greubel, Apr 13 2022

LinearRecurrence[{6,-15,23,-27,24,-16,9,-3,1}, {0,0,4,17,46,116,288,683,1548}, 40] (* G. C. Greubel, Apr 13 2022 *)

def A332863_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x^2*(4-7*x+4*x^2+3*x^3-x^4)/(1-2*x+x^2-x^3)^3 ).list()
A332863_list(40) # G. C. Greubel, Apr 13 2022

G.f.: x^2*(4-7*x+4*x^2+3*x^3-x^4)/(1-2*x+x^2-x^3)^3.

a(n) = Sum_{k=1..n} k^2 * A097230(n,k). - Alois P. Heinz, Mar 03 2020

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula