login
Triangle T(n,k) = Sum_{d|gcd(n,k)} mu(d)*C(n/d,k/d) (n >= 1, 1 <= k <= n).
2

%I #26 Oct 20 2019 01:55:02

%S 1,2,0,3,3,0,4,4,4,0,5,10,10,5,0,6,12,18,12,6,0,7,21,35,35,21,7,0,8,

%T 24,56,64,56,24,8,0,9,36,81,126,126,81,36,9,0,10,40,120,200,250,200,

%U 120,40,10,0,11,55,165,330,462,462,330,165,55,11,0,12,60

%N Triangle T(n,k) = Sum_{d|gcd(n,k)} mu(d)*C(n/d,k/d) (n >= 1, 1 <= k <= n).

%C Triangle of number of primitive words over {0,1} of length n that contain k 1's, for n,k >= 1. - _Benoit Cloitre_, Jun 08 2004

%D J.-P. Allouche and J. Shallit, Automatic sequences, Cambridge University Press, 2003, p. 29.

%H <a href="/index/Pas#Pascal">Index entries for triangles and arrays related to Pascal's triangle</a>

%e Triangle begins

%e 1;

%e 2, 0;

%e 3, 3, 0;

%e 4, 4, 4, 0;

%e 5, 10, 10, 5, 0;

%e 6, 12, 18, 12, 6, 0;

%e ...

%t T[n_, k_] := DivisorSum[GCD[k, n], MoebiusMu[#] Binomial[n/#, k/#] &]; Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Dec 02 2015 *)

%o (PARI) T(n,k)=sumdiv(gcd(k,n),d,moebius(d)*binomial(n/d,k/d)) \\ _Benoit Cloitre_, Jun 08 2004

%Y Cf. A042979, A042980. T(2n, n), T(2n+1, n) match A007727, A001700, respectively. Row sums match A027375.

%Y Same triangle as A050186 except this one does not include column 0.

%K nonn,tabl

%O 1,2

%A _N. J. A. Sloane_, Mar 24 2000