2
$\begingroup$

Here $$T(n,k)=\sum\limits_{d|\gcd(n,k)}\frac{\varphi(d)}{n+k}\binom{(n+k)/d}{n/d}$$

First I need to show where from this formulas came up.

2) 00, 01=10, 11

3) 000, 001=010=100, 011=110=101, 111

4) 0000, 0001=0010=0100=1000, 0011=0110=1100=1001, 0101=1010, 0111=1110=1101=1011, 1111

etc., so we have:

2) {00, 10, 11}

3) {000, 100, 110, 111}

4) {0000, 1000, 1100, 1010, 1110, 1111}

5) {00000, 10000, 11000, 10100, 11100, 11010, 11110, 11111}

6) {000000, 100000, 110000, 101000, 100100, 111000, 110100, 110010, 101010, 111100, 111010, 110110, 111110, 111111}

or, more concretely:

2) {00}{01}{11}

3) {000}{100}{110}{111}

4) {0000}{1000}{1100, 1010}{1110}{1111}

5) {00000}{10000}{11000, 10100}{11100, 11010}{11110}{11111}

6) {000000}{100000}{110000, 101000, 100100}{111000, 110100, 110010, 101010}{111100, 111010, 110110}{111110}{111111}

then we can say, that

2) 1+1+1=3

3) 1+1+1+1=4

4) 1+1+2+1+1=6

5) 1+1+2+2+1+1=8

6) 1+1+3+4+3+1+1=14

7) 1+1+3+5+5+3+1+1=20

If we go to OEIS and write this, we can find two sequence (A000031, A241926).

Why are they have those formulas? Why if we make diagonal summation in second and add to result $2$ it will be equal to one of the terms of first?

If I made some mistakes, sorry for my English.

$\endgroup$
3
$\begingroup$

We observe that the LHS counts necklaces with two colors of beads. We get for the RHS

$$2+\frac{1}{n} \sum_{k=1}^{n-1} \sum_{d|\gcd(n,k)} \varphi(d) {n/d\choose (n-k)/d} \\ = 2+\frac{1}{n} \sum_{k=1}^{n-1} \sum_{d|\gcd(n,k)} \varphi(d) {n/d\choose k/d}.$$

This is

$$2 + \frac{1}{n} \sum_{d|n} \sum_{k=1, \; d|\gcd(n,k)}^{n-1} \varphi(d) {n/d\choose k/d} \\ = 2 + \frac{1}{n} \sum_{d|n} \varphi(d) \sum_{q=1}^{\lfloor (n-1)/d \rfloor} {n/d\choose q} \\ = 2 + \frac{1}{n} \sum_{d|n} \varphi(d) \left( - {n/d\choose 0} - {n/d\choose n/d} + 2^{n/d} \right) \\ = 2 + \frac{1}{n} \sum_{d|n} \varphi(d) 2^{n/d} - 2 \frac{1}{n} \sum_{d|n} \varphi(d) \\ = \frac{1}{n} \sum_{d|n} \varphi(d) 2^{n/d}.$$

This is the claim.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.