A348383 Number of factorizations of n that are either separable (have an anti-run permutation) or are a twin (x*x).

1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 2, 2, 1, 6, 2, 2, 2, 4, 1, 5, 1, 5, 2, 2, 2, 9, 1, 2, 2, 6, 1, 5, 1, 4, 4, 2, 1, 10, 2, 4, 2, 4, 1, 6, 2, 6, 2, 2, 1, 11, 1, 2, 4, 7, 2, 5, 1, 4, 2, 5, 1, 15, 1, 2, 4, 4, 2, 5, 1, 10, 4, 2, 1, 11, 2

Offset

1,4

Comments

First differs from A347050 at a(216) = 28, A347050(216) = 27.

A factorization of n is a weakly increasing sequence of positive integers > 1 with product n.

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts. Alternatively, a multiset is separable if its greatest multiplicity is greater than the sum of the remaining multiplicities plus one.

Links

Table of n, a(n) for n=1..85.

Formula

a(n > 1) = A335434(n) + A010052(n), where A010052(n) = 1 if n is a perfect square, otherwise 0.

Example

The a(216) = 28 factorizations:
  (2*2*2*3*3*3)  (2*2*2*3*9)  (2*2*6*9)   (3*8*9)   (3*72)   (216)
                 (2*2*3*3*6)  (2*3*4*9)   (4*6*9)   (4*54)
                 (2*3*3*3*4)  (2*3*6*6)   (2*2*54)  (6*36)
                              (3*3*4*6)   (2*3*36)  (8*27)
                              (2*2*3*18)  (2*4*27)  (9*24)
                              (2*3*3*12)  (2*6*18)  (12*18)
                                          (2*9*12)  (2*108)
                                          (3*3*24)
                                          (3*4*18)
                                          (3*6*12)
The a(270) = 20 factorizations:
  (2*3*3*3*5)  (2*3*5*9)   (5*6*9)   (3*90)   (270)
               (3*3*5*6)   (2*3*45)  (5*54)
               (2*3*3*15)  (2*5*27)  (6*45)
                           (2*9*15)  (9*30)
                           (3*3*30)  (10*27)
                           (3*5*18)  (15*18)
                           (3*6*15)  (2*135)
                           (3*9*10)

Mathematica

facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
sepQ[m_]:=Select[Permutations[m], !MatchQ[#, {___, x_, x_, ___}]&]!={};
Table[Length[Select[facs[n], MatchQ[#, {x_, x_}]||sepQ[#]&]], {n, 100}]

Crossrefs

Positions of 1's are 1 and A000040.

Not requiring separability gives A010052 for n > 1.

Positions of 2's are A323644.

Partitions of this type are counted by A325534(n) + A000035(n + 1).

Partitions of this type are ranked by A335433 \/ A001248.

Partitions not of this type are counted by A325535(n) - A000035(n + 1).

Partitions not of this type are ranked by A345193 = A335448 \ A001248.

Not allowing twins gives A335434, complement A333487,

The case with an alternating permutation is A347050, no twins A348379.

The case without an alternating permutation is A347706, no twins A348380.

The complement is counted by A348381.

A001055 counts factorizations, strict A045778, ordered A074206.

A001250 counts alternating permutations.

A003242 counts anti-run compositions, ranked by A333489.

A025047 counts alternating or wiggly compositions.

A335452 counts anti-run permutations of prime indices, complement A336107.

A339846 counts even-length factorizations.

A339890 counts odd-length factorizations.

Cf. A119620, A138364, A336103, A344654, A344740, A347437, A347438, A347456, A347458, A348382.

Sequence in context: A345936 A370814 A347050 * A369713 A295635 A115751

Adjacent sequences: A348380 A348381 A348382 * A348384 A348385 A348386

Keyword

nonn

Author

Gus Wiseman, Oct 30 2021

Status

approved