|
%I M1103 N0421 #163 Sep 08 2022 08:44:27
%S 1,2,4,8,15,27,47,80,134,222,365,597,973,1582,2568,4164,6747,10927,
%T 17691,28636,46346,75002,121369,196393,317785,514202,832012,1346240,
%U 2178279,3524547,5702855,9227432,14930318,24157782,39088133,63245949
%N A nonlinear binomial sum.
%C a(n)-1 counts ternary numbers with no 0 digit (A007931) and at least one 2 digit, where the total of ternary digits is <= n. E.g., a(4)-1 = 7: 2 12 21 22 112 121 211. - _Frank Ellermann_, Dec 02 2001
%C A107909(a(n-1)) = A000079(n-1) = 2^(n-1). - _Reinhard Zumkeller_, May 28 2005
%C a(n) is the permanent of the n X n 0-1 matrix whose (i,j) entry is 1 iff i=1 or j=n or |i-j|<=1. For example, a(5)=15 is per([[1, 1, 1, 1, 1], [1, 1, 1, 0, 1], [0, 1, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 0, 1, 1]]). - _David Callan_, Jun 07 2006
%C Conjecture. Let S(1)={1} and, for n>1, let S(n) be the smallest set containing x+1 and 2x+1 for each element x in S(n-1). Then a(n) is the sum of the elements in S(n). (See A122554 for a sequence defined in this way.) - _John W. Layman_, Nov 21 2007
%C a(n+1) indexes the corner blocks on the Fibonacci spiral built from blocks of unit area (using F(1) and F(2) as the sides of the first block). - _Paul Barry_, Mar 06 2008
%C The number of length n binary words with fewer than 2 0-digits between any pair of consecutive 1-digits. - _Jeffrey Liese_, Dec 23 2010
%C If b(n) = a(n+1) then b(0) = 1 and 2*b(n) >= b(n+1) for all n > 1 which is sufficient for b(n) to be a complete sequence. - _Frank M Jackson_, Mar 17 2013
%C From _Gus Wiseman_, Feb 10 2019: (Start)
%C Also the number of non-singleton subsets of {1, ..., n + 1} with no successive elements. For example, the a(5) = 15 subsets are:
%C {},
%C {1,3}, {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,6},
%C {1,3,5}, {1,3,6}, {1,4,6}, {2,4,6}.
%C Also the number of binary sequences with all zeros or at least 2 ones and no adjacent ones. For example, the a(1) = 1 through a(4) = 8 sequences are:
%C (00) (000) (0000) (00000)
%C (101) (0101) (00101)
%C (1001) (01001)
%C (1010) (01010)
%C (10001)
%C (10010)
%C (10100)
%C (10101)
%C (End)
%D Grimaldi, Ralph P. A generalization of the Fibonacci sequence. Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986). Congr. Numer. 54 (1986), 123--128. MR0885268 (89f:11030). - _N. J. A. Sloane_, Apr 08 2012
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000126/b000126.txt">Table of n, a(n) for n = 1..201</a>
%H Alvaro Carbonero, Beth Anne Castellano, Gary Gordon, Charles Kulick, Karie Schmitz, and Brittany Shelton, <a href="https://arxiv.org/abs/2106.14140">Permutations of point sets in R_d</a>, arXiv:2106.14140 [math.CO], 2021.
%H Forbes, Tamsin; Forbes, Tony <a href="https://doi.org/10.1017/mag.2016.108">Hanoi revisited</a>, Math. Gaz. 100, No. 549, 435-441 (2016).
%H T. Langley, J. Liese, J. Remmel, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Langley/langley2.html">Generating Functions for Wilf Equivalence Under Generalized Factor Order </a>, J. Int. Seq. 14 (2011) # 11.4.2.
%H D. A. Lind, <a href="http://www.fq.math.ca/Scanned/3-4/lind.pdf">On a class of nonlinear binomial sums</a>, Fib. Quart., 3 (1965), 292-298.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-1,1).
%F G.f.: (1 - x + x^3 ) / (( 1 - x - x^2 )*( 1 - x )^2). - _Simon Plouffe_ in his 1992 dissertation
%F From _Henry Bottomley_, Oct 22 2001: (Start)
%F a(n) = Fibonacci(n+3) - (n+1) = a(n-1) + a(n-2) + n - 2
%F a(n) = A001924(n-1) + 1 = A065220(n+3) + 2. (End)
%F a(n) = 2*a(n-1) - a(n-3) + 1. - _Franklin T. Adams-Watters_, Jan 13 2006
%F a(n+1) = 1 + Sum_{k=0..n} (Fibonacci(k+2) - 1) = Sum_{k=0..n} Fibonacci(k+2) - n. - _Paul Barry_, Mar 06 2008
%F a(n) = 3*a(n-1)-2*a(n-2)-a(n-3)+a(n-4). - _Harvey P. Dale_, May 05 2011
%F Closed-form without extra leading 1: ((15+7*sqrt(5))*((1+sqrt(5))/2)^n+(15-7*sqrt(5))*((1-sqrt(5))/2)^n-10*n-20)/10; closed-form with extra leading 1: ((20+8*sqrt(5))*((1+sqrt(5))/2)^n+(20-8*sqrt(5))*((1-sqrt(5))/2)^n-20*n-20)/20. - _Tim Monahan_, Jul 16 2011
%F G.f. for closed-form with extra leading 1: (1-2*x+x^2+x^3)/((1-x-x^2)*(x-1)^2). - _Tim Monahan_, Jul 17 2011
%p a:= n-> (Matrix([[1,1,1,2]]). Matrix(4, (i,j)-> if (i=j-1) then 1 elif j=1 then [3,-2,-1,1][i] else 0 fi)^n)[1,2]; seq(a(n), n=1..36); # _Alois P. Heinz_, Aug 26 2008
%p # alternative
%p A000126 := proc(n)
%p combinat[fibonacci](n+3)-n-1 ;
%p end proc:
%p seq(A000126(n),n=1..40) ; # _R. J. Mathar_, Aug 05 2022
%t LinearRecurrence[{3,-2,-1,1},{1,2,4,8},40] (* or *) CoefficientList[ Series[-(1-x+x^3)/((x^2+x-1)(x-1)^2),{x,0,40}],x] (* _Harvey P. Dale_, Apr 24 2011 *)
%t Table[Length[Select[Subsets[Range[n]],Min@@Abs[Subtract@@@Partition[#,2,1,1]]>1&]],{n,15}] (* _Gus Wiseman_, Feb 10 2019 *)
%o (PARI) Vec((1-x+x^3)/(1-x-x^2)/(1-x)^2+O(x^40)) \\ _Charles R Greathouse IV_, Oct 06 2011
%o (Python)
%o def seq(n):
%o if n < 0:
%o return 1
%o a, b = 1, 1
%o for i in range(n + 1):
%o a, b = b, a + b + i
%o return a
%o [seq(i) for i in range(n)] # _Reza K Ghazi_, Mar 03 2019
%o (PARI) vector(40, n, fibonacci(n+3) -(n+1)) \\ _G. C. Greubel_, Jul 09 2019
%o (Magma) [Fibonacci(n+3)-(n+1): n in [1..40]]; // _G. C. Greubel_, Jul 09 2019
%o (Sage) [fibonacci(n+3)-(n+1) for n in (1..40)] # _G. C. Greubel_, Jul 09 2019
%o (GAP) List([1..40], n-> Fibonacci(n+3)-(n+1)); # _G. C. Greubel_, Jul 09 2019
%Y Heap-transform of A000071. - _John W. Layman_
%Y Cf. A066067, A001924, A065220.
%Y Cf. A007931: binary strings with leading 0's, or ternary strings without 0's.
%Y Differences are A000071.
%Y Cf. A122554.
%Y Cf. A005251, A066982, A169985.
%Y Cf. A000045.
%K nonn,easy
%O 1,2
%A _N. J. A. Sloane_
|
