A218796 -id:A218796 - cp's OEIS frontend

A049856 a(n) = (Sum{k=0..n-1} a(k)) - a(n-3), with a(0)=0, a(1)=0, a(2)=1.

0, 0, 1, 1, 2, 3, 6, 11, 21, 39, 73, 136, 254, 474, 885, 1652, 3084, 5757, 10747, 20062, 37451, 69912, 130509, 243629, 454797, 848997, 1584874, 2958580, 5522960, 10310043, 19246380, 35928380, 67069677, 125203017, 233724034, 436306771, 814480202, 1520439387

Offset: 0

Clark Kimberling

a(n+3) is also the number of binary words w of length n with the condition that every subword 11 of w is part of a longer subword of w containing only 1-digits. The a(3+3)=6 binary words of length 3 are 000, 001, 010, 100, 101, 111. - Alois P. Heinz, Mar 25 2009
a(n+2) is the number of compositions of n avoiding the part 3. [Joerg Arndt, Jul 13 2014]
Starting with 1 = INVERT transform of (1,1,0,1,1,1,...). Example: a(9) = 39 = (1,1,2,3,6,11,21) dot (1,1,1,1,0,1,1) = (1+1+2+3+0+11+21). - Gary W. Adamson, Apr 27 2009
For n>=4, a(n) is the number of binary strings of length n-3 without any maximal runs of ones of length 2. - Félix Balado, Aug 25 2025

Alois P. Heinz, Table of n, a(n) for n = 0..1000
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, example 11.
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3
J. J. Madden, A generating function for the distribution of runs in binary words, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=3, k=0.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1).

Cf. A049858.

a:= n-> -(Matrix(4, (i, j)-> if i=j-1 then 1 elif j=1 then [2, 0, -1, 1][i] else 0 fi)^n)[3, 2]: seq (a(n), n=0..40); # Alois P. Heinz, Mar 25 2009

LinearRecurrence[{2,0,-1,1},{0,0,1,1},40] (* Harvey P. Dale, Jul 23 2013 *)

a(n) = 2*a(n-1) - a(n-3) + a(n-4) for n >= 4.
a(n+2) = Sum_{i=0..n} F(i+1)*C(n-i,i) where F=A000045. - Benoit Cloitre, Sep 21 2004
G.f.: x^2*(1-x)/(1-2*x+x^3-x^4). - Vladimir Kruchinin, May 11 2011
a(n) = A218796(n-2,0) for n>1. - Alois P. Heinz, Nov 06 2012
a(n) = A059633(n+1) - A059633(n). - R. J. Mathar, Aug 04 2019

A386891 Irregular triangle read by rows: T(n,k) is the number of compositions of n such that the maximal cardinality of C is k, where C is a subset of the set of parts such that all elements in C appear in weakly increasing order within the composition.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 3, 1, 0, 6, 2, 0, 11, 5, 0, 21, 10, 1, 0, 39, 23, 2, 0, 74, 49, 5, 0, 139, 107, 10, 0, 271, 216, 24, 1, 0, 524, 447, 51, 2, 0, 1031, 895, 117, 5, 0, 2023, 1813, 250, 10, 0, 3998, 3630, 544, 20, 0, 7878, 7344, 1115, 46, 1, 0, 15601, 14738, 2330, 97, 2

Offset: 0

John Tyler Rascoe, Aug 06 2025

Here the set of parts of a composition is the set of all parts appearing in the composition.

			Triangle begins:
    k=0    1    2   3  4
 n=0  1,
 n=1  0,   1,
 n=2  0,   2,
 n=3  0,   3,   1,
 n=4  0,   6,   2,
 n=5  0,  11,   5,
 n=6  0,  21,  10,  1,
 n=7  0,  39,  23,  2,
 n=8  0,  74,  49,  5,
 n=9  0, 139, 107, 10,
 n=10 0, 271, 216, 24, 1,
...
The composition of n = 3 (2,1) with set of parts {1,2} has maximal subsets {1} and {2} both with all parts appearing in weakly increasing order, so (2,1) is counted under T(3,1) = 3.
The composition of n = 15 (3,1,1,2,3,5) with set of parts {1,2,3,5} has the maximal subset {1,2,5}, so (3,1,1,2,3,5) is counted under T(15,3) = 1115.

John Tyler Rascoe, Python code.

Cf. A002024 (row lengths), A011782 (row sums).

Cf. A218796, A333213, A374629, A385604.

Python
```
# see links
```

cp's OEIS Frontend

A049856 a(n) = (Sum{k=0..n-1} a(k)) - a(n-3), with a(0)=0, a(1)=0, a(2)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula