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

Author

Giovanni Resta, Feb 06 2006

Keywords

• nonn

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

Examples

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

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).

Crossrefs

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

Programs

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 *)

PARI

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

Formula

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

Extensions

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