A227345 Triangle read by rows, partitions into distinct parts by size of boundary.
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
Examples
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
Links
- Joerg Arndt, Table of n, a(n) for n = 1..5050
Crossrefs
Programs
-
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 *)
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_{j=1..(n/2-1)} a(j,k-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)
Comments