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

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.

EXTENSIONS

More terms from Vladimir Baltic, Feb 17 2003

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 February 22 09:32 EST 2018. Contains 299448 sequences. (Running on oeis4.)