A174725 a(n) = (A002033(n-1) + A008683(n))/2.

1, 0, 0, 1, 0, 2, 0, 2, 1, 2, 0, 4, 0, 2, 2, 4, 0, 4, 0, 4, 2, 2, 0, 10, 1, 2, 2, 4, 0, 6, 0, 8, 2, 2, 2, 13, 0, 2, 2, 10, 0, 6, 0, 4, 4, 2, 0, 24, 1, 4, 2, 4, 0, 10, 2, 10, 2, 2, 0, 22, 0, 2, 4, 16, 2, 6, 0, 4, 2, 6, 0, 38, 0, 2, 4, 4, 2

Offset

1,6

Comments

From Mats Granvik, May 25 2017: (Start)

A002033(n-1) = a(n) + A174726(n).

A008683(n) = a(n) - A174726(n).

Let m = size of matrix a matrix T, and let T be defined as follows:

T(n,k) = if m = 1 then 1 else if mod(n, k) = 0 then if and(n = k, n = m) then 0 else 1 else if and(n = 1, k = m) then 1 else 0

a(n) is then the number of permutation matrices with a positive contribution in the determinant of matrix T. The determinant of T is equal to the Möbius function A008683, see Mathematica program below for how to compute the determinant.

A174726 is the number of permutation matrices with a negative contribution in the determinant of matrix T.

(End)

From Gus Wiseman, Jan 04 2021: (Start)

Also the number of ordered factorizations of n into an even number of factors > 1. The non-ordered case is A339846. For example, the a(n) factorizations for n = 12, 24, 30, 32, 36 are:

(2*6) (3*8) (5*6) (4*8) (4*9)

(3*4) (4*6) (6*5) (8*4) (6*6)

(4*3) (6*4) (10*3) (16*2) (9*4)

(6*2) (8*3) (15*2) (2*16) (12*3)

(12*2) (2*15) (2*2*2*4) (18*2)

(2*12) (3*10) (2*2*4*2) (2*18)

(2*2*2*3) (2*4*2*2) (3*12)

(2*2*3*2) (4*2*2*2) (2*2*3*3)

(2*3*2*2) (2*3*2*3)

(3*2*2*2) (2*3*3*2)

(3*2*2*3)

(3*2*3*2)

(3*3*2*2)

(End)

Links

Mats Granvik, Table of n, a(n) for n = 1..10000

Formula

a(n) = (Mobius transform of a(n)) + (Mobius transform of A174726). - Mats Granvik, Apr 04 2010

From Mats Granvik, May 25 2017: (Start)

This sequence is the Moebius transform of A002033.

a(n) = (A002033(n-1) + A008683(n))/2.

(End)

G.f. A(x) satisfies: A(x) = x + Sum_{i>=2} Sum_{j>=2} A(x^(i*j)). - Ilya Gutkovskiy, May 11 2019

Mathematica

(* From Mats Granvik, May 25 2017: (Start) *)
Clear[t, nn]; nn = 77; t[1, 1] = 1; t[n_, k_] := t[n, k] = If[k == 1, Sum[t[n, k + i], {i, 1, n - 1}], If[Mod[n, k] == 0, t[n/k, 1], 0], 0]; Monitor[Table[Sum[If[Mod[n, k] == 0, MoebiusMu[k]*t[n/k, 1], 0], {k, 1, 77}], {n, 1, nn}], n]
(* The Möbius function as a determinant *) Table[Det[Table[Table[If[m == 1, 1, If[Mod[n, k] == 0, If[And[n == k, n == m], 0, 1], If[And[n == 1, k == m], 1, 0]]], {k, 1, m}], {n, 1, m}]], {m, 1, 42}]
(* (End) *)
ordfacs[n_]:=If[n<=1, {{}}, Join@@Table[(Prepend[#1, d]&)/@ordfacs[n/d], {d, Rest[Divisors[n]]}]];
Table[Length[Select[ordfacs[n], EvenQ@*Length]], {n, 100}] (* Gus Wiseman, Jan 04 2021 *)

Crossrefs

Cf. A008683, A051731.

The odd version is A174726.

The unordered version is A339846.

A001055 counts factorizations, with strict case A045778.

A058696 counts partitions of even numbers, ranked by A300061.

A074206 counts ordered factorizations, with strict case A254578.

A251683 counts ordered factorizations by product and length.

Other cases of even length:

- A024430 counts set partitions of even length.

- A027187 counts partitions of even length.

- A034008 counts compositions of even length.

- A052841 counts ordered set partitions of even length.

- A067661 counts strict partitions of even length.

- A332305 counts strict compositions of even length

Cf. A002033, A027193, A028260, A050320, A058695, A236913, A316439, A320655, A320656, A339890.

Sequence in context: A147588 A307409 A070824 * A348537 A071459 A319164

Adjacent sequences: A174722 A174723 A174724 * A174726 A174727 A174728

Keyword

nonn

Author

Mats Granvik, Mar 28 2010

Status

approved