|
|
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).
|
|
25
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
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
|
|
|
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
...
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
|
A112798 constructs the multiset with each specification number.
A251683 is the version with zeros removed.
A337107 is the restriction to factorial numbers.
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.
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|