A334996 Irregular triangle read by rows: T(n, m) is the number of ways to distribute Omega(n) objects into precisely m distinct boxes, with no box empty (Omega(n) >= m).

0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 1, 0, 1, 1, 0, 1, 2, 0, 1, 0, 1, 4, 3, 0, 1, 0, 1, 2, 0, 1, 2, 0, 1, 3, 3, 1, 0, 1, 0, 1, 4, 3, 0, 1, 0, 1, 4, 3, 0, 1, 2, 0, 1, 2, 0, 1, 0, 1, 6, 9, 4, 0, 1, 1, 0, 1, 2, 0, 1, 2, 1, 0, 1, 4, 3, 0, 1, 0, 1, 6, 6

Offset

1,13

Comments

n is the specification number for a set of Omega(n) objects (see Theorem 3 in Beekman's article).

The specification number of a multiset is also called its Heinz number. - Gus Wiseman, Aug 25 2020

From Gus Wiseman, Aug 25 2020: (Start)

For n > 1, T(n,k) is also the number of ordered factorizations of n into k factors > 1. For example, row n = 24 counts the following ordered factorizations (the first column is empty):

24 3*8 2*2*6 2*2*2*3

4*6 2*3*4 2*2*3*2

6*4 2*4*3 2*3*2*2

8*3 2*6*2 3*2*2*2

12*2 3*2*4

2*12 3*4*2

4*2*3

4*3*2

6*2*2

For n > 1, T(n,k) is also the number of strict length-k chains of divisors from n to 1. For example, row n = 36 counts the following chains (the first column is empty):

36/1 36/2/1 36/4/2/1 36/12/4/2/1

36/3/1 36/6/2/1 36/12/6/2/1

36/4/1 36/6/3/1 36/12/6/3/1

36/6/1 36/9/3/1 36/18/6/2/1

36/9/1 36/12/2/1 36/18/6/3/1

36/12/1 36/12/3/1 36/18/9/3/1

36/18/1 36/12/4/1

36/12/6/1

36/18/2/1

36/18/3/1

36/18/6/1

36/18/9/1

(End)

References

Richard Beekman, An Introduction to Number-Theoretic Combinatorics, Lulu Press 2017.

Links

Stefano Spezia, First 3000 rows of the table, flattened

Richard Beekman, A General Solution of the Ferris Wheel Problem.

Formula

T(n, m) = Sum_{k=0..m-1} (-1)^k*binomial(m,k)*tau_{m-k-1}(n), where tau_s(r) = A334997(r, s) (see Theorem 3, Lemma 1 and Lemma 2 in Beekman's article).

Conjecture: Sum_{m=0..Omega(n)} T(n, m) = A002033(n-1) for n > 1.

Example

The triangle T(n, m) begins
  n\m| 0     1     2     3     4
  ---+--------------------------
   1 | 0
   2 | 0     1
   3 | 0     1
   4 | 0     1     1
   5 | 0     1
   6 | 0     1     2
   7 | 0     1
   8 | 0     1     2     1
   9 | 0     1     1
  10 | 0     1     2
  11 | 0     1
  12 | 0     1     4     3
  13 | 0     1
  14 | 0     1     2
  15 | 0     1     2
  16 | 0     1     3     3     1
  ...
From Gus Wiseman, Aug 25 2020: (Start)
Row n = 36 counts the following distributions of {1,1,2,2} (the first column is empty):
  {1122}  {1}{122}  {1}{1}{22}  {1}{1}{2}{2}
          {11}{22}  {1}{12}{2}  {1}{2}{1}{2}
          {112}{2}  {11}{2}{2}  {1}{2}{2}{1}
          {12}{12}  {1}{2}{12}  {2}{1}{1}{2}
          {122}{1}  {12}{1}{2}  {2}{1}{2}{1}
          {2}{112}  {1}{22}{1}  {2}{2}{1}{1}
          {22}{11}  {12}{2}{1}
                    {2}{1}{12}
                    {2}{11}{2}
                    {2}{12}{1}
                    {2}{2}{11}
                    {22}{1}{1}
(End)

Mathematica

tau[n_, k_]:=If[n==1, 1, Product[Binomial[Extract[Extract[FactorInteger[n], i], 2]+k, k], {i, 1, Length[FactorInteger[n]]}]]; (* A334997 *)
T[n_, m_]:=Sum[(-1)^k*Binomial[m, k]*tau[n, m-k-1], {k, 0, m-1}]; Table[T[n, m], {n, 1, 30}, {m, 0, PrimeOmega[n]}]//Flatten
(* second program *)
chc[n_]:=If[n==1, {{}}, Prepend[Join@@Table[Prepend[#, n]&/@chc[d], {d, DeleteCases[Divisors[n], 1|n]}], {n}]]; (* change {{}} to {} if a(1) = 0 *)
Table[Length[Select[chc[n], Length[#]==k&]], {n, 30}, {k, 0, PrimeOmega[n]}] (* Gus Wiseman, Aug 25 2020 *)

Prog

(PARI) TT(n, k) = if (k==0, 1, sumdiv(n, d, TT(d, k-1))); \\ A334997
T(n, m) = sum(k=0, m-1, (-1)^k*binomial(m, k)*TT(n, m-k-1));
tabf(nn) = {for (n=1, nn, print(vector(bigomega(n)+1, k, T(n, k-1))); ); } \\ Michel Marcus, May 20 2020

Crossrefs

Cf. A000007 (1st column), A000012 (2nd column), A001222 (Omega function), A002033 (row sums shifted left), A007318.

A008480 gives rows ends.

A073093 gives row lengths.

A074206 gives row sums.

A112798 constructs the multiset with each specification number.

A124433 is a signed version.

A251683 is the version with zeros removed.

A334997 is the non-strict version.

A337107 is the restriction to factorial numbers.

A001055 counts factorizations.

A067824 counts strict chains of divisors starting with n.

A122651 counts strict chains of divisors summing to n.

A167865 counts strict chains of divisors > 1 summing to n.

A253249 counts strict chains of divisors.

A337105 counts strict chains of divisors from n! to 1.

Cf. A007425, A008683, A056239, A124010, A167865, A317144, A319001.

Sequence in context: A025884 A352427 A257024 * A124433 A371074 A287104

Adjacent sequences: A334993 A334994 A334995 * A334997 A334998 A334999

Keyword

nonn,tabf

Author

Stefano Spezia, May 19 2020

Status

approved