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

Author

David M. Bloom

Keywords

• nonn
• easy

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

Examples

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

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

Crossrefs

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

Programs

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

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

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

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