|
| |
|
|
A074206
|
|
Number of ordered factorizations of n.
|
|
29
| |
|
|
0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3, 8, 1, 8, 1, 8, 3, 3, 1, 20, 2, 3, 4, 8, 1, 13, 1, 16, 3, 3, 3, 26, 1, 3, 3, 20, 1, 13, 1, 8, 8, 3, 1, 48, 2, 8, 3, 8, 1, 20, 3, 20, 3, 3, 1, 44, 1, 3, 8, 32, 3, 13, 1, 8, 3, 13, 1, 76, 1, 3, 8, 8, 3, 13, 1, 48, 8, 3, 1, 44, 3, 3, 3, 20, 1, 44, 3, 8, 3, 3, 3, 112
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,5
|
|
|
COMMENTS
| a(n) is the permanent of the n-1 X n-1 matrix A with (i,j) entry = 1 if j|i+1 and = 0 otherwise. This is because ordered factorizations correspond to nonzero elementary products in the permanent. For example, with n=6, 3*2 -> 1,3,6 [partial products] -> 6,3,1 [reverse list] -> (6,3)(3,1) [partition into pairs with offset 1] -> (5,3)(2,1) [decrement first entry] -> (5,3)(2,1)(1,2)(3,4)(4,5) [append pairs (i,i+1) to get a permutation] -> elementary product A(1,2)A(2,1)A(3,4)A(4,5)A(5,3). - David Callan, Oct 19 2005
This sequence is important in describing the amount of energy in all wave structures in the Universe according to harmonics theory. - Ray Tomes (ray(AT)tomes.biz), Jul 22 2007
Contribution from Mats Granvik, Jan 01 2009: (Start)
a(n) appears to be the number of permutation matrices contributing to the Moebius function. See A008683 for more information.
a(n) appears to be the Moebius transform of A067824. Furthermore it appears that except for the first term a(n)=A067824(n)*(1/2). Are there other sequences such that when the Moebius transform is applied, the new sequence is also a factor times the starting sequence? (End)
Numbers divisible by n distinct primes appear to have ordered factorization values that can be found in an n-dimensional summatory Pascal triangle. For example, the ordered factorization values for numbers divisible by 2 distinct primes can be found in table A059576. [From Mats Granvik, Sep 06 2009]
Inverse Mobius transform of A174725 and also except for the first term, inverse Mobius transform of A174726. [From Mats Granvik, Mar 28 2010]
a(n) is a lower bound on the worst-case number of solutions to the probed partial digest problem for n fragments of DNA; see the Newberg & Naor reference, below. - Lee A. Newberg, Aug 02 2011
All integers more than 1 are perfect numbers over this sequence (for definition of A-perfect numbers, see comment to A175522).-Vladimir Shevelev, Aug 03 2011
If n is squarefree, then a(n) = A000670(A001221(n)) = A000670(A001222(n)). -Vladimir Shevelev and Franklin T. Adams-Watters, Aug 05 2011
|
|
|
REFERENCES
| L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.
R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.
L. A. Newberg & D. Naor, 1993, A lower bound on the number of solutions to the probed partial digest problem. Advances in Applied Mathematics, 14(2), 172-183. doi: 10.1006/aama.1993.1009
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n = 0..10000
Peter Brown, Title?
Peter Brown, Title?
M. Klazar and F. Luca, On the maximal order of numbers in the "factorisatio numerorum" problem
Ray Tomes, The Maths and Physics of the Harmonics Theory
Eric Weisstein's World of Mathematics, Perfect Partition
Eric Weisstein's World of Mathematics, Ordered Factorization
David W. Wilson, Comments on A074206 and related sequences
David W. Wilson, Perl program for A074206
Index entries for "core" sequences
|
|
|
FORMULA
| With different offset: a(n) = sum of all a(i) such that i divides n and i < n (Clark Kimberling).
a(p^k)=2^(k-1).
Dirichlet g.f.: 1/(2-zeta(s)). - Herb Wilf, Apr 29, 2003
a(n) = A067824(n)/2 for n>1; a(A122408(n)) = A122408(n)/2. - Reinhard Zumkeller, Sep 03 2006
If p,q,r,... are primes, then a(p*q)=3, a(p^2*q)=8, a(p*q*r)=13, a(p^3*q)=20, etc. -Vladimir Shevelev, Aug 03 2011
|
|
|
EXAMPLE
| Number of ordered factorizations of 8 is 4: 8 = 2*4 = 4*2 = 2*2*2.
|
|
|
MAPLE
| a := array(1..150): for k from 1 to 150 do a[k] := 0 od: a[1] := 1: for j from 2 to 150 do for m from 1 to j-1 do if j mod m = 0 then a[j] := a[j]+a[m] fi: od: od: for k from 1 to 150 do printf(`%d, `, a[k]) od: # from James A. Sellers Dec 07 2000
|
|
|
MATHEMATICA
| a[0] = 0; a[n_] := a[n] = 1 + Sum[If[Mod[n, d] == 0, a[d], 0], {d, 1, n - 1}]; Table[If[n == 1, 2, a[n]], {n, 0, 96}]/2 (* From J. F. Alcover, Apr 28 2011 *)
|
|
|
CROSSREFS
| Apart from initial term, same as A002033. Cf. A001055, A050324. a(A002110)=A000670, cf. A001221, A001222.
Sequence in context: A097283 A118314 A002033 * A173801 A108466 A200780
Adjacent sequences: A074203 A074204 A074205 * A074207 A074208 A074209
|
|
|
KEYWORD
| nonn,core,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Apr 29, 2003
|
|
|
EXTENSIONS
| Originally this sequence was merged with A002033, the number of perfect partitions. Herb Wilf suggested that it warrants an entry of its own.
Word distinct removed from my comment - Mats Granvik (mats.granvik(AT)abo.fi), Oct 07 2010
Added word distinct to my comment - Mats Granvik (mats.granvik(AT)abo.fi), Oct 20 2010
|
| |
|
|
