=========================== Combinatoric Interpretation of a(n,m) Russell Jay Hendel, Jun 25, 2015 Sequence a0034870 =========================== We prove a(n,m) = #s(n,m) with # indicating cardinality, a(n,m)=binomial(2n,m), and s(n,m) equaling the set of base-4, n-digit numbers (with left padding of zeroes if necessary) with n-m more 1-digits than 2-digits. Tables 1,2 and 3 illustrate the proof. The notation bS used in Table 3 where b is a base-4 digit and S is a set of n-digit, base-4 numbers indicates the set of all (n+1)-digit, base-4 numbers with b as their prefix (1st digit) and x, a member of S, as their suffix (last n digits). =========== TABLE 1=============== 1 1 2 1 1 4 6 4 1 ================================= Table 1. Non zero values of a(n,m)=binomial(2n,m) for n<=2. ============ TABLE 2============== {} {2} {0,3} {1} {11} {10,01,13,31} {12,21,00,03,30,33} {20,02,23,32} {22} ================================= Table 2. Values of s(n,m) for n<=2. s(n,m) is the set of base-4, n-digit numbers with n-m more 1-digits than 2-digits. Notice that #s(n,m)=a(n,m), for 0 <= n <= 2, with # indicating cardinality. ===============TABLE 3================= 2s(2,1) = 2{10,01,13,31} = {210,201,213,231} 0s(2,2) = 0{12,21,00,03,30,33} = {012,021,000,003,030,033} 3s(2,2) = 3{12,21,00,03,30,33} = {312,321,300,303,330,333} 1s(2,3) = 1{20,02,23,32} = {120,102,123,132} ===================================== Table 3. The union of the right hand sides of the 4 equations equals s(3,3) which contains the 20 base-4, 3-digit numbers with an equal number of 1-digits and 2-digits. As shown, s(3,3) can be recursively built up from the values of s(2,x). We have the following relation. s(3,3)=2s(2,1) UNION 0s(2,2) UNION 3s(2,2) UNION 1s(2,3). This set relation corresponds to the numerical relation a(3,3)=a(2,1)+2a(2,2)+a(2,3). It will facilitate the formal proof if we first introduce the difference function d. Let d(n) equals the number of 1-digits in the base-4 representation of n less the number of 2-digits in n. If S is a set of base-4, n-digit numbers such that d(x)=c, for some constant c, for all x in S, then we define d(S) = c.(If d is not constant on S, then d(S) is undefined). Lemma: When d(S) is defined, we have d(0S) = d(S), d(3S) = d(S), d(1S) = d(S)+1, and d(2S) = d(S)-1. Proof: Clear. For example, if all members, x, of S, have d(x) = c, then d(1x) = 1+c since there is now one more 1-digit. Examples: The 4 rows of Table 3 illustrate the lemma since, for example, using the 1st row, d(s(2,1) = 1 and d(2s(2,1)) = 0. We now prove a(n,m) = #s(n,m). The inductive proof follows the verbal counting methods in [1]. The use of verbal counting methods is greatly facilitated using the correspondence between numbers and sets presented in Tables 1 and 2. More specifically, the proof is motivated by the fact that a(n,m)-identities in numbers neatly correspond to s(n,m)-identities in sets. We show i) that a(n,m) and #s(n,m) both agree on initial values and ii) that a(n,m) and #s(n,m) both obey the same recursion. It then immediately follows that a(n,m) and #s(n,m) are always equal. i) Proof that a(n,m) = #s(n,m) for initial values. ================================ Tables 1 and 2 show that a(n,m)=#s(n,m) for 0 <=n<=2 and all values of m. ii) Proof that a(n,m) and #s(n,m) both obey the same recursion. =========================================== a(n,m) satisfies the following recursion. a(n,m) = binomial(2n,m)=binomial(2n-1,m)+binomial(2n-1,m-1) = (binomial(2n-2,m)+binomial(2n-2,m-1)+ (binomial(2n-2,m-1)+binomial(2n-2,m-2) = a(n-1,m)+2a(n-1,m-1)+a(n-1,m-2) Clearly every n-digit, base-4 number begins with a 0, 1, 2 or 3. But then by Lemma 1, s(n,m) = 1s(n-1,m) UNION 0s(n-1,m-1) UNION 3s(n-1,m-1) UNION 2s(n-1,m-1). By applying the cardinality function to each side of the last equation we obtain #s(n,m) = #s(n-1,m) + 2#s(n-1,m-1) + #s(n-1,m-2). This completes the proof. References ======== [1] Arthur T. Benjamin and Jennifer Quinn, "Proofs that Really Count: The Art of Combinatorial Proof," Dolciani Mathematical Expositions, MAA Publications, 2003.