A238998 Number of partitions of n that such that no part is a Fibonacci number.

1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 2, 2, 3, 2, 4, 4, 6, 5, 9, 8, 11, 11, 16, 16, 22, 22, 29, 31, 40, 42, 54, 57, 71, 77, 95, 103, 127, 137, 165, 182, 218, 238, 285, 313, 369, 408, 479, 530, 619, 684, 794, 883, 1019, 1130, 1304, 1446, 1658, 1843, 2107, 2340, 2670

Offset

0,11

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Formula

G.f.: A(x) = sum(1/product(1 - x^c(i))), i >=1, where c(i) are the non-Fibonacci numbers.

Example

a(15) counts these partitions:  [15], [11,4], [9,6], [7,4,4]; a(16) counts these:  [16], [12,4], [10,6], [9,7], [6,6,4], [4,4,4,4].

Maple

a:= proc(n) option remember; `if`(n=0, 1, add(add(
      `if`((f-> issqr(f+4) or issqr(f-4))(5*d^2), 0, d),
        d=numtheory[divisors](j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Mar 31 2017

Mathematica

p[n_] := IntegerPartitions[n, All, Complement[Range@n, Fibonacci@Range@15]]; Table[p[n], {n, 0, 20}] (* shows partitions *)
a[n_] := Length@p@n; a /@ Range[0, 80] (* counts partitions *)
(* Second program: *)
a[n_] := a[n] = If[n == 0, 1, Sum[Sum[
    If[Function[f, IntegerQ@Sqrt[f+4] || IntegerQ@Sqrt[f-4]][5*d^2], 0, d],
    {d, Divisors[j]}]*a[n - j], {j, 1, n}]/n];
a /@ Range[0, 100] (* Jean-François Alcover, Jun 05 2021, after Alois P. Heinz *)

Prog

(PARI) N=66; q='q+O('q^N); Vec( prod(n=1, 11, 1-q^fibonacci(n+1))/eta(q) ) \\ Joerg Arndt, Mar 11 2014

Crossrefs

Cf. A003107, A000045.

Sequence in context: A117660 A358015 A184198 * A355359 A144369 A033822

Adjacent sequences: A238995 A238996 A238997 * A238999 A239000 A239001

Keyword

nonn,easy

Author

Clark Kimberling, Mar 08 2014

Status

approved