OFFSET
1,2
COMMENTS
a(n-1) is the sum, over all Boolean n-strings, of the product of the lengths of the runs. For example, the Boolean 7-string (0,1,1,0,1,1,1) has four runs, whose lengths are 1,2,1 and 3, contributing a product of 6 to a(6). The 4 Boolean 2-strings contribute to a(3) as follows: 00 and 11 both contribute 2 and 01 and 10 both contribute 1. - David Callan, Jul 22 2008
a(n) = A025169(n-2) for n > 1. - Reinhard Zumkeller, Apr 08 2012
The sequence 0, 2, 0, 0, 1, 2, 6, 16, 42, 110, 288, 754, 1974, ... with g.f. H(x) = 2*x+(x^4-x^5+x^6)/(1-3*x+x^2) is the number of "splitted indecomposable weakly threshold graphs" on n nodes [Barrus, 2016]. - N. J. A. Sloane, Jul 25 2017
Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {2>1, 2>4} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the second element is larger than the first and fourth elements. - Sergey Kitaev, Dec 09 2020
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
M. Albert, R. Aldred, M. Atkinson, C. Handley, D. Holton, D. McCaughan and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb. 12 (2005) #R31.
Michael D. Barrus, Weakly threshold graphs, arXiv preprint arXiv:1608.01358 [math.CO], 2016.
Hacène Belbachir, Soumeya Merwa Tebtoub, and László Németh, Ellipse Chains and Associated Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.5.
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Index entries for linear recurrences with constant coefficients, signature (3, -1).
FORMULA
a(n) = 3a(n-1) - a(n-2), n > 3.
a(n) = A025169(n-2), n > 1. - R. J. Mathar, Aug 18 2008
From Paul Barry, Oct 13 2009: (Start)
G.f.: (1 - x + x^2)/(1 - 3x + x^2).
a(n) = F(2n+1) + F(2n-2) + 0^n. (End)
EXAMPLE
x + 2*x^2 + 6*x^3 + 16*x^4 + 42*x^5 + 110*x^6 + 288*x^7 + ...
MATHEMATICA
a[1] = 1; a[2] = 2; a[3] = 6; a[n_] := a[n] = 3a[n - 1] - a[n - 2]; Table[a[n], {n, 28}] (* Robert G. Wilson v *)
PROG
(Haskell)
a111282 n = a111282_list !! (n-1)
a111282_list = 1 : a025169_list
-- Reinhard Zumkeller, Apr 08 2012
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Len Smiley, Nov 01 2005
STATUS
approved