|
|
A179255
|
|
Number of partitions of n into distinct parts such that the successive differences of consecutive parts are nondecreasing.
|
|
11
|
|
|
1, 1, 1, 2, 2, 3, 4, 5, 5, 8, 9, 10, 13, 15, 16, 22, 24, 26, 33, 36, 39, 50, 54, 58, 70, 77, 83, 100, 109, 116, 137, 150, 159, 186, 202, 216, 249, 270, 288, 328, 355, 379, 428, 462, 491, 554, 597, 633, 707, 760, 807, 899, 964, 1020, 1127, 1211, 1282, 1412, 1512, 1596, 1750, 1873, 1976, 2160, 2305, 2434, 2652, 2826, 2978
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Partitions into distinct parts (p(1), p(2), ..., p(m)) such that p(k-1) - p(k-2) <= p(k) - p(k-1) for all k >= 3.
|
|
LINKS
|
|
|
EXAMPLE
|
There are a(17) = 26 such partitions of 17:
01: [ 1 2 3 4 7 ]
02: [ 1 2 3 11 ]
03: [ 1 2 4 10 ] *
04: [ 1 2 5 9 ] *
05: [ 1 2 14 ] *
06: [ 1 3 5 8 ]
07: [ 1 3 13 ] *
08: [ 1 4 12 ] *
09: [ 1 5 11 ] *
10: [ 1 16 ] *
11: [ 2 3 4 8 ]
12: [ 2 3 5 7 ]
13: [ 2 3 12 ] *
14: [ 2 4 11 ] *
15: [ 2 5 10 ] *
16: [ 2 15 ] *
17: [ 3 4 10 ] *
18: [ 3 5 9 ] *
19: [ 3 14 ] *
20: [ 4 5 8 ] *
21: [ 4 13 ] *
22: [ 5 12 ] *
23: [ 6 11 ] *
24: [ 7 10 ] *
25: [ 8 9 ] *
26: [ 17 ] *
The 21 partitions marked with * have strictly increasing differences, see the example for A179254.
|
|
PROG
|
(Sage)
has_nondecreasing_diffs = lambda x: min(differences(x, 2)) >= 0
allowed = lambda x: len(x) < 3 or has_nondecreasing_diffs(x)
return len([x for x in Partitions(n, max_slope=-1) if allowed(x[::-1])])
(Ruby)
def partition(n, min, max)
return [[]] if n == 0
[max, n].min.downto(min).flat_map{|i| partition(n - i, min, i - 1).map{|rest| [i, *rest]}}
end
def f(n)
return 1 if n == 0
cnt = 0
partition(n, 1, n).each{|ary|
ary0 = (1..ary.size - 1).map{|i| ary[i - 1] - ary[i]}
cnt += 1 if ary0.sort == ary0.reverse
}
cnt
end
(0..n).map{|i| f(i)}
end
|
|
CROSSREFS
|
Cf. A240026 (partitions with nondecreasing differences), A240027 (partitions with strictly increasing differences), A320382.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|