|
|
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.
|
|
5
|
|
|
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, 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, 30, 15, 5, 1, 1, 1, 5, 19, 42, 66, 76, 66, 43, 19, 5, 1, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,12
|
|
COMMENTS
|
Row less the last element is palindrome for n=odd or n=power of 2 where n is the row number (observation-conjecture).
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).
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.
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.
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).
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.
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.
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).
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).
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.
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.
(End)
|
|
LINKS
|
|
|
FORMULA
|
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.
G.f. for column k >= 1: (x^k/k) * Sum_{s|k} phi(s) * (-1)^(k - (k/s)) / (1 - x^s)^(k/s).
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).
(End)
|
|
EXAMPLE
|
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.
Table for T(n,k) begins as follows:
n\k 1 2 3 4 5 6 7 8 9 10
1 1
2 1 0
3 1 1 1
4 1 1 1 0
5 1 2 2 1 1
6 1 2 4 3 1 0
7 1 3 5 5 3 1 1
8 1 3 7 9 7 3 1 0
9 1 4 10 14 14 10 4 1 1
10 1 4 12 22 26 20 12 5 1 0
...
|
|
MAPLE
|
local a, msel, p;
a := 0 ;
for msel in combinat[choose](n, k) do
if modp(add(p, p=msel), n) = 0 then
a := a+1 ;
end if;
end do:
a;
# second Maple program:
b:= proc(n, m, s) option remember; expand(`if`(n=0,
`if`(s=0, 1, 0), b(n-1, m, s)+x*b(n-1, m, irem(s+n, m))))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2, 0)):
|
|
MATHEMATICA
|
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 *)
|
|
CROSSREFS
|
Cf. A004526, A032801, A037306, A047996, A054532, A054533, A054534, A054535, A058212, A063776, A082550 (row sums), A309122.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|