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

Author

Stefano Spezia, May 19 2020

Keywords

• nonn
• tabf
• changed

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)

Examples

			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)
		

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.

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.

Programs

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

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

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.

The above conjecture is true since T(n, m) is also the number of ordered factorizations of n into m factors (see Comments) and A002033(n-1) is the number of ordered factorizations of n. - Stefano Spezia, Aug 21 2025