A068009 Square array T(m,n) with m (row) >= 1 and n (column) >= 0 read by antidiagonals: number of subsets of {1,2,3,...n} that sum to 0 mod m (including the empty set, whose sum is 0).
1, 2, 1, 4, 1, 1, 8, 2, 1, 1, 16, 4, 2, 1, 1, 32, 8, 4, 1, 1, 1, 64, 16, 6, 2, 1, 1, 1, 128, 32, 12, 4, 2, 1, 1, 1, 256, 64, 24, 8, 4, 2, 1, 1, 1, 512, 128, 44, 16, 8, 3, 1, 1, 1, 1, 1024, 256, 88, 32, 14, 6, 3, 1, 1, 1, 1, 2048, 512, 176, 64, 26, 12, 5, 2, 1, 1, 1, 1, 4096, 1024, 344, 128, 52, 22, 10, 4, 2, 1, 1, 1, 1
Offset: 0
Examples
Table for T(m,n) (with rows m >= 1 and columns n >= 0) begins as follows: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, ... 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... 1, 1, 2, 4, 6, 12, 24, 44, 88, 176, 344, ... 1, 1, 1, 2, 4, 8, 16, 32, 64, 128, ... 1, 1, 1, 2, 4, 8, 14, 26, 52, ... 1, 1, 1, 2, 3, 6, 12, 22, ... 1, 1, 1, 1, 3, 5, 10, ... 1, 1, 1, 1, 2, 4, ... 1, 1, 1, 1, 2, ... 1, 1, 1, 1, ... 1, 1, 1, ... 1, 1, ... 1, ... ...
Links
- Alois P. Heinz, Antidiagonals n = 0..140, flattened
- Antti Karttunen, Scheme code for computing this table and its rows.
- N. Kitchloo and L. Pachter, An interesting result about subset sums, Nov 27 1993.
- William Kuszmaul, A new approach to enumerating statistics modulo n, arXiv:1402.3839 [math.CO], 2014.
- Lior Pachter, Subset sums, 2015.
- Bill Pet, Sophie LeBlanc, Will Self et al., Subsets of {1,2,3,...,n} (discussion in sci.math).
- R. P. Stanley and M. F. Yoder, A study of Varshamov codes for asymmetric channels, JPL Technical Report 32-1526, Vol. XIV (1972), 117-123.
- Index entries for sequences related to subset sums mod m
Crossrefs
Main diagonal: A000016, superdiagonal: A063776. The first term greater than one occurs on each row m in the position A002024(m) and these are given in A068049.
Row 1: A000079, row 2: A011782, row 3: A068010, row 5: A068011, row 6: A068012, row 7: A068013, row 9: A068030, row 10: A068031, row 11: A068032, row 12: A068033, row 13: A068034, row 14: A068035, row 15: A068036, row 16: A068037, row 17: A068038, row 18: A068039, row 19: A068040, row 20: A068041, row 21: A068042, row 25: A068043, row 32: A068044, row 64: A068045.
Programs
-
Maple
b:= proc(n, m, t) option remember; `if`(n=0, `if`(t=0, 1, 0), b(n-1, m, t)+ b(n-1, m, irem(t+n,m))) end: T:= (m, n)-> b(n, m, 0): seq(seq(T(1+m, d-m), m=0..d), d=0..12); # Alois P. Heinz, Jan 18 2014 -
Mathematica
max = 13; row[m_] := (ClearAll[t]; im = IdentityMatrix[m]; v = Join[ {Last[im]}, Most[im] ]; t[0] = im[[1]]; t[k_] := t[k] = (im + MatrixPower[v, k]) . t[k-1]; Table[ t[k][[1]], {k, 0, max}]); rows = Table[ row[m], {m, 1, max}]; A068009 = Flatten[ Table[ rows[[m-n+1, n]], {m, 1, max, 1}, {n, m, 1, -1}]] (* Jean-François Alcover, Apr 02 2012, after Will Self *) b[n_, m_, t_] := b[n, m, t] = If[n == 0, If[t == 0, 1, 0], b[n-1, m, t]+b[n-1, m, Mod[t+n, m]]]; T[m_, n_] := b[n, m, 0]; Table[Table[T[1+m, d-m], {m, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Jan 13 2015, after Alois P. Heinz *)
Comments