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

Comments

When p is an odd prime, T(p,k+p) = 2*T(p,k) + (2^k * ((2^p) - 2)/p) for all k >= 0. [Sophie LeBlanc]

When m divides n (with n >= m), T(m,n) = (1/m) Sum_{d | m and d is odd} phi(d) * 2^(n/d). [N. Kitchloo and L. Pachter; D. Rusin]

A068009(C(i+1,2), i) = 2, A068009(C(i,2)+1, i) = A000009(i-1) + 1. [AK, cf. A068049]

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

Example

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

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 *)

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.

Sequence in context: A088443 A117352 A137710 * A140168 A059119 A305333

Adjacent sequences: A068006 A068007 A068008 * A068010 A068011 A068012

Keyword

nonn,nice,tabl

Author

Antti Karttunen, Feb 11 2002

Status

approved