The discussion centers on the function S_n, which represents the number of ways to express a positive integer n as a sum of positive integers, where the order of summands matters. The values established are S_1=1, S_2=2, and S_3=4, with the recursive relationship S_n = S_{n-1} + S_{n-2} - S_1 + 1. The confusion arises from the notation and the interpretation of expressing integers, specifically regarding the different combinations that yield the same sum. The example provided clarifies that S_3 can be expressed in four distinct ways: 1+1+1, 2+1, 1+2, and 3.
PREREQUISITESMathematicians, students studying combinatorics, and anyone interested in the theory of integer partitions and recursive functions.
nicksauce said:Sorry, but to me it's not clear what your question means. What does it mean to express a positive integer as positive integers? I can only think of one way to express 3 as a positive integer, namely by 3. Can you show how S_3 = 4?
Your notation in the equation is also confusing. What is the meaning of three consecutive minus signs?
Yup that's what I meanttmccullough said:I assume that you mean S_n is the number of ways to express n as a sum of positive integers, where orders matters.
Consider the different cases for the last integer in the sum, all of which are disjoint, since order matters. There are n different cases.
Explicitly: if the last integer is 1, then the rest of the integers sum to n-1...