login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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).

From Petros Hadjicostas, Jul 13 2019: (Start)

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

Alois P. Heinz, Rows n = 1..150, flattened

Eric Stephen Barnes, The construction of perfect and extreme forms I, Acta Arith., 5 (1959); see pp. 65-66.

Michiel Kosters, The subset sum problem for finite abelian groups, J. Combin. Theory Ser. A 120 (2013), 527-530.

Jiyou Li and Daqing Wan, Counting subset sums of finite abelian groups, J. Combin. Theory Ser. A 119 (2012), 170-182; see pp. 171-172.

K. G. Ramanathan, Some applications of Ramanujan's trigonometrical sum C_m(n), Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69; see p. 66.

R. D. von Sterneck, Ein Analogon zur additiven Zahlentheorie, Sitzungsber. Akad. Wiss. Sapientiae Math.-Naturwiss. Kl. 111 (1902), 1567-1601 (Abt. IIa).

R. D. von Sterneck, Über ein Analogon zur additiven Zahlentheorie, Jahresbericht der Deutschen Mathematiker-Vereinigung 12 (1903), 110-113.

FORMULA

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

From Petros Hadjicostas, Jul 13 2019: (Start)

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)

Sum_{k=1..n} k * T(n,k) = A309122(n). - Alois P. Heinz, Jul 13 2019

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

A267632 := proc(n, k)

    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;

end proc: # R. J. Mathar, May 15 2016

# 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)):

seq(T(n), n=1..14);  # Alois P. Heinz, Aug 27 2018

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.

Sequence in context: A114730 A031282 A085685 * A112465 A112468 A207194

Adjacent sequences:  A267629 A267630 A267631 * A267633 A267634 A267635

KEYWORD

nonn,tabl

AUTHOR

Dimitri Papadopoulos, Jan 18 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 00:14 EDT 2020. Contains 337378 sequences. (Running on oeis4.)