|
%I
%S 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,
%T 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,
%U 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
%N Number of ordered factorizations of n.
%C 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
%C 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
%C a(n) appears to be the number of permutation matrices contributing to the Moebius function. See A008683 for more information. (cont.)
%C 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? - Mats Granvik, Jan 01 2009
%C 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]
%C Inverse Mobius transform of A174725 and also except for the first term, inverse Mobius transform of A174726. [From Mats Granvik, Mar 28 2010]
%C 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
%C 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
%C If n is squarefree, then a(n) = A000670(A001221(n)) = A000670(A001222(n)). -Vladimir Shevelev and Franklin T. Adams-Watters, Aug 05 2011
%C A074206 take on the values of A034776. _Robert G. Wilson v_, Jun 02 2012
%D Chor, Benny; Lemke, Paul; Mador, Ziv. On the number of ordered factorizations of natural numbers. Discrete Math. 214 (2000), no. 1-3, 123--133. MR1743631 (2000m:11093)
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.
%D E. Hille, A problem in factorisatio numerorum, Acta Arith., 2 (1936), 134-144.
%D R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.
%D 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
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.
%H T. D. Noe, <a href="/A074206/b074206.txt">Table of n, a(n) for n = 0..10000</a>
%H Peter Brown, <a href="http://www.mountainman.com.au/harmonics.htm">Number of Ordered Factorizations</a>
%H Peter Brown, <a href="http://www.mountainman.com.au/harmonics_01.htm">Number of Ordered Factorizations</a>
%H M. Klazar and F. Luca, <a href="http://arXiv.org/abs/math.NT/0505352">On the maximal order of numbers in the "factorisatio numerorum" problem</a>
%H Ray Tomes, <a href="http://ray.tomes.biz/maths.html">The Maths and Physics of the Harmonics Theory</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerfectPartition.html">Perfect Partition</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/OrderedFactorization.html">Ordered Factorization</a>
%H David W. Wilson, <a href="/A074206/a074206.txt">Comments on A074206 and related sequences</a>
%H David W. Wilson, <a href="/A074206/a074206.pl.txt">Perl program for A074206</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F With different offset: a(n) = sum of all a(i) such that i divides n and i < n (Clark Kimberling).
%F a(p^k)=2^(k-1).
%F Dirichlet g.f.: 1/(2-zeta(s)). - Herb Wilf, Apr 29, 2003
%F a(n) = A067824(n)/2 for n>1; a(A122408(n)) = A122408(n)/2. - _Reinhard Zumkeller_, Sep 03 2006
%F If p,q,r,... are distinct 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
%e Number of ordered factorizations of 8 is 4: 8 = 2*4 = 4*2 = 2*2*2.
%p 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
%t aa[0] = 0; a[1] = 2; a[n_] := a[n] = Block[{d = Most@ Divisors@ n}, Sum[ a[i], {i, d}]]; Array[a, 97, 0]/2 (* From J. F. Alcover, Apr 28 2011 and modified by Robert G. Wilson v, Jun 2 2012 *)
%o (Haskell)
%o a074206 n | n <= 1 = n
%o | otherwise = 1 + (sum $ map (a074206 . (div n)) $
%o tail $ a027751_row n)
%o -- _Reinhard Zumkeller_, Oct 01 2012
%o (PARI) A=vector(100);A[1]=1; for(n=2,#A,A[n]=1+sumdiv(n,d,A[d])); A/=2; A[1]=1; concat(0,A) \\ _Charles R Greathouse IV_, Nov 20 2012
%Y Apart from initial term, same as A002033. Cf. A001055, A050324. a(A002110)=A000670, cf. A001221, A001222, A034776.
%Y Cf. A027751.
%K nonn,core,easy,nice
%O 0,5
%A _N. J. A. Sloane_, Apr 29, 2003
%E Originally this sequence was merged with A002033, the number of perfect partitions. Herb Wilf suggested that it warrants an entry of its own.
%E Word distinct removed from my comment - _Mats Granvik_, Oct 07 2010
%E Added word distinct to my comment - _Mats Granvik_, Oct 20 2010
%E Formula corrected. - _Charles R Greathouse IV_, Jun 02 2012
|
