A227538 -id:A227538 - cp's OEIS frontend

A186053 Smallest perimeter among all sets of nonnegative integers whose volume (sum) is n.

0, 1, 2, 2, 4, 5, 3, 6, 7, 6, 4, 8, 8, 9, 7, 5, 10, 11, 9, 10, 8, 6, 11, 12, 13, 10, 11, 9, 7, 14, 12, 13, 14, 11, 12, 10, 8, 16, 16, 13, 14, 15, 12, 13, 11, 9, 16, 17, 17, 14, 15, 16, 13, 14, 12, 10, 16, 17, 18, 18, 15, 16, 17, 14, 15, 13, 11, 22, 17, 18, 19, 19, 16, 17

Offset: 0

John W. Layman, Feb 11 2011

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.

For all partitions into distinct parts (with first part 0 implied), the perimeter of a set is the sum of parts p such that not both of p-1 and p+1 are in the partition. The partition with smallest perimeter is sometimes, but not often unique. For example, there are three partitions of volume 37 achieving the minimal perimeter 16, namely [ 0 1 2 3 4 5 6 7 x 9 ], [ x 2 x 5 6 7 8 9 ], and [0 x 2 x 5 6 7 8 9 ] (where x is for one or more skipped parts), but there is only one partition of 36 with minimal perimeter 8, namely [ 0 1 2 3 4 5 6 7 8 ]. [Joerg Arndt, Jun 03 2013]

			For n=8, the set S={0,1,2,5} has sum 8 and the perimeter 7 (the sum of 2 and 5).  No other set of volume 8 has a smaller perimeter, so a(8)=7.

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..2000 (terms n = 0..201 from Joerg Arndt)
Patrick Devlin, Sets with High Volume and Low Perimeter, arXiv:1107.2954 [math.CO], 2011.
Patrick Devlin, Integer Subsets with High Volume and Low Perimeter, arXiv:1202.1331 [math.CO], 2012.
Patrick Devlin, Integer Subsets with High Volume and Low Perimeter, INTEGERS, Vol. 12, #A32.
J. Miller, F. Morgan, E. Newkirk, L. Pedersen and D. Seferis, Isoperimetric Sets of Integers, Math. Mag. 84 (2011) 37-42.

Cf. A227538.

b:= proc(n, i, t) option remember; `if`(n=0 and i<>0, `if`(t>1, i+1, 0),
      `if`(i<0, infinity, min(`if`(t>1, i+1, 0)+b(n, i-1, iquo(t, 2)),
      `if`(i>n, NULL, `if`(t=2, i+1, 0)+b(n-i, i-1, iquo(t, 2)+2)))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..100);  # Alois P. Heinz, Jul 23 2013

notBoth[lst_List] := Select[lst, !MemberQ[lst, #-1] || !MemberQ[lst, #+1]&]; Table[s=Select[IntegerPartitions[n], Length[#]==Length[Union[#]]&]; s=Append[#,0]&/@s; Min[Table[Plus@@notBoth[i], {i,s}]], {n,40}]
(* Second program: *)
b[n_, i_, t_] := b[n, i, t] = If[n == 0 && i != 0, If[t > 1, i+1, 0], If[ i<0, Infinity, Min[If[t>1, i+1, 0] + b[n, i-1, Quotient[t, 2]], If[i > n, Infinity, If[t == 2, i+1, 0] + b[n-i, i-1, Quotient[t, 2]+2]]]]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Aug 29 2016, after Alois P. Heinz *)

If t(n) is a triangular number t(n)=n*(n+1)/2, then a(t(n))=n.

a(n) = A002024(n) + A182298(A025581(n)) unless n is one of the 114 known counterexamples listed in A182246. This allows the n-th term to be calculated in order log(log(n)) time using constant memory. The first n terms can be calculated in order n time (using order n memory). [Result and details in above listed paper by Patrick Devlin (2012).]

A227344 Triangle read by rows, partitions into distinct parts by perimeter.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 3, 0, 0, 0, 1, 0, 3, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 1, 0, 0, 7, 0, 0, 0, 0, 1, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 11, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 13, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 16, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 20, 0

Offset: 1

Joerg Arndt, Jul 08 2013

The perimeter of a partition is the sum of all parts p that do not have two neighbors (that is, not both p-1 and p+1 are parts).
Row sums are A000009.
Column sums are A122129 (noted by Patrick Devlin).

			Triangle starts (dots for zeros):
01: 1
02: . 1
03: . . 2
04: . . . 2
05: . . . . 3
06: . . . 1 . 3
07: . . . . . . 5
08: . . . . . . . 6
09: . . . . . 1 . . 7
10: . . . . 1 . . . . 9
11: . . . . . . . . 1 . 11
12: . . . . . . . 1 . 1 . 13
13: . . . . . . . . 1 . 1 . 16
14: . . . . . . 1 . . . . 1 . 20
15: . . . . . 1 . . . 1 . 1 1 . 23
16: . . . . . . . . . . 2 . 1 1 . 28
17: . . . . . . . . . . . 2 . 1 2 . 33
18: . . . . . . . . 1 . . 1 2 . 1 2 . 39
19: . . . . . . . . . 1 . . 1 1 1 1 3 . 46
20: . . . . . . . 1 . . . . . 1 1 2 1 3 . 55
21: . . . . . . 1 . . . . . . 2 2 1 2 1 4 . 63
22: . . . . . . . . . . 1 . 1 . 2 1 1 2 2 4 . 75
23: . . . . . . . . . . . 1 . 1 . 2 1 3 2 2 5 . 87
24: . . . . . . . . . . . . 1 . 1 2 3 . 4 2 3 5 . 101
25: . . . . . . . . . 1 . . . 1 . 1 1 3 . 6 2 3 7 . 117
26: . . . . . . . . . . 1 . 1 . . . 2 1 3 . 7 2 4 8 . 136
27: . . . . . . . . 1 . . . . 1 . . . 5 2 2 1 8 3 4 9 . 156
28: . . . . . . . 1 . . . . . . 1 1 . . 4 2 3 2 8 4 5 11 . 180
29: . . . . . . . . . . . . . . 1 2 1 . . 4 3 3 3 9 5 5 13 . 207
30: . . . . . . . . . . . 1 . . 1 1 1 1 . 3 6 2 2 5 9 6 6 14 . 238

Joerg Arndt, Table of n, a(n) for n = 1..5050

Cf. A227345 (partitions by boundary size).
Cf. A227426 (diagonal: number of partitions with maximal perimeter).
Cf. A227538 (smallest k with positive T(n,k)), A227614 (second lower diagonal). - Alois P. Heinz, Jul 17 2013

b:= proc(n, i, t) option remember; `if`(n=0, `if`(t>1, x^(i+1), 1),
      expand(`if`(i<1, 0, `if`(t>1, x^(i+1), 1)*b(n, i-1, iquo(t, 2))+
      `if`(i>n, 0, `if`(t=2, x^(i+1), 1)*b(n-i, i-1, iquo(t, 2)+2)))))
    end:
T:= n-> (p->seq(coeff(p, x, i), i=1..n))(b(n$2, 0)):
seq(T(n), n=1..20);  # Alois P. Heinz, Jul 16 2013

b[n_, i_, t_] := b[n, i, t] = If[n == 0, If[t>1, x^(i+1), 1], Expand[If[i<1, 0, If[t>1, x^(i+1), 1]*b[n, i-1, Quotient[t, 2]] + If[i>n, 0, If[t == 2, x^(i+1), 1]*b[n-i, i-1, Quotient[t, 2]+2]]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, n, 0]]; Table[T[n], {n, 1, 20}] // Flatten (* Jean-François Alcover, Jan 28 2015, after Alois P. Heinz *)

cp's OEIS Frontend

A186053 Smallest perimeter among all sets of nonnegative integers whose volume (sum) is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula