A251683 Irregular triangular array: T(n,k) is the number of ordered factorizations of n with exactly k factors, n >= 1, 1 <= k <= A086436(n).

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 2, 1, 2, 1, 3, 3, 1, 1, 1, 4, 3, 1, 1, 4, 3, 1, 2, 1, 2, 1, 1, 6, 9, 4, 1, 1, 1, 2, 1, 2, 1, 1, 4, 3, 1, 1, 6, 6, 1, 1, 4, 6, 4, 1, 1, 2, 1, 2, 1, 2, 1, 7, 12, 6, 1, 1, 2, 1, 2, 1, 6, 9, 4

Offset

1,8

Comments

Row sums = A074206.

Row lengths give A086436.

T(n,2) = A070824(n).

T(n,3) = A200221(n).

Sum_{k>=1} k*T(n,k) = A254577.

For all n > 1, Sum_{k=1..A086436(n)} (-1)^k*T(n,k) = A008683(n). - Geoffrey Critzer, May 25 2018

From Gus Wiseman, Aug 21 2020: (Start)

Also the number of strict length k + 1 chains of divisors from n to 1. For example, row n = 24 counts the following chains:

24/1 24/2/1 24/4/2/1 24/8/4/2/1

24/3/1 24/6/2/1 24/12/4/2/1

24/4/1 24/6/3/1 24/12/6/2/1

24/6/1 24/8/2/1 24/12/6/3/1

24/8/1 24/8/4/1

24/12/1 24/12/2/1

24/12/3/1

24/12/4/1

24/12/6/1

(End)

Links

Alois P. Heinz, Rows n = 1..4000, flattened

Jeffery Kline, On the eigenstructure of sparse matrices related to the prime number theorem, Linear Algebra and its Applications (2020) Vol. 584, 409-430.

Arnold Knopfmacher and Michael Mays, Ordered and Unordered Factorizations of Integers, The Mathematica Journal, Vol 10 (1).

Eric Weisstein's World of Mathematics, Ordered Factorization

Formula

Dirichlet g.f.: 1/(1 - y*(zeta(x)-1)).

Example

Triangle T(n,k) begins:
  1;
  1;
  1;
  1, 1;
  1;
  1, 2;
  1;
  1, 2, 1;
  1, 1;
  1, 2;
  1;
  1, 4, 3;
  1;
  1, 2;
  1, 2;
  ...
There are 8 ordered factorizations of the integer 12: 12, 6*2, 4*3, 3*4, 2*6, 3*2*2, 2*3*2, 2*2*3.  So T(12,1)=1, T(12,2)=4, and T(12,3)=3.

Maple

with(numtheory):
b:= proc(n) option remember; expand(x*(1+
      add(b(n/d), d=divisors(n) minus {1, n})))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(b(n)):
seq(T(n), n=1..100);  # Alois P. Heinz, Dec 07 2014

Mathematica

f[1] = {{}};
f[n_] := f[n] =
  Level[Table[
    Map[Prepend[#, d] &, f[n/d]], {d, Rest[Divisors[n]]}], {2}];
Prepend[Map[Select[#, # > 0 &] &,
  Drop[Transpose[
    Table[Map[Count[#, k] &,
      Map[Length, Table[f[n], {n, 1, 40}], {2}]], {k, 1, 10}]],
   1]], {1}] // Grid
(* Second program: *)
b[n_] := b[n] = x(1+Sum[b[n/d], {d, Divisors[n]~Complement~{1, n}}]);
T[n_] := CoefficientList[b[n]/x, x];
Array[T, 100] // Flatten (* Jean-François Alcover, Nov 17 2020, after Alois P. Heinz *)

Crossrefs

Cf. A008683, A070824, A200221, A254577.

A008480 gives rows ends.

A086436 gives row lengths.

A124433 is the same except for signs and zeros.

A334996 is the same except for zeros.

A337107 is the restriction to factorial numbers (but with zeros).

A000005 counts divisors.

A001055 counts factorizations.

A001222 counts prime factors with multiplicity.

A074206 counts strict chains of divisors from n to 1.

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 nonempty chains of divisors of n.

A337071 counts strict chains of divisors starting with n!.

A337256 counts strict chains of divisors of n.

Cf. A001221, A002033, A124010, A167865, A337070, A337105.

Sequence in context: A359141 A366785 A322480 * A354579 A306261 A329722

Adjacent sequences: A251680 A251681 A251682 * A251684 A251685 A251686

Keyword

nonn,tabf

Author

Geoffrey Critzer, Dec 06 2014

Status

approved