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