A136343 Number of partitions of n such that each summand is greater than or equal to the sum of the next two summands.

1, 1, 2, 2, 4, 4, 6, 7, 10, 11, 14, 16, 21, 23, 29, 32, 40, 43, 52, 57, 69, 75, 88, 96, 113, 122, 141, 153, 177, 190, 216, 233, 265, 285, 320, 345, 387, 415, 461, 495, 551, 589, 650, 695, 767, 818, 896, 957, 1048, 1116, 1214, 1293, 1407, 1495, 1620, 1721, 1864

Offset

0,3

Comments

This sequence was suggested by Moshe Shmuel Newman. The idea came to him while reading a paper of Lev Shneerson.

Number of partitions of 2n into exactly n positive Fibonacci numbers. a(8) = 10: 82111111, 55111111, 53311111, 53221111, 52222111, 33331111, 33322111, 33222211, 32222221, 22222222. - Alois P. Heinz, Sep 18 2018

Links

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

Formula

From Alois P. Heinz, Sep 18 2018: (Start)

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

a(n) = A319394(2n,n). (End)

Example

a(5) = 4 because 4 of the 7 partitions of 5 have the required property: {5} {4,1} {3,2} {3,1,1}. The other 3 partitions of 5: {2,2,1} {2,1,1,1} and {1,1,1,1,1} each have an element which is < the sum of next two.

Maple

b:= proc(n, i, j) option remember; `if`(n=0, 1,
      `if`(i<1, 0, b(n-i, min(n-i, i,
      `if`(j=0, i, j-i)), i) +b(n, i-1, j)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..60);  # Alois P. Heinz, Jul 29 2017

Mathematica

b[n_, i_, j_]:=b[n, i, j]=If[n==0, 1, If[i<1, 0, b[n - i, Min[n - i, i, If[j==0, i, j - i]], i] + b[n, i - 1, j]]]; Table[b[n, n, 0], {n, 0, 60}] (* Indranil Ghosh, Aug 01 2017, after Maple code *)

Crossrefs

Cf. A000045, A319394.

Sequence in context: A319403 A029008 A240844 * A161254 A241313 A241317

Adjacent sequences: A136340 A136341 A136342 * A136344 A136345 A136346

Keyword

nonn

Author

David S. Newman, May 11 2008

Extensions

Conjectured g.f. removed and a(0), a(35)-a(56) added by Alois P. Heinz, Jul 29 2017

Status

approved