login
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.
9
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)
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
Main diagonal gives A318477.
Sequence in context: A342129 A292861 A292133 * A309021 A307968 A338501
KEYWORD
nonn,tabl
AUTHOR
Marko Riedel, Aug 28 2018
STATUS
approved