|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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;
|
|
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|