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

Author

David S. Newman, May 11 2008

Keywords

• nonn

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A000045, A319394.

Programs

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

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)

Extensions

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