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.
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.