A227135 -id:A227135 - cp's OEIS frontend

A182372 Number of distinct sets of nonnegative integers with perimeter n, as defined in the comments.

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

John W. Layman, Apr 26 2012

nonn

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

			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)

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.

Cf. A186053, A182298.

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

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

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

{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

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

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

A227134 Partitions with parts repeated at most twice and repetition only allowed if first part has an odd index (first index = 1).

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 7, 8, 11, 14, 19, 22, 30, 36, 46, 55, 70, 83, 104, 123, 151, 179, 218, 256, 309, 363, 433, 507, 602, 701, 828, 961, 1127, 1306, 1525, 1759, 2046, 2355, 2725, 3129, 3609, 4131, 4750, 5424, 6214, 7081, 8090, 9195, 10478, 11886, 13506, 15290, 17335, 19583, 22154, 24981, 28197, 31741, 35757, 40176, 45176

Offset: 0

Joerg Arndt, Jul 02 2013

nonn

			G.f.: 1 + x + 2*x^2 + 2*x^3 + 4*x^4 + 4*x^5 + 7*x^6 + 8*x^7 + 11*x^8 + ...
G.f.: 1/(1-x) + x^2/((1-x)*(1-x^2)) + x^4/((1-x)*(1-x^2)*(1-x^3)) + x^6/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)) + x^9/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)*(1-x^5)) + x^12/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)*(1-x^5)*(1-x^6)) + ...
There are a(13)=36 such partitions, displayed here as partitions into two sorts of parts (format P:S for sort:part) where the first sort is 0 and sorts oscillate:
01:  [ 1:0  1:1  2:0  2:1  3:0  4:1  ]
02:  [ 1:0  1:1  2:0  2:1  7:0  ]
03:  [ 1:0  1:1  2:0  3:1  6:0  ]
04:  [ 1:0  1:1  2:0  4:1  5:0  ]
05:  [ 1:0  1:1  2:0  9:1  ]
06:  [ 1:0  1:1  3:0  3:1  5:0  ]
07:  [ 1:0  1:1  3:0  8:1  ]
08:  [ 1:0  1:1  4:0  7:1  ]
09:  [ 1:0  1:1  5:0  6:1  ]
10:  [ 1:0  1:1 11:0  ]
11:  [ 1:0  2:1  3:0  3:1  4:0  ]
12:  [ 1:0  2:1  3:0  7:1  ]
13:  [ 1:0  2:1  4:0  6:1  ]
14:  [ 1:0  2:1  5:0  5:1  ]
15:  [ 1:0  2:1 10:0  ]
16:  [ 1:0  3:1  4:0  5:1  ]
17:  [ 1:0  3:1  9:0  ]
18:  [ 1:0  4:1  8:0  ]
19:  [ 1:0  5:1  7:0  ]
20:  [ 1:0 12:1  ]
21:  [ 2:0  2:1  3:0  6:1  ]
22:  [ 2:0  2:1  4:0  5:1  ]
23:  [ 2:0  2:1  9:0  ]
24:  [ 2:0  3:1  4:0  4:1  ]
25:  [ 2:0  3:1  8:0  ]
26:  [ 2:0  4:1  7:0  ]
27:  [ 2:0  5:1  6:0  ]
28:  [ 2:0 11:1  ]
29:  [ 3:0  3:1  7:0  ]
30:  [ 3:0  4:1  6:0  ]
31:  [ 3:0 10:1  ]
32:  [ 4:0  4:1  5:0  ]
33:  [ 4:0  9:1  ]
34:  [ 5:0  8:1  ]
35:  [ 6:0  7:1  ]
36:  [13:0  ]

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

Cf. A227135 (parts may repeat after even index).

## Computes A227134 and A227135 in order n^2 time and order n^2 memory:
a34:=proc(n) # n-th term of A227134
  return oddMin(n,1):
end proc:
a35:=proc(n) # n-th term of A227135
  return evenMin(n,1):
end proc:
# oddMin(n,m) finds number of partitions of n (as in A227134) but with the
#  minimum part AT LEAST m
oddMin:=proc(n, m) option remember:
  if(n=0) then return 1: fi:  ## Start base cases
  if((n<0) or (m>n)) then return 0: fi:
  if(n=m) then return 1: fi:  ## End base cases
  return oddMin(n, m+1) + evenMin(n-m, m+1) + oddMin(n-2*m, m+1): ## How many times is the element m in the partition
end proc:
# evenMin(n,m) finds number of partitions of n (as in A227135) but with the
#  minimum part AT LEAST m
evenMin:=proc(n, m) option remember:
  if(n=0) then return 1: fi:   ## Start base cases
  if((n<0) or (m>n)) then return 0: fi:
  if(n=m) then return 1: fi:   ## End base cases
  return evenMin(n, m+1) + oddMin(n-m, m+1): ## Is the element m in the partition
end proc:
## Patrick Devlin, Jul 02 2013
# second Maple program:
b:= proc(n, i, t) option remember; `if`(n=0, t,
      `if`(i*(i+1) add(b(n$2, t), t=0..1):
seq(a(n), n=0..60);  # Alois P. Heinz, Feb 15 2017

nMax = 60; 1/(1-x) + Sum[x^Floor[(n+1)^2/4]/Product[1-x^k, {k, 1, n}], {n, 2, Ceiling @ Sqrt[4*nMax]}] + O[x]^(nMax+1) // CoefficientList[#, x]& (* Jean-François Alcover, Feb 15 2017, after Paul D. Hanna *)

{A002620(n)=floor(n/2)*ceil(n/2)}
{a(n)=polcoeff(1/(1-x+x*O(x^n)) + sum(m=2,sqrtint(4*n), x^A002620(m+1)/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

Conjecture: A227134(n) + A227135(n) = A182372(n) for n >= 0, see comment in A182372.
G.f.: 1/(1-x) + Sum_{n>=2} x^A002620(n+1) / 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
a(n) ~ c * exp(Pi*sqrt(2*n/5)) / n^(3/4), where c = 1 / (2^(1/4)*sqrt(5*(1 + sqrt(5)))) = 0.2090492823352... - Vaclav Kotesovec, May 28 2018, updated Mar 06 2020

cp's OEIS Frontend

A182372 Number of distinct sets of nonnegative integers with perimeter n, as defined in the comments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions