login
A227345
Triangle read by rows, partitions into distinct parts by size of boundary.
14
1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 2, 0, 0, 0, 1, 3, 0, 0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 1, 3, 2, 0, 0, 0, 0, 0, 1, 5, 2, 0, 0, 0, 0, 0, 0, 1, 5, 4, 0, 0, 0, 0, 0, 0, 0, 1, 5, 6, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 10, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 7, 11, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 9, 13, 4, 0
OFFSET
1,12
COMMENTS
The boundary size of a partition is the number of parts p that do not have two neighbors (that is, not both p-1 and p+1 are parts).
Row sums are A000009.
Conjecture: there exists a partition (into distinct parts) of n with boundary size k if and only if 0 < k^2 * 3/4 <= n. [Patrick Devlin, Jul 13 2013]
FORMULA
From Patrick Devlin, Jul 13 2013: (Start)
Let a(n,k) denote the number of partitions into distinct parts of n with boundary size k. Then for all n>0 and k>=0, we have a(n,k+1) >= floor(binomial(n-k, k) * 2^(-binomial(k, 2))) = floor(binomial(n-k, k) * 2^(-A000217(k)). (Proof is by noting a(n,k) >= sum(a(j,k-1), j=1..(n/2-1)).)
On the other hand, for all n>0 and k>=0, we also have that a(n,k+1) <= binomial(n-k,k)*A000045(k+1). This is obtained by considering the largest k parts of the boundary, which must be some subset of {1, 2, ..., n-k}. Then the possible 'gaps' of the boundary can each either be filled with the corresponding consecutive integers or left empty. (End)
EXAMPLE
Triangle starts (dots for zeros, trailing zeros omitted for n>=14):
01: 1
02: 1 .
03: 1 1 .
04: 1 1 . .
05: 1 2 . . .
06: 1 3 . . . .
07: 1 3 1 . . . .
08: 1 3 2 . . . . .
09: 1 5 2 . . . . . .
10: 1 5 4 . . . . . . .
11: 1 5 6 . . . . . . . .
12: 1 6 7 1 . . . . . . . .
13: 1 6 10 1 . . . . . . . . .
14: 1 7 11 3 . . . . . . . . .
15: 1 9 13 4 . . . . . . . . .
16: 1 7 18 6 . . . . . . . . .
17: 1 8 20 9 . . . . . . . . .
18: 1 10 21 14 . . . . . . . .
19: 1 9 27 16 1 . . . . . . .
20: 1 10 29 22 2 . . . . . . .
21: 1 12 32 28 3 . . . . . . .
22: 1 11 37 35 5 . . . . . . .
23: 1 11 42 42 8 . . . . . . .
24: 1 12 45 53 11 . . . . . .
25: 1 13 49 62 17 . . . . . .
26: 1 13 54 73 24 . . . . . .
27: 1 15 58 86 31 1 . . . . .
28: 1 14 65 98 43 1 . . . . .
29: 1 14 70 114 54 3 . . . . .
30: 1 17 72 134 67 5 . . . . .
31: 1 15 82 148 86 8 . . . . .
32: 1 15 87 168 108 11 . . . .
33: 1 18 90 192 129 18 . . . .
34: 1 17 98 212 160 24 . . . .
35: 1 19 103 235 192 35 . . .
36: 1 19 111 264 224 49 . . .
37: 1 18 119 289 268 64 1 . .
38: 1 19 124 320 315 83 2 . .
39: 1 21 130 355 360 112 3 . .
40: 1 20 139 385 424 138 6 . .
In particular, for the tenth row of this table, note that the partitions of ten into distinct parts are 10 = 10 = 9 + 1 = 8 + 2 = 7 + 3 = 6 + 4 = 4 + 3 + 2 + 1 = 7 + 2 + 1 = 6 + 3 + 1 = 5 + 4 + 1 = 5 + 3 + 2. These partitions are sorted by increasing number of parts in the boundary. In particular, note that 4 + 3 + 2 + 1 has only two parts in its boundary (namely 4 and 1). [Patrick Devlin, Jul 13 2013]
MAPLE
b:= proc(n, i, t) option remember; `if`(n=0, `if`(t>1, x, 1),
expand(`if`(i<1, 0, `if`(t>1, x, 1)*b(n, i-1, iquo(t, 2))+
`if`(i>n, 0, `if`(t=2, x, 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
MATHEMATICA
b[n_, i_, t_] := b[n, i, t] = If[n == 0, If[t>1, x, 1], Expand[If[i<1, 0, If[t>1, x, 1]*b[n, i-1, Quotient[t, 2]] + If[i>n, 0, If[t == 2, x, 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, Feb 18 2015, after Alois P. Heinz *)
CROSSREFS
Cf. A227344 (partitions by perimeter).
Columns k=1-10 give: A057427 (for n>=1), A227559, A227560, A227561, A227562, A227563, A227564, A227565, A227566, A227567. Cf. A227551 (a version without trailing zeros), A227552. - Alois P. Heinz, Jul 16 2013
Sequence in context: A079100 A296167 A244233 * A123262 A191906 A371647
KEYWORD
nonn,tabl
AUTHOR
Joerg Arndt, Jul 08 2013
STATUS
approved