cp's OEIS Frontend

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

%I A267632 #61 Aug 20 2019 12:45:07
%S A267632 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 A267632 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 A267632 30,15,5,1,1,1,5,19,42,66,76,66,43,19,5,1,0
%N A267632 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 A267632 Row less the last element is palindrome for n=odd or n=power of 2 where n is the row number (observation-conjecture).
%C A267632 From _Petros Hadjicostas_, Jul 13 2019: (Start)
%C A267632 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 A267632 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 A267632 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 A267632 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 A267632 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 A267632 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 A267632 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 A267632 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 A267632 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 A267632 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 A267632 (End)
%H A267632 Alois P. Heinz, <a href="/A267632/b267632.txt">Rows n = 1..150, flattened</a>
%H A267632 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 A267632 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 A267632 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 A267632 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 A267632 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 A267632 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 A267632 T(2n+1, k) = A037306(2n+1, k) = A047996(2n+1, k).
%F A267632 From _Petros Hadjicostas_, Jul 13 2019: (Start)
%F A267632 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 A267632 G.f. for column k >= 1: (x^k/k) * Sum_{s|k} phi(s) * (-1)^(k - (k/s)) / (1 - x^s)^(k/s).
%F A267632 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 A267632 (End)
%F A267632 Sum_{k=1..n} k * T(n,k) = A309122(n). - _Alois P. Heinz_, Jul 13 2019
%e A267632 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 A267632 Table for T(n,k) begins as follows:
%e A267632 n\k 1 2   3    4    5    6    7    8    9   10
%e A267632 1   1
%e A267632 2   1 0
%e A267632 3   1 1   1
%e A267632 4   1 1   1    0
%e A267632 5   1 2   2    1    1
%e A267632 6   1 2   4    3    1    0
%e A267632 7   1 3   5    5    3    1    1
%e A267632 8   1 3   7    9    7    3    1    0
%e A267632 9   1 4  10   14   14   10    4    1    1
%e A267632 10  1 4  12   22   26   20   12    5    1    0
%e A267632 ...
%p A267632 A267632 := proc(n,k)
%p A267632     local a,msel,p;
%p A267632     a := 0 ;
%p A267632     for msel in combinat[choose](n,k) do
%p A267632         if modp(add(p,p=msel),n) = 0 then
%p A267632             a := a+1 ;
%p A267632         end if;
%p A267632     end do:
%p A267632     a;
%p A267632 end proc: # _R. J. Mathar_, May 15 2016
%p A267632 # second Maple program:
%p A267632 b:= proc(n, m, s) option remember; expand(`if`(n=0,
%p A267632       `if`(s=0, 1, 0), b(n-1, m, s)+x*b(n-1, m, irem(s+n, m))))
%p A267632     end:
%p A267632 T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2, 0)):
%p A267632 seq(T(n), n=1..14);  # _Alois P. Heinz_, Aug 27 2018
%t A267632 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 A267632 Cf. A004526, A032801, A037306, A047996, A054532, A054533, A054534, A054535, A058212, A063776, A082550 (row sums), A309122.
%K A267632 nonn,tabl
%O A267632 1,12
%A A267632 _Dimitri Papadopoulos_, Jan 18 2016