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

Comments

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

Links

Table of n, a(n) for n=1..55.

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.

Example

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

Mathematica

<<DiscreteMath`Combinatorica`;
SubsetSums[l_]:=Plus@@#&/@Subsets[l];
NumSumsModN[l_, n_]:=Length[Union[Mod[SubsetSums[l], n]]];
a[1, k_]:=1;
a[n_, k_]:=Plus@@Table[NumSumsModN[IntegerDigits[x, n, k], n], {x, 0, n^k-1}];
Flatten[Table[a[n, j-n], {j, 1, 10}, {n, 1, j-1}]]

Crossrefs

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

Sequence in context: A135858 A193845 A265706 * A021763 A261693 A138257

Adjacent sequences: A098963 A098964 A098965 * A098967 A098968 A098969

Keyword

nonn,tabl

Author

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

Status

approved