|
%I #37 Jan 07 2024 14:15:02
%S 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,
%T 126,52,0,0,1,7,30,155,460,603,152,1,0,1,8,42,276,1220,3104,3084,492,
%U 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
%N 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.
%C 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.
%H Andrew Howroyd, <a href="/A304482/b304482.txt">Table of n, a(n) for n = 0..1325</a> (first 51 antidiagonals)
%H Marko Riedel et al., <a href="https://math.stackexchange.com/questions/2894653/">Number of n-element subsets divisible by n</a>
%F 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.
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 0, 1, 2, 3, 4, 5, 6, 7, ...
%e 0, 0, 2, 6, 12, 20, 30, 42, ...
%e 0, 1, 8, 30, 76, 155, 276, 448, ...
%e 0, 0, 18, 126, 460, 1220, 2670, 5138, ...
%e 0, 1, 52, 603, 3104, 10630, 28506, 64932, ...
%e 0, 0, 152, 3084, 22404, 98900, 324516, 874104, ...
%e 0, 1, 492, 16614, 169152, 960650, 3854052, 12271518, ...
%p with(numtheory):
%p A:= (n, k)-> `if`(n=0, 1, add(binomial(k*d, d)*(-1)^(n+d)*
%p phi(n/d), d in divisors(n))/n):
%p seq(seq(A(n, d-n), n=0..d), d=0..11);
%t 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;
%t Table[A[n-k, k], {n, 0, 11}, {k, n, 0, -1}] // Flatten (* _Jean-François Alcover_, Sep 23 2019 *)
%o (PARI) T(n,k)=if(n==0, 1, (-1)^n*sumdiv(n, d, binomial(k*d, d) * (-1)^d * eulerphi(n/d))/n)
%o for(n=0, 7, for(k=0, 7, print1(T(n, k), ", ")); print); \\ _Andrew Howroyd_, Aug 28 2018
%Y Cf. A000007, A169888, A318431, A318432, A318433, A318557.
%Y Main diagonal gives A318477.
%K nonn,tabl
%O 0,8
%A _Marko Riedel_, Aug 28 2018
|
