A319394 Number T(n,k) of partitions of n into exactly k positive Fibonacci numbers; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 2, 1, 1, 0, 1, 1, 2, 1, 1, 0, 0, 2, 2, 2, 1, 1, 0, 0, 1, 3, 2, 2, 1, 1, 0, 1, 1, 2, 4, 2, 2, 1, 1, 0, 0, 1, 3, 3, 4, 2, 2, 1, 1, 0, 0, 2, 2, 4, 4, 4, 2, 2, 1, 1, 0, 0, 1, 3, 4, 5, 4, 4, 2, 2, 1, 1, 0, 0, 0, 3, 5, 5, 6, 4, 4, 2, 2, 1, 1

Offset

0,13

Comments

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k <= n. T(n,k) = 0 for k > n.

Links

Alois P. Heinz, Rows n = 0..200, flattened

Formula

T(n,k) = [x^n y^k] 1/Product_{j>=2} (1-y*x^A000045(j)).

Sum_{k=1..n} k * T(n,k) = A281689(n).

T(A000045(n),n) = A319503(n).

Example

T(14,3) = 2: 851, 833.
T(14,4) = 5: 8321, 8222, 5531, 5522, 5333.
T(14,5) = 6: 83111, 82211, 55211, 53321, 53222, 33332.
T(14,6) = 8: 821111, 551111, 533111, 532211, 522221, 333311, 333221, 332222.
T(14,7) = 7: 8111111, 5321111, 5222111, 3332111, 3322211, 3222221, 2222222.
T(14,8) = 6: 53111111, 52211111, 33311111, 33221111, 32222111, 22222211.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1, 1;
  0, 1, 1, 1;
  0, 0, 2, 1, 1;
  0, 1, 1, 2, 1, 1;
  0, 0, 2, 2, 2, 1, 1;
  0, 0, 1, 3, 2, 2, 1, 1;
  0, 1, 1, 2, 4, 2, 2, 1, 1;
  0, 0, 1, 3, 3, 4, 2, 2, 1, 1;
  0, 0, 2, 2, 4, 4, 4, 2, 2, 1, 1;
  0, 0, 1, 3, 4, 5, 4, 4, 2, 2, 1, 1;
  0, 0, 0, 3, 5, 5, 6, 4, 4, 2, 2, 1, 1;
  0, 1, 1, 2, 4, 7, 6, 6, 4, 4, 2, 2, 1, 1;
  0, 0, 1, 2, 5, 6, 8, 7, 6, 4, 4, 2, 2, 1, 1;
  ...

Maple

h:= proc(n) option remember; `if`(n<1, 0, `if`((t->
      issqr(t+4) or issqr(t-4))(5*n^2), n, h(n-1)))
    end:
b:= proc(n, i) option remember; `if`(n=0 or i=1, x^n,
      b(n, h(i-1))+expand(x*b(n-i, h(min(n-i, i)))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, h(n))):
seq(T(n), n=0..20);

Mathematica

T[n_, k_] := SeriesCoefficient[1/Product[(1 - y x^Fibonacci[j]) + O[x]^(n+1) // Normal, {j, 2, n+1}], {x, 0, n}, {y, 0, k}];
Table[T[n, k], {n, 0, 40}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 28 2020 *)
h[n_] := h[n] = If[n < 1, 0, If[Function[t, IntegerQ@Sqrt[t + 4] || IntegerQ@Sqrt[t - 4]][5 n^2], n, h[n - 1]]];
b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1, If[i < 1 || t < 1, 0, b[n, h[i - 1], t] + b[n - i, h[Min[n - i, i]], t - 1]]];
T[n_, k_] :=  b[n, h[n], k] - b[n, h[n], k - 1];
Table[T[n, k], {n, 0, 20}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 07 2020, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A000007, A010056 (for n>0), A319395, A319396, A319397, A319398, A319399, A319400, A319401, A319402, A319403.

Row sums give A003107.

T(2n,n) gives A136343.

Cf. A000045, A281689, A319503.

Sequence in context: A340379 A075685 A037906 * A278347 A120936 A335294

Adjacent sequences: A319391 A319392 A319393 * A319395 A319396 A319397

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 18 2018

Status

approved