This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A182372 #79 Feb 10 2025 21:03:21
%S A182372 2,2,3,4,6,8,11,14,19,24,31,39,50,61,77,94,117,141,173,208,253,302,
%T A182372 363,431,516,609,723,850,1003,1174,1379,1607,1878,2181,2537,2936,3404,
%U A182372 3925,4532,5212,5998,6877,7890,9021,10320,11771,13427,15277,17385,19734,22401,25375,28739,32485
%N A182372 Number of distinct sets of nonnegative integers with perimeter n, as defined in the comments.
%C A182372 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.
%C A182372 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
%C A182372 The conjecture of Arndt [namely that a(n) = A227134(n) + A227135(n)] has been verified for n < 1200. - _Patrick Devlin_, Jul 02 2013
%C A182372 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
%H A182372 Joerg Arndt, <a href="/A182372/b182372.txt">Table of n, a(n) for n = 0..200</a>
%H A182372 Patrick Devlin, <a href="http://arxiv.org/abs/1202.1331">Integer Subsets with High Volume and Low Perimeter</a>, arXiv:1202.1331 [math.CO], 2012.
%H A182372 J. Miller, F. Morgan, E. Newkirk, L. Pedersen and D. Seferis, <a href="http://www.jstor.org/stable/10.4169/math.mag.84.1.037">Isoperimetric Sets of Integers</a>, Math. Mag. 84 (2011) 37-42.
%F A182372 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
%e A182372 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 + ...
%e A182372 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
%e A182372 From _Joerg Arndt_, Jun 01 2013: (Start)
%e A182372 ##: set perimeter sum(perimeter)
%e A182372 00: ....... ....... 0 (empty set)
%e A182372 01: ......1 ......1 0
%e A182372 02: .....1. .....1. 1
%e A182372 03: .....11 .....11 1
%e A182372 04: ....1.. ....1.. 2
%e A182372 05: ....1.1 ....1.1 2
%e A182372 06: ....11. ....11. 3
%e A182372 07: ....111 ....1.1 2
%e A182372 08: ...1... ...1... 3
%e A182372 09: ...1..1 ...1..1 3
%e A182372 10: ...1.1. ...1.1. 4
%e A182372 11: ...1.11 ...1.11 4
%e A182372 12: ...11.. ...11.. 5
%e A182372 13: ...11.1 ...11.1 5
%e A182372 14: ...111. ...1.1. 4
%e A182372 15: ...1111 ...1..1 3
%e A182372 16: ..1.... ..1.... 4
%e A182372 17: ..1...1 ..1...1 4
%e A182372 18: ..1..1. ..1..1. 5
%e A182372 19: ..1..11 ..1..11 5
%e A182372 20: ..1.1.. ..1.1.. 6
%e A182372 21: ..1.1.1 ..1.1.1 6
%e A182372 22: ..1.11. ..1.11. 7
%e A182372 23: ..1.111 ..1.1.1 6
%e A182372 24: ..11... ..11... 7
%e A182372 25: ..11..1 ..11..1 7
%e A182372 26: ..11.1. ..11.1. 8
%e A182372 27: ..11.11 ..11.11 8
%e A182372 28: ..111.. ..1.1.. 6
%e A182372 29: ..111.1 ..1.1.1 6
%e A182372 30: ..1111. ..1..1. 5
%e A182372 31: ..11111 ..1...1 4
%e A182372 The last set contribution to a(n) n has index 2^(n+1)-1, so the statistics is complete up to 4.
%e A182372 We find a(1)=2, a(1)=2, a(2)=2, and a(4)=6.
%e A182372 (End)
%e A182372 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.
%e A182372 From _Joerg Arndt_, Jun 01 2013: (Start)
%e A182372 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"):
%e A182372 01: [ 1:0 1:1 2:0 2:1 3:0 ]
%e A182372 02: [ 1:0 1:1 2:0 5:1 ]
%e A182372 03: [ 1:0 1:1 3:0 4:1 ]
%e A182372 04: [ 1:0 1:1 7:0 ]
%e A182372 05: [ 1:0 2:1 3:0 3:1 ]
%e A182372 06: [ 1:0 2:1 6:0 ]
%e A182372 07: [ 1:0 3:1 5:0 ]
%e A182372 08: [ 1:0 8:1 ]
%e A182372 09: [ 2:0 2:1 5:0 ]
%e A182372 10: [ 2:0 3:1 4:0 ]
%e A182372 11: [ 2:0 7:1 ]
%e A182372 12: [ 3:0 6:1 ]
%e A182372 13: [ 4:0 5:1 ]
%e A182372 14: [ 9:0 ]
%e A182372 15: [ 1:1 2:0 2:1 4:0 ]
%e A182372 16: [ 1:1 2:0 6:1 ]
%e A182372 17: [ 1:1 3:0 5:1 ]
%e A182372 18: [ 1:1 4:0 4:1 ]
%e A182372 19: [ 1:1 8:0 ]
%e A182372 20: [ 2:1 3:0 4:1 ]
%e A182372 21: [ 2:1 7:0 ]
%e A182372 22: [ 3:1 6:0 ]
%e A182372 23: [ 4:1 5:0 ]
%e A182372 24: [ 9:1 ]
%e A182372 There are A227134(9)=14 and A227135(9)= 10 such partitions where the first part is respectively of sort 0 and 1.
%e A182372 The corresponding sets and perimeters are (format as in first example)
%e A182372 0042: .....1.1.1. .....1.1.1. 9
%e A182372 0043: .....1.1.11 .....1.1.11 9
%e A182372 0046: .....1.111. .....1.1.1. 9
%e A182372 0048: .....11.... .....11.... 9
%e A182372 0049: .....11...1 .....11...1 9
%e A182372 0058: .....111.1. .....1.1.1. 9
%e A182372 0059: .....111.11 .....1.1.11 9
%e A182372 0070: ....1...11. ....1...11. 9
%e A182372 0072: ....1..1... ....1..1... 9
%e A182372 0073: ....1..1..1 ....1..1..1 9
%e A182372 0079: ....1..1111 ....1..1..1 9
%e A182372 0120: ....1111... ....1..1... 9
%e A182372 0121: ....1111..1 ....1..1..1 9
%e A182372 0132: ...1....1.. ...1....1.. 9
%e A182372 0133: ...1....1.1 ...1....1.1 9
%e A182372 0135: ...1....111 ...1....1.1 9
%e A182372 0252: ...111111.. ...1....1.. 9
%e A182372 0253: ...111111.1 ...1....1.1 9
%e A182372 0258: ..1......1. ..1......1. 9
%e A182372 0259: ..1......11 ..1......11 9
%e A182372 0510: ..11111111. ..1......1. 9
%e A182372 0512: .1......... .1......... 9
%e A182372 0513: .1........1 .1........1 9
%e A182372 1023: .1111111111 .1........1 9
%e A182372 (End)
%e A182372 From _Patrick Devlin_, Jul 03 2013: (Start)
%e A182372 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).
%e A182372 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).].
%e A182372 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.
%e A182372 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).
%e A182372 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)].
%e A182372 (End)
%p A182372 a(n):=proc(n) # This computes a(n) in order n^3 time and order n^2 memory
%p A182372 return givenMax(n, n);
%p A182372 end proc:
%p A182372 ## This helper function finds the number of sets with perimeter n
%p A182372 ## and maximum element AT MOST m
%p A182372 givenMax:=proc(n, m) option remember:
%p A182372 # Begin base cases
%p A182372 if((n=0) and (m < 0)) then return 1: fi:
%p A182372 if((n=0) and (m >=0)) then return 2: fi:
%p A182372 if((n<0)) then return 0: fi:
%p A182372 if((n>0) and (m < 1)) then return 0: fi:
%p A182372 # End base cases
%p A182372 # Conditions based on the largest element
%p A182372 # of {-1, 0, 1, 2, ..., m} NOT in the sets of interest
%p A182372 return givenMax(n, m-1) + givenMax(n-m, m-2) + add(givenMax(n-m-(m-k), m-k-2), k=1..m);
%p A182372 end proc:
%p A182372 # _Patrick Devlin_, Jul 02 2013
%t A182372 a[n_] := givenMax[n, n];
%t A182372 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}]];
%t A182372 Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Dec 14 2017, after _Patrick Devlin_ *)
%o A182372 (PARI) {A002620(n)=floor(n/2)*ceil(n/2)}
%o A182372 {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)}
%o A182372 for(n=0,60,print1(a(n),", ")) \\ _Paul D. Hanna_, Jul 06 2013
%Y A182372 Cf. A186053, A182298.
%Y A182372 Cf. A227134 (corresponding partitions, first sort = 0), A227135 (first sort = 1).
%K A182372 nonn
%O A182372 0,1
%A A182372 _John W. Layman_, Apr 26 2012
%E A182372 Prepended a(0) and added more terms, _Joerg Arndt_, Jun 01 2013
%E A182372 Changed a(0) = 2, allowing the empty set, _Patrick Devlin_, Jul 02 2013