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

Author

Gus Wiseman, Oct 30 2021

Keywords

• nonn

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.

Examples

			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)
		

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.

Programs

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}]

Formula

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