login
A182372
Number of distinct sets of nonnegative integers with perimeter n, as defined in the comments.
3
2, 2, 3, 4, 6, 8, 11, 14, 19, 24, 31, 39, 50, 61, 77, 94, 117, 141, 173, 208, 253, 302, 363, 431, 516, 609, 723, 850, 1003, 1174, 1379, 1607, 1878, 2181, 2537, 2936, 3404, 3925, 4532, 5212, 5998, 6877, 7890, 9021, 10320, 11771, 13427, 15277, 17385, 19734, 22401, 25375, 28739, 32485
OFFSET
0,1
COMMENTS
The volume and perimeter of a set S of nonnegative integers are introduced in the reference. The volume is defined simply as the sum of the elements of S, and the perimeter is defined as the sum of the elements of S whose predecessor and successor are not both in S.
Conjecture: number of partitions of n into two sorts of parts such that no two successive parts are the same sort (as the order of sorts in a run of identical parts is immaterial, there can be at most two parts of same size), see example. [Joerg Arndt, Jun 01 2013]
The conjecture of Arndt [namely that a(n) = A227134(n) + A227135(n)] has been verified for n < 1200. [Patrick Devlin, Jul 02 2013]
a(n) is also the number of ways to write n as the sum of nonnegative integers, t_1 < t_2 < ... < t_k, such that (i) each such integer is labeled "E" or "F", (ii) t_1 is labeled "E", (iii) if t_j - t_{j-1} = 1, then t_j is labeled "F", and (iv) the label "F" does not appear twice in a row. (This includes the empty sum for the case n=0.) See examples [Patrick Devlin, Jul 03 2013].
LINKS
Patrick Devlin, Integer Subsets with High Volume and Low Perimeter, arXiv:1202.1331 [math.CO], 2012.
J. Miller, F. Morgan, E. Newkirk, L. Pedersen and D. Seferis, Isoperimetric Sets of Integers, Math. Mag. 84 (2011) 37-42.
FORMULA
G.f.: 2/(1-x) + Sum_{n>=2} x^A002620(n+2)*(1 + x^[n/2]) / Product_{k=1..n} (1-x^k), where A002620(n) = floor(n/2)*ceiling(n/2) forms the quarter-squares. - Paul D. Hanna, Jul 06 2013
EXAMPLE
G.f.: 2 + 2*x + 3*x^2 + 4*x^3 + 6*x^4 + 8*x^5 + 11*x^6 + 14*x^7 + 19*x^8 + ...
G.f.: 2/(1-x) + x^2*(1+x)/((1-x)*(1-x^2)) + x^4*(1+x)/((1-x)*(1-x^2)*(1-x^3)) + x^6*(1+x^2)/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)) + x^9*(1+x^2)/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)*(1-x^5)) + x^12*(1+x^3)/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)*(1-x^5)*(1-x^6))) + ... [Paul D. Hanna, Jul 06 2013]
From Joerg Arndt, Jun 01 2013: (Start)
##: set perimeter sum(perimeter)
00: ....... ....... 0 (empty set)
01: ......1 ......1 0
02: .....1. .....1. 1
03: .....11 .....11 1
04: ....1.. ....1.. 2
05: ....1.1 ....1.1 2
06: ....11. ....11. 3
07: ....111 ....1.1 2
08: ...1... ...1... 3
09: ...1..1 ...1..1 3
10: ...1.1. ...1.1. 4
11: ...1.11 ...1.11 4
12: ...11.. ...11.. 5
13: ...11.1 ...11.1 5
14: ...111. ...1.1. 4
15: ...1111 ...1..1 3
16: ..1.... ..1.... 4
17: ..1...1 ..1...1 4
18: ..1..1. ..1..1. 5
19: ..1..11 ..1..11 5
20: ..1.1.. ..1.1.. 6
21: ..1.1.1 ..1.1.1 6
22: ..1.11. ..1.11. 7
23: ..1.111 ..1.1.1 6
24: ..11... ..11... 7
25: ..11..1 ..11..1 7
26: ..11.1. ..11.1. 8
27: ..11.11 ..11.11 8
28: ..111.. ..1.1.. 6
29: ..111.1 ..1.1.1 6
30: ..1111. ..1..1. 5
31: ..11111 ..1...1 4
The last set contribution to a(n) n has index 2^(n+1)-1, so the statistics is complete up to 4.
We find a(1)=2, a(1)=2, a(2)=2, and a(4)=6.
(End)
The six sets {4}, {0,4}, {1,3}, {0,1,3}, {1,2,3}, and {0,1,2,3,4}, and no others, have perimeter 4, so a(4)=6.
From Joerg Arndt, Jun 01 2013: (Start)
There are a(9) = 24 partitions of 9 into two sorts of parts such that no two successive parts are of same sort (format "P:S" for "part:sort"):
01: [ 1:0 1:1 2:0 2:1 3:0 ]
02: [ 1:0 1:1 2:0 5:1 ]
03: [ 1:0 1:1 3:0 4:1 ]
04: [ 1:0 1:1 7:0 ]
05: [ 1:0 2:1 3:0 3:1 ]
06: [ 1:0 2:1 6:0 ]
07: [ 1:0 3:1 5:0 ]
08: [ 1:0 8:1 ]
09: [ 2:0 2:1 5:0 ]
10: [ 2:0 3:1 4:0 ]
11: [ 2:0 7:1 ]
12: [ 3:0 6:1 ]
13: [ 4:0 5:1 ]
14: [ 9:0 ]
15: [ 1:1 2:0 2:1 4:0 ]
16: [ 1:1 2:0 6:1 ]
17: [ 1:1 3:0 5:1 ]
18: [ 1:1 4:0 4:1 ]
19: [ 1:1 8:0 ]
20: [ 2:1 3:0 4:1 ]
21: [ 2:1 7:0 ]
22: [ 3:1 6:0 ]
23: [ 4:1 5:0 ]
24: [ 9:1 ]
There are A227134(9)=14 and A227135(9)= 10 such partitions where the first part is respectively of sort 0 and 1.
The corresponding sets and perimeters are (format as in first example)
0042: .....1.1.1. .....1.1.1. 9
0043: .....1.1.11 .....1.1.11 9
0046: .....1.111. .....1.1.1. 9
0048: .....11.... .....11.... 9
0049: .....11...1 .....11...1 9
0058: .....111.1. .....1.1.1. 9
0059: .....111.11 .....1.1.11 9
0070: ....1...11. ....1...11. 9
0072: ....1..1... ....1..1... 9
0073: ....1..1..1 ....1..1..1 9
0079: ....1..1111 ....1..1..1 9
0120: ....1111... ....1..1... 9
0121: ....1111..1 ....1..1..1 9
0132: ...1....1.. ...1....1.. 9
0133: ...1....1.1 ...1....1.1 9
0135: ...1....111 ...1....1.1 9
0252: ...111111.. ...1....1.. 9
0253: ...111111.1 ...1....1.1 9
0258: ..1......1. ..1......1. 9
0259: ..1......11 ..1......11 9
0510: ..11111111. ..1......1. 9
0512: .1......... .1......... 9
0513: .1........1 .1........1 9
1023: .1111111111 .1........1 9
(End)
From Patrick Devlin, Jul 03 2013: (Start)
The six sets {4}, {0,4}, {1,3}, {0,1,3}, {1,2,3}, and {0,1,2,3,4}, and no others, have perimeter 4, so a(4)=6. These sets correspond to the labeled partitions (allowing 0 as a part) [4E], [0E, 4E], [1E, 3E], [0E, 1F, 3E], [1E, 3F], and [0E, 4F] (respectively).
To explain this bijection further, the partition itself (e.g., 32 = 0 + 2 + 4 + 5 + 9 + 12) corresponds to which integers of the set will contribute to the perimeter. Thus, this unlabeled partition of 32 corresponds to the family of sets of the form {0, ??, 2, ??, 4, 5, ??, 9, ??, 12}. Then we only need to decide for each gap (here represented as ??) whether or not to fill it in ("F") with the corresponding string of consecutive integers or to leave it empty ("E"). This decision making process is equivalent to labeling each integer immediately following a gap with "F" or "E" (to denote if the gap is filled or empty) subject to the four 'rules' above [Rules (ii) and (iii) force the appropriate labelings for places where there are no gap (in this example, before 0 and before 5). And rule (iv) ensures that consecutive gaps are not both filled (in order to preserve the 'boundary' of the set).].
In the unlabeled example 32 = 0 + 2 + 4 + 5 + 9 + 12, as we begin to label, rules (ii) and (iii) force us to have [0E, 2?, 4?, 5F, 9?, 12?]. Then since we may not have two consecutive labels of "F", we are forced to have [0E, 2?, 4E, 5F, 9E, 12?]. We can then label 2 as either "F" or "E" (which determines whether or not 1 is in the set), and we can independently label 12 as "F" or "E" (which determines whether or not {10, 11} is in the set). For instance, the labeling [0E, 2E, 4E, 5F, 9E, 12F] corresponds to the set {0, 2, 4, 5, 9, 10, 11, 12}, which has perimeter 32.
Given an unlabeled partition, after the partially labeling that's forced to satisfy rules (ii), (iii), and (iv), then the number of ways to extend this partial labeling to a valid labeling is related to the Fibonacci numbers (in a clear but perhaps useless way).
Noting that a(n) is the same as counting these 'labeled partitions' (allowing 0 as a part) may help prove the conjecture of Arndt [namely that a(n) = A227134(n) + A227135(n)].
(End)
MAPLE
a(n):=proc(n) # This computes a(n) in order n^3 time and order n^2 memory
return givenMax(n, n);
end proc:
## This helper function finds the number of sets with perimeter n
## and maximum element AT MOST m
givenMax:=proc(n, m) option remember:
# Begin base cases
if((n=0) and (m < 0)) then return 1: fi:
if((n=0) and (m >=0)) then return 2: fi:
if((n<0)) then return 0: fi:
if((n>0) and (m < 1)) then return 0: fi:
# End base cases
# Conditions based on the largest element
# of {-1, 0, 1, 2, ..., m} NOT in the sets of interest
return givenMax(n, m-1) + givenMax(n-m, m-2) + add(givenMax(n-m-(m-k), m-k-2), k=1..m);
end proc:
# Patrick Devlin, Jul 02 2013
MATHEMATICA
a[n_] := givenMax[n, n];
givenMax[n_, m_] := givenMax[n, m] = Which[n == 0 && m < 0, 1, n == 0 && m >= 0, 2, n < 0, 0, n > 0 && m < 1, 0, True, givenMax[n, m - 1] + givenMax[n-m, m-2] + Sum[givenMax[n - m - (m-k), m - k - 2], {k, 1, m}]];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Dec 14 2017, after Patrick Devlin *)
PROG
(PARI) {A002620(n)=floor(n/2)*ceil(n/2)}
{a(n)=polcoeff(2/(1-x+x*O(x^n)) + sum(m=2, sqrtint(4*n)+1, x^A002620(m+1)*(1+x^(m\2))/prod(k=1, m, 1-x^k+x*O(x^n))), n)}
for(n=0, 60, print1(a(n), ", ")) \\ Paul D. Hanna, Jul 06 2013
CROSSREFS
Cf. A227134 (corresponding partitions, first sort = 0), A227135 (first sort = 1).
Sequence in context: A225484 A130081 A141847 * A089333 A098492 A217314
KEYWORD
nonn
AUTHOR
John W. Layman, Apr 26 2012
EXTENSIONS
Prepended a(0) and added more terms, Joerg Arndt, Jun 01 2013
Changed a(0) = 2, allowing the empty set, Patrick Devlin, Jul 02 2013
STATUS
approved