The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A074206 Kalmár's [Kalmar's] problem: number of ordered factorizations of n. 198
 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; text; internal format)
 OFFSET 0,5 COMMENTS a(0)=0, a(1)=1; thereafter a(n) is the number of ordered factorizations of n as a product of integers greater than 1. Kalmár (1931) seems to be the earliest reference that mentions this sequence (as opposed to A002033). - N. J. A. Sloane, May 05 2016 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 a(n) appears to be the number of permutation matrices contributing to the Moebius function. See A008683 for more information. Also 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 constant factor times the starting sequence? - Mats Granvik, Jan 01 2009 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 two distinct primes can be found in table A059576. - Mats Granvik, Sep 06 2009 Inverse Mobius transform of A174725 and also except for the first term, inverse Mobius transform of A174726. - 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 greater 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 A034776 lists the values taken by this sequence. - Robert G. Wilson v, Jun 02 2012 From Gus Wiseman, Aug 25 2020: (Start) Also the number of strict chains of divisors from n to 1. For example, the a(n) chains for n = 1, 2, 4, 6, 8, 12, 30 are:   1  2/1  4/1    6/1    8/1      12/1      30/1           4/2/1  6/2/1  8/2/1    12/2/1    30/2/1                  6/3/1  8/4/1    12/3/1    30/3/1                         8/4/2/1  12/4/1    30/5/1                                  12/6/1    30/6/1                                  12/4/2/1  30/10/1                                  12/6/2/1  30/15/1                                  12/6/3/1  30/6/2/1                                            30/6/3/1                                            30/10/2/1                                            30/10/5/1                                            30/15/3/1                                            30/15/5/1 (End) REFERENCES L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27. R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141. Kalmár, Laszlo, A "factorisatio numerorum" problemajarol [Hungarian], Matemat. Fizik. Lapok, 38 (1931), 1-15. J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124. LINKS T. D. Noe and N. J. A. Sloane, Table of n, a(n) for n = 0..20000, May 05 2016 [First 10000 terms from T. D. Noe] Peter Brown, Number of Ordered Factorizations Peter Brown, Number of Ordered Factorizations Benny Chor, Paul Lemke, Ziv Mador, On the number of ordered factorizations of natural numbers, Discrete Math. 214 (2000), no. 1-3, 123--133. MR1743631 (2000m:11093). E. Hille, A problem in factorisatio numerorum, Acta Arith., 2 (1936), 134-144. E. Hille, The inversion problem of Möbius, Duke Math. J., 3 (1937), 549-568. Shikao Ikehara, On Kalmar's Problem in "Factorisatio Numerorum", Proceedings of the Physico-Mathematical Society of Japan. 3rd Series, Vol. 21 (1939) pp. 208-219. Shikao Ikehara, On Kalmar's Problem in "Factorisatio Numerorum" II, Proceedings of the Physico-Mathematical Society of Japan. 3rd Series, Vol. 23 (1941) pp. 767-774. Laszlo Kalmár, Über die mittlere Anzahl der Produktdarstellungen der Zahlen. (Erste Mitteilung), Acta Litt. ac Scient. Szeged 5 (1931): 95-107. M. Klazar and F. Luca, On the maximal order of numbers in the "factorisatio numerorum" problem, arXiv:math/0505352 [math.NT], 2005-2006. Arnold Knopfmacher & Michael Mays, Ordered and Unordered Factorization of Integers, The Mathematica Journal, Volume 10, Issue 1 p. 72. Arnau Mir, Francesc Rossello, Lucia Rotger, Sound Colless-like balance indices for multifurcating trees, arXiv:1805.01329 [q-bio.PE], 2018. Augustine O. Munagi, Labeled factorization of integers, INTEGERS: The Electronic Journal of Combinatorics 16:1 (2009), #R50. L. A. Newberg & D. Naor, A lower bound on the number of solutions to the probed partial digest problem, Advances in Applied Mathematics, 14(2), 1993, 172-183. doi: 10.1006/aama.1993.1009. 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 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) if k>0 and p is a prime. Dirichlet g.f.: 1/(2-zeta(s)). - Herbert S. 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 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 [corrected by Charles R Greathouse IV, Jun 02 2012] a(0) = 0, a(1) = 1; a(n) = [x^n] Sum_{k=1..n-1} a(k)*x^k/(1 - x^k). - Ilya Gutkovskiy, Dec 11 2017 a(n) = a(A046523(n)); a(A025487(n)) = A050324(n): a(n) depends only on the nonzero exponents in the prime factorization of n, more precisely prime signature of n, cf. A124010 and A320390. - M. F. Hasler, Oct 12 2018 a(n) = A000670(A001221(n)) for squarefree n. In particular a(A002110(n)) = A000670(n). - Amiram Eldar, May 13 2019 a(n) = A050369(n)/n, for n>=1. - Ridouane Oudra, Aug 31 2019 EXAMPLE G.f. = x + x^2 + x^3 + 2*x^4 + x^5 + 3*x^6 + x^7 + 4*x^8 + 2*x^9 + 3*x^10 + ... 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: 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: # James A. Sellers, Dec 07 2000 A074206:= proc(n) option remember; if n > 1 then `+`(op(apply(A074206, numtheory[divisors](n)[1..-2]))) else n fi end: # M. F. Hasler, Oct 12 2018 MATHEMATICA a = 0; a = 1; a[n_] := a[n] = a /@ Most[Divisors[n]] // Total; a /@ Range (* N. J. A. Sloane, May 04 2016, based on program in A002033 *) ccc[n_]:=Switch[n, 0, {}, 1, {{1}}, _, Join@@Table[Prepend[#, n]&/@ccc[d], {d, Most[Divisors[n]]}]]; Table[Length[ccc[n]], {n, 0, 100}] (* Gus Wiseman, Aug 25 2020 *) PROG (Haskell) a074206 n | n <= 1 = n | otherwise = 1 + (sum \$ map (a074206 . (div n)) \$ tail \$ a027751_row n) -- Reinhard Zumkeller, Oct 01 2012 (PARI) A=vector(100); A=1; for(n=2, #A, A[n]=1+sumdiv(n, d, A[d])); A/=2; A=1; concat(0, A) \\ Charles R Greathouse IV, Nov 20 2012 (PARI) {a(n) = if( n<2, n>0, my(A = divisors(n)); sum(k=1, #A-1, a(A[k])))}; /* Michael Somos, Dec 26 2016 */ (PARI) A074206(n)=if(n>1, sumdiv(n, i, if(i 1 else n # Chai Wah Wu, Sep 16 2022 CROSSREFS Apart from initial term, same as A002033. a(A002110) = A000670, row sums of A251683. A173382 (and A025523) gives partial sums. Cf. A008683, A050324, A027751, A001221, A034776, A000670, A050369. A124433 has these as unsigned row sums. A334996 has these as row sums. A001055 counts factorizations. A001222 counts prime factors with multiplicity. A008480 counts ordered prime factorizations. A067824 counts strict chains of divisors starting with n. A122651 counts strict chains of divisors summing to n. A253249 counts strict chains of divisors. Cf. A000005, A124010, A167865, A334997, A337105. Sequence in context: A118314 A349059 A002033 * A173801 A108466 A211110 Adjacent sequences:  A074203 A074204 A074205 * A074207 A074208 A074209 KEYWORD nonn,core,easy,nice,changed AUTHOR N. J. A. Sloane, Apr 29 2003 EXTENSIONS Originally this sequence was merged with A002033, the number of perfect partitions. Herbert S. Wilf suggested that it warrants an entry of its own. STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 26 18:11 EDT 2022. Contains 357002 sequences. (Running on oeis4.)