Some identities for A194602 (Li-yao Xia) ======================================== Here are short proofs of identities for A194602 proposed by Tilman Piesk. Description of A194602: a(m): This sequence (A194602) p(n): The number of integer partitions of n, or equivalently, nondecreasing compositions of n (A000041) a is an increasing sequence. Equivalently, as a sequence of binary numbers, it is in lexicographical order. For 0 <= i < p(n), a(i) is associated to a nondecreasing composition of n, denoted by A(n,i). E.g., for n = 7, a(11) = 43 =(base 2) 0101011 -> A(7, 11) = [2 2 3], for n = 8, a(11) =(base 2) 00101011 -> A(8, 11) = [1 2 2 3]. Note that for a given integer n, A(n, 0), ..., A(n, p(n)-1) do not all have the same length. A(8, 11) = [1 2 2 3] A(8, 12) = [1 2 5] Although it is certainly possible to reason directly about the bit patterns of terms a(m), it might be clearer to rely on another interpretation of the ordering of a. Observation: For any integer n, the compositions of n represented by the first p(n) terms of a are in lexicographical order: If 0 <= i < j < p(n), then A(n,i) <_lex A(n,j). (<_lex: lexicographically smaller than) Proof omitted. E.g., n = 8, 10 < 11 < 12 < 13, and A(8, 10) < A(8, 11) < A(8, 12) < A(8, 13): 1 = 1 = 1 = 1 1 < 2 = 2 < 3 6 2 < 5 4 3 --- a(p(2n-1)) = 0101...01 (2n bits), corresponding to the partition of 2n with n addends 2: A(2n,p(2n-1)) = [2 ... 2]. Proof: a(0), ..., a(p(2n)-1): compositions of 2n. a(0), ..., a(p(2n-1)-1): compositions of 2n with one addend of size 1. Then a(p(2n-1)) is the smallest composition of 2n with zero addend of size 1, i.e., they all have to be greater than or equal to 2. The smallest such composition is [2 ... 2]. --- a(p(n)-1) = 011...1 (n bits), corresponding to the partition of n with only one addend: A(n,p(n)-1) = [n]. Proof: That is indeed the greatest among the p(n) compositions of n. Proof': As the n-bit binary representation of a composition of n, a(p(n)-1) must have a leading 0. It is clear that 011...1 is an upper bound, actually achieved by a nondecreasing composition. --- a(p(2n)-2) = 01...101...1 (n+n bits), corresponding to the partition of 2n with two addends of equal size: A(2n,p(2n)-2) = [n n]. Proof: Since there is only one composition of 2n with one addend [2n], the penultimate composition must have at least two addends, the first of which is smaller than the other(s). The greatest possible value for this addend is n. --- a(p(3n)-floor(n/2)-3) = 01...101...101...1 (n+n+n bits), corresponding to the partition of 3n with three addends of equal size: A(3n,p(3n)-floor(n/2)-3) = [n n n]. Proof: Compositions of 3n that are greater than [n n n] are: - [3n], and - [n' 3n-n'], for n <= n' <= 3n-n', that is n <= n' <= 3n/2 ([n n n] is the greatest composition of 3n with three addends.) There are 1 + (floor(3n/2) - n + 1) = floor(n/2) + 2, which leads to the above formula by counting down from the last composition, with index p(3n)-1.