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

Author

Marko Riedel, Aug 28 2018

Keywords

• nonn
• tabl

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.

Examples

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

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

Crossrefs

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

Main diagonal gives A318477.

Programs

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 *)

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

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.