A003158

A003158 is a sequence in the On-Line Encyclopedia of Integer Sequences (OEIS). The sequence is defined as the number of partitions of n into parts not divisible by 3. A partition of a positive integer n is a way of writing n as a sum of positive integers, where the order of the summands does not matter. For example, the partitions of 4 are 4, 3+1, 2+2, 2+1+1, and 1+1+1+1.

The sequence A003158 begins with the following terms: 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 45, 53, 62, 72, 83, 95, 108, 122, 137, 153, 170, 188, ...

This sequence arises in various combinatorial contexts. One way to interpret it is as the number of ways to form a sum of n using only integers that are congruent to 1 or 2 modulo 3. For instance, for n=4, the partitions into parts not divisible by 3 are 4 (as 4 is not divisible by 3), 2+2, 2+1+1, and 1+1+1+1. The partition 3+1 is excluded because 3 is divisible by 3.

The generating function for A003158 is given by the infinite product:

(1/(1-x)) * (1/(1-x^2)) * (1/(1-x^4)) * (1/(1-x^5)) * (1/(1-x^7)) * (1/(1-x^8)) * ...

This can be more compactly written as:

Product_{k=1 to infinity} (1/(1-x^(3k-2)) * (1/(1-x^(3k-1)))

This sequence is related to other combinatorial sequences and can be computed using recurrence relations, although these can be complex. The OEIS entry A003158 provides further details, including additional formulas, references, and related sequences.