A267632 - OEIS

%I #61 Aug 20 2019 12:45:07

%S 1,1,0,1,1,1,1,1,1,0,1,2,2,1,1,1,2,4,3,1,0,1,3,5,5,3,1,1,1,3,7,9,7,3,

%T 1,0,1,4,10,14,14,10,4,1,1,1,4,12,22,26,20,12,5,1,0,1,5,15,30,42,42,

%U 30,15,5,1,1,1,5,19,42,66,76,66,43,19,5,1,0

%N Triangle T(n, k) read by rows: the k-th column of the n-th row lists the number of ways to select k distinct numbers (k >= 1) from [1..n] so that their sum is divisible by n.

%C Row less the last element is palindrome for n=odd or n=power of 2 where n is the row number (observation-conjecture).

%C From _Petros Hadjicostas_, Jul 13 2019: (Start)

%C By reading carefully the proof of Lemma 5.1 (pp. 65-66) in Barnes (1959), we see that he actually proved a general result (even though he does not state it in the lemma).

%C According to the definition of this sequence, for 1 <= k <= n, T(n, k) is the number of unordered sets b_1, b_2, ..., b_k of k distinct integers from 1..n such that b_1 + b_2 + ... + b_k = 0 (mod n). The proof of Lemma 5.1 in Barnes (1959) implies that T(n, k) = (1/n) * Sum_{s | gcd(n, k)} (-1)^(k - (k/s)) * phi(s) * binomial(n/s, k/s) for 1 <= k <= n.

%C For fixed k >= 1, the g.f. of the column (T(n, k): n >= 1) (with T(n, k) = 0 for 1 <= n < k) is (x^k/k) * Sum_{s|k} phi(s) * (-1)^(k - (k/s)) / (1 - x^s)^(k/s), which generalizes _Herbert Kociemba_'s formula from A032801.

%C Barnes' (1959) formula is a special case of Theorem 4 (p. 66) in Ramanathan (1944). If R(n, k, v) is the number of unordered sets b_1, b_2, ..., b_k of k distinct integers from 1..n such that b_1 + b_2 + ... + b_k = v (mod n), then he proved that R(n, k, v) = (1/n) * Sum_{s | gcd(n,k)} (-1)^(k - (k/s)) * binomial(n/s, k/s) * C_s(v), where C_s(v) = A054535(s, v) =  Sum_{d | gcd(s,v)} d * Moebius(s/d) is Ramanujan's sum (even though it was first discovered around 1900 by the Austrian mathematician R. D. von Sterneck).

%C Because C_s(v = 0) = phi(s), we get Barnes' (implicit) result; i.e., R(n, k, v=0) = T(n, k) for 1 <= k <= n.

%C For k=2, we have R(n, k=2, v=0) = T(n, k=2) = A004526(n-1) for n >= 1. For k=3, we have R(n, k=3, v=0) = T(n, k=3) = A058212(n) for n >= 1. For k=4, we have R(n, k=4, v=0) = A032801(n) for n >= 1. For k=5, we have R(n, k=5, v=0) = T(n, k=5) = A008646(n-5) for n >= 5.

%C The reason we have T(2*m+1, k) = A037306(2*m+1, k) = A047996(2*m+1, k) for m >= 0 and k >= 1 is the following. When n = 2*m + 1, all divisors s of gcd(n, k) are odd. In such a case, k - (k/s) is even for all k >= 1, and thus (-1)^(k - (k/s)) = 1, and thus T(n = 2*m+1, k) = (1/n) * Sum_{s | gcd(n, k)} phi(s) * binomial(n/s, k/s) = A037306(2*m+1, k) = A047996(2*m+1, k).

%C By summing the products of the g.f. of column k times y^k from k = 1 to k = infinity, we get the bivariate g.f. for the array: Sum_{n, k >= 1} T(n, k)*x^n*y^k = Sum_{s >= 1} (phi(s)/s) * log((1 - x^s + (-x*y)^s)/(1 - x^s)) = -x/(1 - x) - Sum_{s >= 1} (phi(s)/s) * log(1 - x^s + (-x*y)^s).

%C Letting y = 1 in the above bivariate g.f., we get the g.f. of the sequence (Sum_{1 <= k <= n} T(n, k): n >= 1) is -x/(1 - x) - Sum_{s >= 1} (phi(s)/s) * log(1 - x^s + (-x)^s) = -x/(1 - x) + Sum_{m >= 0} (phi(2*m + 1)/(2*m + 1)) * log(1 - 2*x^(2*m+1)), which is the g.f. of sequence A082550. Hence, sequence A082550 consists of the row sums.

%C There is another important interpretation of this array T(n, k) which is related to some of the references for sequence A047996, but because the discussion is too lengthy, we omit the details.

%C (End)

