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.