login
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),...
0
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).
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: A193845 A372938 A265706 * A021763 A261693 A138257
KEYWORD
nonn,tabl
AUTHOR
Andrew Childs (amchilds(AT)caltech.edu) and Wim van Dam (vandam(AT)cs.ucsb.edu), Oct 13 2004
STATUS
approved