%H Alois P. Heinz, <a href="/A267632/b267632.txt">Rows n = 1..150, flattened</a>

%H Eric Stephen Barnes, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa5/aa516.pdf">The construction of perfect and extreme forms I</a>, Acta Arith., 5 (1959); see pp. 65-66.

%H Michiel Kosters, <a href="https://doi.org/10.1016/j.jcta.2012.10.006">The subset sum problem for finite abelian groups</a>, J. Combin. Theory Ser. A 120 (2013), 527-530.

%H Jiyou Li and Daqing Wan, <a href="https://doi.org/10.1016/j.jcta.2011.07.003 ">Counting subset sums of finite abelian groups</a>, J. Combin. Theory Ser. A 119 (2012), 170-182; see pp. 171-172.

%H K. G. Ramanathan, <a href="https://www.ias.ac.in/article/fulltext/seca/020/01/0062-0069">Some applications of Ramanujan's trigonometrical sum C_m(n)</a>, Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69; see p. 66.

%H R. D. von Sterneck, <a href="https://play.google.com/books/reader?id=V1I-AQAAMAAJ&amp;hl=de&amp;printsec=frontcover&amp;pg=GBS.PA1567">Ein Analogon zur additiven Zahlentheorie</a>, Sitzungsber. Akad. Wiss. Sapientiae Math.-Naturwiss. Kl. 111 (1902), 1567-1601 (Abt. IIa).

%H R. D. von Sterneck, <a href="https://eudml.org/doc/144877">Über ein Analogon zur additiven Zahlentheorie</a>, Jahresbericht der Deutschen Mathematiker-Vereinigung 12 (1903), 110-113.

%F T(2n+1, k) = A037306(2n+1, k) = A047996(2n+1, k).

%F From _Petros Hadjicostas_, Jul 13 2019: (Start)

%F T(n, k) = (1/n) * Sum_{s | gcd(n, k)} (-1)^(k - (k/s)) * phi(s) * binomial(n/s, k/s) for 1 <= k <= n.

%F G.f. for column k >= 1: (x^k/k) * Sum_{s|k} phi(s) * (-1)^(k - (k/s)) / (1 - x^s)^(k/s).

%F Bivariate g.f.: Sum_{n, k >= 1} T(n, k)*x^n*y^k = -x/(1 - x) - Sum_{s >= 1} (phi(s)/s) * log(1 - x^s + (-x*y)^s).

%F (End)

%F Sum_{k=1..n} k * T(n,k) = A309122(n). - _Alois P. Heinz_, Jul 13 2019

%e For n = 5, there is one way to pick one number (5), two ways to pick two numbers (1+4, 2+3), two ways to pick 3 numbers (1+4+5, 2+3+5), one way to pick 4 numbers (1+2+3+4), and one way to pick 5 numbers (1+2+3+4+5) so that their sum is divisible by 5. Therefore, T(5,1) = 1, T(5,2) = 2, T(5,3) = 2, T(5,4) = 1, and T(5,5) = 1.

%e Table for T(n,k) begins as follows:

%e n\k 1 2   3    4    5    6    7    8    9   10

%e 1   1

%e 2   1 0

%e 3   1 1   1

%e 4   1 1   1    0

%e 5   1 2   2    1    1

%e 6   1 2   4    3    1    0

%e 7   1 3   5    5    3    1    1

%e 8   1 3   7    9    7    3    1    0

%e 9   1 4  10   14   14   10    4    1    1

%e 10  1 4  12   22   26   20   12    5    1    0

%e ...

%p A267632 := proc(n,k)

%p     local a,msel,p;

%p     a := 0 ;

%p     for msel in combinat[choose](n,k) do

%p         if modp(add(p,p=msel),n) = 0 then

%p             a := a+1 ;

%p         end if;

%p     end do:

%p     a;

%p end proc: # _R. J. Mathar_, May 15 2016

%p # second Maple program:

%p b:= proc(n, m, s) option remember; expand(`if`(n=0,

%p       `if`(s=0, 1, 0), b(n-1, m, s)+x*b(n-1, m, irem(s+n, m))))

%p     end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2, 0)):

%p seq(T(n), n=1..14);  # _Alois P. Heinz_, Aug 27 2018

%t f[k_, n_] :=  Length[Select[Select[Subsets[Range[n]], Length[#] == k &], IntegerQ[Total[#]/n] &]];MatrixForm[Table[{n, Table[f[k, n], {k, n}]}, {n, 10}]] (* _Dimitri Papadopoulos_, Jan 18 2016 *)

%Y Cf. A004526, A032801, A037306, A047996, A054532, A054533, A054534, A054535, A058212, A063776, A082550 (row sums), A309122.

%K nonn,tabl

%O 1,12

%A _Dimitri Papadopoulos_, Jan 18 2016