|
| |
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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).
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]
|
|
|
LINKS
|
|
|
|
FORMULA
|
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)):
|
|
|
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
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
