A006367 Number of binary vectors of length n+1 beginning with 0 and containing just 1 singleton.

1, 0, 2, 2, 5, 8, 15, 26, 46, 80, 139, 240, 413, 708, 1210, 2062, 3505, 5944, 10059, 16990, 28646, 48220, 81047, 136032, 228025, 381768, 638450, 1066586, 1780061, 2968040, 4944519, 8230370, 13689118, 22751528, 37786915, 62716752, 104028245

Offset

0,3

Comments

Number of compositions of n+1 containing exactly one 1. - Emeric Deutsch, Mar 08 2002

Number of permutations with one fixed point avoiding 231 and 321.

A singleton is a run of length 1. - Michael Somos, Nov 29 2014

Second column of A105422. - Michael Somos, Nov 29 2014

Number of weak compositions of n with one 0 and no 1's. Example: Combine one 0 with the compositions of 5 without 1 to get a(5) = 8 weak compositions: 0,5; 5,0; 0,2,3; 0,3,2; 2,0,3; 3,0,2; 2,3,0; 3,2,0. - Gregory L. Simay, Mar 21 2018

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.

Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 11.

Mengmeng Liu and Andrew Yezhou Wang, The Number of Designated Parts in Compositions with Restricted Parts, J. Int. Seq., Vol. 23 (2020), Article 20.1.8.

J. J. Madden, A generating function for the distribution of runs in binary words, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=k=1.

T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002.

Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Formula

a(n) = a(n-1) + a(n-2) + Fibonacci(n-3).

G.f.: (1-x)^2/(1-x-x^2)^2. - Emeric Deutsch, Mar 08 2002

a(n) = A010049(n+1) - A010049(n). - R. J. Mathar, May 30 2014

Convolution square of A212804. - Michael Somos, Nov 29 2014

a(n) = -(-1)^n * A004798(-1-n) for all n in Z. - Michael Somos, Nov 29 2014

0 = a(n)*(-2*a(n) - 7*a(n+1) + 2*a(n+2) + a(n+3)) + a(n+1)*(-4*a(n+1) + 10*a(n+2) - 2*a(n+3)) + a(n+2)*(+4*a(n+2) - 7*a(n+3)) + a(n+3)*(+2*a(n+3)) for all n in Z. - Michael Somos, Nov 29 2014

a(n) = (n*Lucas(n-2) + Fibonacci(n))/5 + Fibonacci(n-1). - Ehren Metcalfe, Jul 29 2017

Example

a(4) = 5 because among the 2^4 compositions of 5 only 4+1,1+4,2+2+1,2+1+2,1+2+2 contain exactly one 1.
a(4) = 5 because the binary vectors of length 4+1 beginning with 0 and with exactly one singleton are: 00001, 00100, 00110, 01100, 01111. - Michael Somos, Nov 29 2014
G.f. = 1 + 2*x^2 + 2*x^3 + 5*x^4 + 8*x^5 + 15*x^6 + 26*x^7 + 46*x^8 + ...

Mathematica

nn=36; CoefficientList[Series[1/(1 -x/(1-x) +x)^2, {x, 0, nn}], x] (* Geoffrey Critzer, Feb 18 2014 *)
a[n_]:= If[ n<0, SeriesCoefficient[((1-x)/(1+x-x^2))^2, {x, 0, -2-n}], SeriesCoefficient[((1-x)/(1-x-x^2))^2, {x, 0, n}]]; (* Michael Somos, Nov 29 2014 *)

Prog

(Magma) I:=[1, 0]; [n le 2 select I[n] else Self(n-1)+Self(n-2)+Fibonacci(n-3): n in [1..40]]; // Vincenzo Librandi, Feb 20 2014
(PARI) Vec( (1-x)^2/(1-x-x^2)^2 + O(x^66) ) \\ Joerg Arndt, Feb 20 2014
(PARI) {a(n) = if( n<0, n = -2-n; polcoeff( (1 - x)^2 / (1 + x - x^2)^2 + x * O(x^n), n), polcoeff( (1 - x)^2 / (1 - x - x^2)^2 + x * O(x^n), n))}; /* Michael Somos, Nov 29 2014 */
(Python)
from sympy import fibonacci
from sympy.core.cache import cacheit
@cacheit
def a(n): return 1 if n==0 else 0 if n==1 else a(n - 1) + a(n - 2) + fibonacci(n - 3)
print([a(n) for n in range(51)]) # Indranil Ghosh, Jul 20 2017
(SageMath)
def A006367(n): return (1/5)*(n*lucas_number2(n-2, 1, -1) + fibonacci(n+1) + 4*fibonacci(n-1))
[A006367(n) for n in (0..40)] # G. C. Greubel, Apr 06 2022

Crossrefs

Cf. A000032, A000045, A004798, A006355, A010049, A105422, A139821, A212804.

Sequence in context: A335443 A042982 A340249 * A246807 A077902 A005834

Adjacent sequences: A006364 A006365 A006366 * A006368 A006369 A006370

Keyword

nonn,easy

Author

David M. Bloom

Status

approved