A114091 Number of partitions of n into parts that are distinct mod 3.

1, 1, 2, 2, 2, 4, 3, 3, 7, 4, 4, 11, 5, 5, 16, 6, 6, 22, 7, 7, 29, 8, 8, 37, 9, 9, 46, 10, 10, 56, 11, 11, 67, 12, 12, 79, 13, 13, 92, 14, 14, 106, 15, 15, 121, 16, 16, 137, 17, 17, 154, 18, 18, 172, 19, 19, 191, 20, 20, 211, 21, 21, 232, 22, 22, 254, 23, 23, 277, 24

Offset

1,3

Comments

Each partition can have at most three parts if n is a multiple of three and at most two parts otherwise. - Andrew Howroyd, Jan 28 2020

In general, these sequences can be generated by a linear recurrence with a signature that contains k=1..d tuples of the form (d-1 zeros, (-1)^(k-1) * binomial(d, k)), where d = number of distinct parts (here: d=3). - Georg Fischer, Sep 03 2022

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (0,0,3,0,0,-3,0,0,1).

Formula

a(3*n) = 1 + n + binomial(n, 2); a(3*n-1) = a(3*n-2) = n. - Andrew Howroyd, Jan 28 2020

Example

a(5)=2 because there are 2 such partition of 5: {5}, {2,3}.

Mathematica

<< DiscreteMath`Combinatorica`; np[n_]:= Length@Select[Mod[ #, 3]& /@ Partitions[n], (Length@# != Length@Union@#)&]; lst = Array[np, 50] (* or *)
LinearRecurrence[{0, 0, 3, 0, 0, -3, 0, 0, 1}, {1, 1, 2, 2, 2, 4, 3, 3, 7}, 64] (* Georg Fischer, Sep 03 2022 *)

Prog

(PARI) a(n)={1 + n\3 + if(n%3==0, binomial(n/3, 2))} \\ Andrew Howroyd, Jan 28 2020

Crossrefs

Cf. A008619(d=2), A114092(4), A114093(5), A114094(6), A114095(7), A114096(8), A114098(9), A114097(10).

Sequence in context: A338796 A085454 A083403 * A209580 A166008 A194291

Adjacent sequences: A114088 A114089 A114090 * A114092 A114093 A114094

Keyword

nonn

Author

Giovanni Resta, Feb 06 2006

Extensions

Terms a(51) and beyond from Andrew Howroyd, Jan 28 2020

Status

approved