login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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).

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]

LINKS

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

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: A244966 A079100 A244233 * A123262 A191906 A187080

Adjacent sequences:  A227342 A227343 A227344 * A227346 A227347 A227348

KEYWORD

nonn,tabl

AUTHOR

Joerg Arndt, Jul 08 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 18 17:56 EST 2017. Contains 294894 sequences.