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

Author

Alois P. Heinz, Sep 18 2018

Keywords

• nonn
• tabl

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.

Examples

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

Links

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

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.

Programs

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

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