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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006500 Restricted combinations.
(Formerly M1092)
7
1, 2, 4, 8, 12, 18, 27, 45, 75, 125, 200, 320, 512, 832, 1352, 2197, 3549, 5733, 9261, 14994, 24276, 39304, 63580, 102850, 166375, 269225, 435655, 704969, 1140624, 1845504, 2985984, 4831488, 7817616, 12649337, 20466953, 33116057, 53582633 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

REFERENCES

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.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

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

G. E. Bergum and V. E. Hoggatt, Jr., A combinatorial problem involving recursive sequences and tridiagonal matrices, Fib. Quart., 16 (1978), 113-118.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301

Index entries for linear recurrences with constant coefficients, signature (1, 1, -1, 1, 1, 1, -1, -1).

FORMULA

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

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

EXAMPLE

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.

MAPLE

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.

MATHEMATICA

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

Table[Product[Fibonacci[Floor[(n + i)/3] + 2], {i, 0, 2}], {n, 0, 30}] (* David Nacin, Mar 07 2012 *)

LinearRecurrence[{1, 1, -1, 1, 1, 1, -1, -1}, {1, 2, 4, 8, 12, 18, 27, 45}, 40] (* David Nacin, Mar 07 2012 *)

PROG

(Python)

def a(n, adict={0:1, 1:2, 2:4, 3:8, 4:12, 5:18, 6:27, 7:45}):

.if n in adict:

..return adict[n]

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

.return adict[n] # David Nacin, Mar 07 2012

CROSSREFS

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.

Sequence in context: A224810 A074633 A294049 * A134181 A171645 A125606

Adjacent sequences:  A006497 A006498 A006499 * A006501 A006502 A006503

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane.

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 October 23 16:50 EDT 2018. Contains 316529 sequences. (Running on oeis4.)