# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a074206
Showing 1-1 of 1
%I A074206 #221 Jan 20 2024 09:19:10
%S A074206 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 A074206 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 A074206 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 A074206 Kalmár's [Kalmar's] problem: number of ordered factorizations of n.
%C A074206 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.
%C A074206 Kalmár (1931) seems to be the earliest reference that mentions this sequence (as opposed to A002033). - _N. J. A. Sloane_, May 05 2016
%C A074206 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 A074206 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 A074206 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
%C A074206 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
%C A074206 Inverse Mobius transform of A174725 and also except for the first term, inverse Mobius transform of A174726. - _Mats Granvik_, Mar 28 2010
%C A074206 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 A074206 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
%C A074206 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 A034776 lists the values taken by this sequence. - _Robert G. Wilson v_, Jun 02 2012
%C A074206 From _Gus Wiseman_, Aug 25 2020: (Start)
%C A074206 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:
%C A074206 1 2/1 4/1 6/1 8/1 12/1 30/1
%C A074206 4/2/1 6/2/1 8/2/1 12/2/1 30/2/1
%C A074206 6/3/1 8/4/1 12/3/1 30/3/1
%C A074206 8/4/2/1 12/4/1 30/5/1
%C A074206 12/6/1 30/6/1
%C A074206 12/4/2/1 30/10/1
%C A074206 12/6/2/1 30/15/1
%C A074206 12/6/3/1 30/6/2/1
%C A074206 30/6/3/1
%C A074206 30/10/2/1
%C A074206 30/10/5/1
%C A074206 30/15/3/1
%C A074206 30/15/5/1
%C A074206 (End)
%D A074206 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.
%D A074206 R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.
%D A074206 Kalmár, Laszlo, A "factorisatio numerorum" problemajarol [Hungarian], Matemat. Fizik. Lapok, 38 (1931), 1-15.
%D A074206 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.
%H A074206 N. J. A. Sloane, Table of n, a(n) for n = 0..20000 (first 10000 terms from T. D. Noe)
%H A074206 Peter Brown, Number of Ordered Factorizations.
%H A074206 Peter Brown, Number of Ordered Factorizations.
%H A074206 Benny Chor, Paul Lemke, and Ziv Mador, On the number of ordered factorizations of natural numbers, Discrete Math. 214 (2000), no. 1-3, 123-133. MR1743631 (2000m:11093).
%H A074206 Kristin DeVleming and Nikita Singh, Rational unicuspidal plane curves of low degree, arXiv:2311.15922 [math.AG], 2023. See p. 14.
%H A074206 T. M. A. Fink, Properties of the recursive divisor function and the number of ordered factorizations, arXiv:2307.09140 [math.NT], 2023.
%H A074206 E. Hille, A problem in factorisatio numerorum, Acta Arith., 2 (1936), 134-144.
%H A074206 E. Hille, The inversion problem of Möbius, Duke Math. J., 3 (1937), 549-568.
%H A074206 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.
%H A074206 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.
%H A074206 Laszlo Kalmár, Über die mittlere Anzahl der Produktdarstellungen der Zahlen. (Erste Mitteilung), Acta Litt. ac Scient. Szeged 5 (1931): 95-107.
%H A074206 M. Klazar and F. Luca, On the maximal order of numbers in the "factorisatio numerorum" problem, arXiv:math/0505352 [math.NT], 2005-2006.
%H A074206 Arnold Knopfmacher and Michael Mays, Ordered and Unordered Factorization of Integers, The Mathematica Journal, Volume 10, Issue 1 p. 72.
%H A074206 Arnau Mir, Francesc Rossello, and Lucia Rotger, Sound Colless-like balance indices for multifurcating trees, arXiv:1805.01329 [q-bio.PE], 2018.
%H A074206 Augustine O. Munagi, Labeled factorization of integers, INTEGERS: The Electronic Journal of Combinatorics 16:1 (2009), #R50.
%H A074206 L. A. Newberg and 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.
%H A074206 Ray Tomes, The Maths and Physics of the Harmonics Theory.
%H A074206 Eric Weisstein's World of Mathematics, Perfect Partition.
%H A074206 Eric Weisstein's World of Mathematics, Ordered Factorization.
%H A074206 David W. Wilson, Comments on A074206 and related sequences.
%H A074206 David W. Wilson, Perl program for A074206.
%H A074206 Index entries for "core" sequences
%F A074206 With different offset: a(n) = sum of all a(i) such that i divides n and i < n. - _Clark Kimberling_
%F A074206 a(p^k) = 2^(k-1) if k>0 and p is a prime.
%F A074206 Dirichlet g.f.: 1/(2-zeta(s)). - Herbert S. Wilf, Apr 29 2003
%F A074206 a(n) = A067824(n)/2 for n>1; a(A122408(n)) = A122408(n)/2. - _Reinhard Zumkeller_, Sep 03 2006
%F A074206 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]
%F A074206 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
%F A074206 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
%F A074206 a(n) = A000670(A001221(n)) for squarefree n. In particular a(A002110(n)) = A000670(n). - _Amiram Eldar_, May 13 2019
%F A074206 a(n) = A050369(n)/n, for n>=1. - _Ridouane Oudra_, Aug 31 2019
%F A074206 a(n) = A361665(A181819(n)). - _Pontus von Brömssen_, Mar 25 2023
%F A074206 From _Ridouane Oudra_, Nov 02 2023: (Start)
%F A074206 If p,q are distinct primes, and n,m>0 then we have:
%F A074206 a(p^n*q^m) = Sum_{k=0..min(n,m)} 2^(n+m-k-1)*binomial(n,k)*binomial(m,k);
%F A074206 More generally: let tau[k](n) denote the number of ordered factorizations of n as a product of k terms, also named the k-th Piltz function (see A007425), then we have for n>1:
%F A074206 a(n) = Sum_{j=1..bigomega(n)} Sum_{k=1..j} (-1)^(j-k)*binomial(j,k)*tau[k](n), or
%F A074206 a(n) = Sum_{j=1..bigomega(n)} Sum_{k=0..j-1} (-1)^k*binomial(j,k)*tau[j-k](n). (End)
%e A074206 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 + ...
%e A074206 Number of ordered factorizations of 8 is 4: 8 = 2*4 = 4*2 = 2*2*2.
%p A074206 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: # _James A. Sellers_, Dec 07 2000
%p A074206 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
%t A074206 a[0] = 0; a[1] = 1; a[n_] := a[n] = a /@ Most[Divisors[n]] // Total; a /@ Range[20000] (* _N. J. A. Sloane_, May 04 2016, based on program in A002033 *)
%t A074206 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 *)
%o A074206 (Haskell)
%o A074206 a074206 n | n <= 1 = n
%o A074206 | otherwise = 1 + (sum $ map (a074206 . (div n)) $
%o A074206 tail $ a027751_row n)
%o A074206 -- _Reinhard Zumkeller_, Oct 01 2012
%o A074206 (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
%o A074206 (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 */
%o A074206 (PARI) A074206(n)=if(n>1, sumdiv(n, i, if(i