A098966 Number of (k+1)-tuples of integers modulo n (x_1,...,x_k,s) such that at least one subset of the x_i sums to s mod n. In other words, n^k times the expected number of distinct subset sums mod n of k integers mod n chosen uniformly at random. Read by antidiagonals, i.e., with entries in the order (n,k)=(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...

1, 1, 3, 1, 7, 5, 1, 15, 21, 7, 1, 31, 73, 43, 9, 1, 63, 233, 215, 73, 11, 1, 127, 717, 951, 497, 111, 13, 1, 255, 2173, 3971, 2865, 959, 157, 15, 1, 511, 6545, 16171, 15161, 6863, 1657, 211, 17, 1, 1023, 19665, 65167, 77369, 44391, 14521, 2631, 273, 19

Offset: 1

Author

Andrew Childs (amchilds(AT)caltech.edu) and Wim van Dam (vandam(AT)cs.ucsb.edu), Oct 13 2004

Keywords

• nonn
• tabl

Comments

a(n,k) <= n^(k+1).

Examples

			Table begins
  1,  1,   1,    1,     1, ...
  3,  7,  15,   31,    63, ...
  5, 21,  73,  233,   717, ...
  7, 43, 215,  951,  3971, ...
  9, 73, 497, 2865, 15161, ...
  ...
		

Crossrefs

First column is A005408; second column is A054569; second row is A000225.

Programs

Mathematica

<
				

Formula

a(n, 1) = 2*n - 1;

a(n, 2) = 4*n^2 - 6*n + 3;

a(n, 3) = 8*n^3 - 28*n^2 + 44*n - 23, n odd;

a(n, 3) = 8*n^3 - 28*n^2 + 44*n - 25, n even;

a(1, k) = 1;

a(2, k) = 2^(k+1) - 1;

a(3, k) = 3^(k+1) - 2*k - 2.