A117145 Triangle read by rows: T(n,k) is the number of partitions of n into parts of the form 2^j-1, j=1,2,... and having k parts (n>=0, 0<=k<=n). Partitions into parts of the form 2^j-1, j=1,2,... are called s-partitions.

1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 2, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 2, 0, 2, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 1

Offset

0,49

Comments

Row sums yield A000929.

Links

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

P. C. P. Bhatt, An interesting way to partition a number, Inform. Process. Lett., 71, 1999, 141-148.

W. M. Y. Goh, P. Hitczenko and A. Shokoufandeh, s-partitions, Inform. Process. Lett., 82, 2002, 327-329.

Formula

G.f.: G(t,x) = 1/Product_{k>=1} (1-t*x^(2^k-1)).

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

Example

T(9,3) = 2 because we have [7,1,1] and [3,3,3].
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 0, 1;
  0, 1, 0, 1;
  0, 0, 1, 0, 1;
  0, 0, 0, 1, 0, 1;
  0, 0, 1, 0, 1, 0, 1;
  0, 1, 0, 1, 0, 1, 0, 1;
  0, 0, 1, 0, 1, 0, 1, 0, 1;
  0, 0, 0, 2, 0, 1, 0, 1, 0, 1;
  0, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1;
  0, 0, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1;
  0, 0, 0, 0, 2, 0, 2, 0, 1, 0, 1, 0, 1;
  0, 0, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 1;
  0, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 1;
  0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 1, 0, 1, 0, 1;
  ...

Maple

g:= 1/product(1-t*x^(2^k-1), k=1..10):
gser:=simplify(series(g, x, 20)):
for n from 0 to 19 do P[n]:=sort(coeff(gser, x, n)) od:
for n from 0 to 19 do seq(coeff(P[n], t, j), j=0..n) od; # yields sequence in triangular form
# Alternative:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1)+(p-> `if`(p>n, 0, expand(x*b(n-p, i))))(2^i-1)))
    end:
T:= (n, k)-> coeff(b(n, 1+ilog2(n)), x, k):
seq(seq(T(n, k), k=0..n), n=0..20);  # Alois P. Heinz, Oct 01 2025

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, b[n, i-1] + With[{p = 2^i-1}, If[p > n, 0, Expand[x*b[n-p, i]]]]]];
T[n_, k_] := Coefficient[b[n, Length[IntegerDigits[n, 2]]], x, k];
Table[T[n, k], {n, 0, 20}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 03 2026, after_Alois P. Heinz_ *)

Crossrefs

Cf. A000929, A117146.

Sequence in context: A341519 A307837 A123671 * A191261 A387487 A355745

Adjacent sequences: A117142 A117143 A117144 * A117146 A117147 A117148

Keyword

nonn,tabl

Author

Emeric Deutsch, Mar 06 2006

Extensions

Column k=0 inserted by Alois P. Heinz, Oct 01 2025

Status

approved