login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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 labelled "E" or "F", (ii) t_1 is labelled "E", (iii) if t_j - t_{j-1} = 1, then t_j is labelled "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

Joerg Arndt, Table of n, a(n) for n = 0..200

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 labelled 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 unlabelled 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 labelling 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 labellings 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 unlabelled 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 labelling [0E, 2E, 4E, 5F, 9E, 12F] corresponds to the set {0, 2, 4, 5, 9, 10, 11, 12}, which has perimeter 32.

Given an unlablled partition, after the partially labelling that's forced to satisfy rules (ii), (iii), and (iv), then the number of ways to extend this partial labelling to a valid labelling is related to the Fibonacci numbers (in a clear but perhaps useless way).

Noting that a(n) is the same as counting these 'labelled 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

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. A186053, A182298.

Cf. A227134 (corresponding partitions, first sort =0), A227135 (first sort =1).

Sequence in context: A225484 A130081 A141847 * A089333 A098492 A217314

Adjacent sequences:  A182369 A182370 A182371 * A182373 A182374 A182375

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 22 00:13 EDT 2017. Contains 289648 sequences.