|
Search: id:A098966
|
|
|
| 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, 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
(list; table; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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: A010603 A100584 A135858 this_sequence A021763 A138257 A071043
Adjacent sequences: A098963 A098964 A098965 this_sequence 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
|
|
|
Search completed in 0.002 seconds
|
