A304482 Number A(n,k) of n-element subsets of [k*n] whose elements sum to a multiple of n. Square array A(n,k) with n, k >= 0 read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 1, 0, 1, 4, 6, 8, 0, 0, 1, 5, 12, 30, 18, 1, 0, 1, 6, 20, 76, 126, 52, 0, 0, 1, 7, 30, 155, 460, 603, 152, 1, 0, 1, 8, 42, 276, 1220, 3104, 3084, 492, 0, 0, 1, 9, 56, 448, 2670, 10630, 22404, 16614, 1618, 1, 0, 1, 10, 72, 680, 5138, 28506, 98900, 169152, 91998, 5408, 0, 0

Offset

0,8

Comments

When k=1 the only subset of [n] with n elements is [n] which sums to n(n+1)/2 and hence for n>0 and n even A(n,1) is zero and for n odd A(n,1) is one.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)

Marko Riedel et al., Number of n-element subsets divisible by n

Formula

A(n,k) = (-1)^n * (1/n) * Sum_{d|n} C(k*d,d)*(-1)^d*phi(n/d), boundary values A(0,0) = 1, A(n, 0) = 0, A(0, k) = 1.

Example

Square array A(n,k) begins:
  1, 1,   1,     1,      1,      1,       1,        1, ...
  0, 1,   2,     3,      4,      5,       6,        7, ...
  0, 0,   2,     6,     12,     20,      30,       42, ...
  0, 1,   8,    30,     76,    155,     276,      448, ...
  0, 0,  18,   126,    460,   1220,    2670,     5138, ...
  0, 1,  52,   603,   3104,  10630,   28506,    64932, ...
  0, 0, 152,  3084,  22404,  98900,  324516,   874104, ...
  0, 1, 492, 16614, 169152, 960650, 3854052, 12271518, ...

Maple

with(numtheory):
A:= (n, k)-> `if`(n=0, 1, add(binomial(k*d, d)*(-1)^(n+d)*
              phi(n/d), d in divisors(n))/n):
seq(seq(A(n, d-n), n=0..d), d=0..11);

Mathematica

A[n_, k_] : = (-1)^n (1/n) Sum[Binomial[k d, d] (-1)^d EulerPhi[n/d], {d, Divisors[n]}]; A[0, 0] = 1; A[_, 0] = 0; A[0, _] = 1;
Table[A[n-k, k], {n, 0, 11}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Sep 23 2019 *)

Prog

(PARI) T(n, k)=if(n==0, 1, (-1)^n*sumdiv(n, d, binomial(k*d, d) * (-1)^d * eulerphi(n/d))/n)
for(n=0, 7, for(k=0, 7, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Aug 28 2018

Crossrefs

Cf. A000007, A169888, A318431, A318432, A318433, A318557.

Main diagonal gives A318477.

Sequence in context: A342129 A292861 A292133 * A309021 A307968 A338501

Adjacent sequences: A304479 A304480 A304481 * A304483 A304484 A304485

Keyword

nonn,tabl

Author

Marko Riedel, Aug 28 2018

Status

approved