login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006367 Number of binary vectors of length n+1 beginning with 0 and containing just 1 singleton. 14
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 (list; graph; refs; listen; history; text; internal format)
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

LINKS

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

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

class Memoize:

    def __init__(self, func):

        self.func = func

        self.cache = {}

    def __call__(self, arg):

        if arg not in self.cache:

            self.cache[arg] = self.func(arg)

        return self.cache[arg]

@Memoize

def a(n): return 1 if n==0 else 0 if n==1 else a(n - 1) + a(n - 2) + fibonacci(n - 3)

print map(a, xrange(51)) # Indranil Ghosh, Jul 20 2017

CROSSREFS

Cf. A004798, A006355, A105422, A139821, A212804.

Sequence in context: A056224 A052527 A042982 * A246807 A077902 A005834

Adjacent sequences:  A006364 A006365 A006366 * A006368 A006369 A006370

KEYWORD

nonn,easy

AUTHOR

David M. Bloom

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 24 22:31 EDT 2017. Contains 292441 sequences.