|
| |
|
|
A097230
|
|
Triangle read by rows: number of binary sequences with no isolated 1's.
|
|
0
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
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.
|
|
|
FORMULA
| G.f.: (1-x*y+x^2*y^2)/( (1-x)(1-x*y) -x^3*y^2 ) = Sum_{n>=0, k>=0} a(n, k) x^n y^k.
|
|
|
EXAMPLE
| 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
T(6,4) = 6 counts 001111, 011011, 011110, 110011, 110110, 111100.
|
|
|
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 are A005251.
Sequence in context: A085144 A156578 A171846 * A144789 A087117 A029340
Adjacent sequences: A097227 A097228 A097229 * A097231 A097232 A097233
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| David Callan (callan(AT)stat.wisc.edu), Aug 01 2004
|
| |
|
|
