|
%I M1092 #54 Apr 13 2022 13:25:18
%S 1,2,4,8,12,18,27,45,75,125,200,320,512,832,1352,2197,3549,5733,9261,
%T 14994,24276,39304,63580,102850,166375,269225,435655,704969,1140624,
%U 1845504,2985984,4831488,7817616,12649337,20466953,33116057,53582633
%N Restricted combinations.
%C a(n)=( A000045(k+2) )^3 if n=3k, a(n)=( A000045(k+2) )^3 * A000045(k+3) if n=3k+1, a(n)= A000045(k+2) * ( A000045(k+3) )^2 if n=3k+2. Number of all subsets of the set {1,2,...,n} which do not contain two elements whose difference is 3. a(n) is number of compositions of n+3 into elements of the set {1,2,4,5,6}, but with condition that 2 succeed only 2 or 4. Number of all permutations of {1,2,...,n+3} satisfying p(i)-i in {-3,0,3}. - _Vladimir Baltic_, Feb 17 2003
%D M. El-Mikkawy, T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461 doi:10.1016/j.amc.2009.12.069, Table 1 k=3.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A006500/b006500.txt">Table of n, a(n) for n = 0..1000</a>
%H Katharine A. Ahrens, <a href="https://repository.lib.ncsu.edu/bitstream/handle/1840.20/37364/etd.pdf">Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis</a>, Ph. D. thesis, North Carolina State University (2020).
%H G. E. Bergum and V. E. Hoggatt, Jr., <a href="http://www.fq.math.ca/Scanned/16-2/bergum.pdf">A combinatorial problem involving recursive sequences and tridiagonal matrices</a>, Fib. Quart., 16 (1978), 113-118.
%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 M. Tetiva, <a href="http://www.jstor.org/stable/10.4169/math.mag.84.4.296">Subsets that make no difference d</a>, Mathematics Magazine 84 (2011), no. 4, 300-301
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (1, 1, -1, 1, 1, 1, -1, -1).
%F Recurrence: a(n) = a(n-1)+a(n-2)-a(n-3)+a(n-4)+a(n-5)+a(n-6)-a(n-7)-a(n-8) G.f.: -(x^7+2*x^6+x^5-x^4-3*x^3-x^2-x-1)/(x^8+x^7-x^6-x^5-x^4+x^3-x^2-x+1). - _Vladimir Baltic_, Feb 17 2003
%F a(n) = F(floor(n/3) + 3)^(n mod 3)*F(floor(n/3) + 2)^(3 - (n mod 3)) where F(n) is the n-th Fibonacci number. - _David Nacin_, Feb 29 2012
%e For example, a_4=12 and 12 subsets are: emptyset, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {2,3}, {2,4}, {3,4}, {1,2,3}, {2,3,4}. Corresponding compositions of 7=4+3 are: 1+1+1+1+1+1+1+1, 4+1+1+1, 1+4+1+1, 1+1+4+1, 1+1+1+4, 5+1+1, 4+2+1, 1+5+1, 1+4+2, 1+1+5, 6+1 and 1+6.
%p A006500:=-(2*z**6+z**7-z**4+z**5-3*z**3-z**2-z-1)/(z**6-z**3-1)/(z**2+z-1); # Conjectured by _Simon Plouffe_ in his 1992 dissertation.
%t Table[Fibonacci[Floor[n/3] + 3]^Mod[n, 3] * Fibonacci[Floor[n/3] + 2]^(3 - Mod[n, 3]), {n, 0, 40}] (* _David Nacin_, Feb 29 2012 *)
%t Table[Product[Fibonacci[Floor[(n + i)/3] + 2], {i, 0, 2}], {n, 0, 30}] (* _David Nacin_, Mar 07 2012 *)
%t LinearRecurrence[{1, 1, -1, 1, 1, 1, -1, -1}, {1, 2, 4, 8, 12, 18, 27, 45}, 40] (* _David Nacin_, Mar 07 2012 *)
%o (Python)
%o def a(n, adict={0:1, 1:2, 2:4, 3:8, 4:12, 5:18, 6:27, 7:45}):
%o if n in adict:
%o return adict[n]
%o adict[n]=a(n-1)+a(n-2)-a(n-3)+a(n-4)+a(n-5)+a(n-6)-a(n-7)-a(n-8)
%o return adict[n] # _David Nacin_, Mar 07 2012
%Y Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_.
|
