A096753 -id:A096753 - cp's OEIS frontend

A096751 Square table, read by antidiagonals, where T(n,k) equals the number of n-dimensional partitions of k.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 1, 4, 6, 5, 1, 1, 1, 5, 10, 13, 7, 1, 1, 1, 6, 15, 26, 24, 11, 1, 1, 1, 7, 21, 45, 59, 48, 15, 1, 1, 1, 8, 28, 71, 120, 140, 86, 22, 1, 1, 1, 9, 36, 105, 216, 326, 307, 160, 30, 1, 1, 1, 10, 45, 148, 357, 657, 835, 684, 282, 42, 1

Offset: 0

Paul D. Hanna, Jul 07 2004

Main diagonal forms A096752. Antidiagonal sums form A096753. Row with index n lists the row sums of the n-th matrix power of triangle A096651, for n>=0.

			n-th row lists n-dimensional partitions; table begins with n=0:
  [1,1,1,1,1,1,1,1,1,1,1,1,...],
  [1,1,2,3,5,7,11,15,22,30,42,56,...],
  [1,1,3,6,13,24,48,86,160,282,500,859,...],
  [1,1,4,10,26,59,140,307,684,1464,3122,...],
  [1,1,5,15,45,120,326,835,2145,5345,...],
  [1,1,6,21,71,216,657,1907,5507,15522,...],
  [1,1,7,28,105,357,1197,3857,12300,38430,...],
  [1,1,8,36,148,554,2024,7134,24796,84625,...],
  [1,1,9,45,201,819,3231,12321,46209,170370,...],
  [1,1,10,55,265,1165,4927,20155,80920,...],...
Array begins:
      k=0:  k=1:  k=2:  k=3:  k=4:  k=5:  k=6:  k=7:  k=8:
  n=0:  1     1     1     1     1     1     1     1     1
  n=1:  1     1     2     3     5     7    11    15    22
  n=2:  1     1     3     6    13    24    48    86   160
  n=3:  1     1     4    10    26    59   140   307   684
  n=4:  1     1     5    15    45   120   326   835  2145
  n=5:  1     1     6    21    71   216   657  1907  5507
  n=6:  1     1     7    28   105   357  1197  3857 12300
  n=7:  1     1     8    36   148   554  2024  7134 24796
  n=8:  1     1     9    45   201   819  3231 12321 46209
  n=9:  1     1    10    55   265  1165  4927 20155 80920

G. E. Andrews, The Theory of Partitions, Add.-Wes. 1976, pp. 189-197.

Pontus von Brömssen, Table of n, a(n) for n = 0..275 (first 23 antidiagonals)
A. O. L. Atkin, P. Bratley, I. G. McDonald and J. K. S. McKay, Some computations for m-dimensional partitions, Proc. Camb. Phil. Soc., 63 (1967), 1097-1100. [Annotated scanned copy]

Rows: A000012 (n=0), A000041 (n=1), A000219 (n=2), A000293 (n=3), A000334 (n=4), A000390 (n=5), A000416 (n=6), A000427 (n=7), A179855 (n=8).
Columns: A008778 (k=4), A008779 (k=5), A042984 (k=6).
Cf. A096651, A096752, A096753.
Cf. A096806.
Cf. A042984.
Cf. A144150, A213427, A290353, A323718, A323719.

trans[x_]:=If[x=={},{},Transpose[x]];
levptns[n_,k_]:=If[k==1,IntegerPartitions[n],Join@@Table[Select[Tuples[levptns[#,k-1]&/@y],And@@(GreaterEqual@@@trans[Flatten/@(PadRight[#,ConstantArray[n,k-1]]&/@#)])&],{y,IntegerPartitions[n]}]];
Table[If[sum==k,1,Length[levptns[k,sum-k]]],{sum,0,10},{k,0,sum}] (* Gus Wiseman, Jan 27 2019 *)

T(0, n)=T(n, 0)=T(n, 1)=1 for n>=0.

Inverse binomial transforms of the columns is given by triangle A096806.

A182080 a(n) is the maximal depth of an indecomposable exact cover of an n-set.

Original entry on oeis.org

1, 2, 3, 5, 9, 18, 38

Offset: 1

N. J. A. Sloane, Apr 10 2012

Let U = {1,2,...,n} and let P = collection of all subsets of U.
A block system on U is a function f: P -> {0,1,2,...}; f(S) is the number of times a subset S occurs as a block in the system.
The sum of two block systems f,g is defined in the obvious way, and z denotes the zero block system.
f is an exact cover of depth d if for each u in U,
Sum_{ S in P: u in S} f(S) = d.
An exact cover is decomposable if f = g+h where g, h are nonzero exact covers.
Then a(n) is the maximal depth of an indecomposable exact cover of U.
The values of a(6), a(7), a(8) shown here were only conjectural, but that may have changed since Graver's paper is now nearly 40 years old.
Graver gives many references, most of which seem never to have been published (see scanned pages below).

			Example showing an indecomposable f of depth d = 2 for n = 3, illustrating a(3) = 2:
.S. | 1 2 3 | f(S)
------------------
..- | 0 0 0 | 0
..1 | 1 0 0 | 0
..2 | 0 1 0 | 0
..3 | 0 0 1 | 0
.12 | 1 1 0 | 1
.13 | 1 0 1 | 1
.23 | 0 1 1 | 1
123 | 1 1 1 | 0

J. E. Graver, A survey of the maximum depth problem for indecomposable exact covers. In "Infinite and finite sets" (Colloq., Keszthely, 1973; dedicated to P. Erdos on his 60th birthday), Vol. II, pp. 731-743. Colloq. Math. Soc. Janos Bolyai, Vol. 10, North-Holland, Amsterdam, 1975. MR0401516 (53 #5343). See scans of selected pages below.

Noga Alon and Van H. Vu, Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs, Journal of Combinatorial Theory, Series A, Volume 79, Issue 1, July 1997, Pages 133-160.
Zoltán Füredi, Indecomposable regular graphs and hypergraphs, Discrete Mathematics, Volume 101, Issues 1-3, 29 May 1992 (DOI: 10.1016/0012-365X(92)90590-C), pp. 59-64.
J. E. Graver, Pages 731-734 and 742-743
J. H. van Lint and H. O. Pollak, An "offense-last-move" game against perfect local defense at targets of arbitrary values, Unpublished AT&T Bell Labs Memorandum, 1968.
J. H. van Lint and H. O. Pollak, An Asymmetric Contest for Properties of Arbitrary Value, Philips Res. Repts. 30 (1975), 40-55, (Special issue in honour of C. J. Bouwkamp).

Cf. A096753 (has the same beginning, but is unlikely to be the same sequence).

Alon and Vu give asymptotics.

cp's OEIS Frontend

A096751 Square table, read by antidiagonals, where T(n,k) equals the number of n-dimensional partitions of k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula