|
%I M2576 N1019 #130 Oct 28 2023 11:24:21
%S 1,1,3,6,14,27,58,111,223,424,817,1527,2870,5279,9710,17622,31877,
%T 57100,101887,180406,318106,557453,972796,1688797,2920123,5026410,
%U 8619551,14722230,25057499,42494975,71832114,121024876,203286806,340435588,568496753,946695386
%N Functional determinants; partitions of partitions; Euler transform applied twice to all 1's sequence.
%C a(n) = number of partitions of n, when for each k there are p(k) different copies of part k. E.g., let the parts be 1, 2a, 2b, 3a, 3b, 3c, 4a, 4b, 4c, 4d, 4e, ... Then the a(4) = 14 partitions of 4 are: 4 = 4a = 4b = ... = 4e = 3a+1 = 3b+1 = 3c+1 = 2a+2a = 2a+2b = 2b+2b = 2a+1 = 2b+1 = 1+1+1+1.
%C Equivalently (Cayley), a(n) = number of 2-dimensional partitions of n. E.g., for n = 4 we have:
%C 4 31 3 22 2 211 21 2 2 1111 111 11 11 1
%C 1 2 1 11 1 1 11 1 1
%C 1 1 1
%C 1
%C Also total number of different species of singularity for conjugate functions with n letters (Sylvester).
%C According to [Belmans], this sequence gives "[t]he number of Segre symbols for the intersection of two quadrics in a fixed dimension". - _Eric M. Schmidt_, Sep 02 2017
%C From _Gus Wiseman_, Jul 30 2022: (Start)
%C Also the number of non-isomorphic multiset partitions of weight n with all constant blocks. The strict case is A089259. For example, non-isomorphic representatives of the a(1) = 1 through a(3) = 6 multiset partitions are:
%C {{1}} {{1,1}} {{1,1,1}}
%C {{1},{1}} {{1},{1,1}}
%C {{1},{2}} {{1},{2,2}}
%C {{1},{1},{1}}
%C {{1},{2},{2}}
%C {{1},{2},{3}}
%C A000688 counts factorizations into prime powers.
%C A007716 counts non-isomorphic multiset partitions by weight.
%C A279784 counts twice-partitions of type PPR, factorizations A295935.
%C Constant partitions are ranked by prime-powers: A000961, A023894, A054685, A246655, A355743.
%C (End)
%D A. Cayley, Recherches sur les matrices dont les termes sont des fonctions linéaires d'une seule indéterminée, J. Reine angew. Math., 50 (1855), 313-317; Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 2, p. 219.
%D V. A. Liskovets, Counting rooted initially connected directed graphs. Vesci Akad. Nauk. BSSR, ser. fiz.-mat., No 5, 23-32 (1969), MR44 #3927.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D J. J. Sylvester, An Enumeration of the Contacts of Lines and Surfaces of the Second Order, Phil. Mag. 1 (1851), 119-140. Reprinted in Collected Papers, Vol. 1. See p. 239, where one finds a(n)-2, but with errors.
%D J. J. Sylvester, Note on the 'Enumeration of the Contacts of Lines and Surfaces of the Second Order', Phil. Mag., Vol. VII (1854), pp. 331-334. Reprinted in Collected Papers, Vol. 2, pp. 30-33.
%H Reinhard Zumkeller, <a href="/A001970/b001970.txt">Table of n, a(n) for n = 0..5000</a> (first 500 terms from T. D. Noe)
%H Pieter Belmans, <a href="http://pbelmans.ncag.info/notes/segre.pdf">Segre symbols</a>, 2016.
%H P. J. Cameron, <a href="http://dx.doi.org/10.1016/0012-365X(89)90081-2">Some sequences of integers</a>, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=148">Encyclopedia of Combinatorial Structures 148</a>
%H R. Kaneiwa, <a href="http://projecteuclid.org/euclid.tjm/1270473566">An asymptotic formula for Cayley's double partition function p(2; n)</a>, Tokyo J. Math. 2, 137-158 (1979).
%H L. Kaylor and D. Offner, <a href="https://projecteuclid.org/euclid.involve/1513733722">Counting matrices over a finite field with all eigenvalues in the field</a>, Involve, a Journal of Mathematics, Vol. 7 (2014), No. 5, 627-645. [<a href="http://dx.doi.org/10.2140/involve.2014.7.627">DOI</a>]
%H M. Kozek, F. Luca, P. Pollack, and C. Pomerance, <a href="https://math.dartmouth.edu/~carlp/harmonious4.pdf">Harmonious pairs</a>, 2014.
%H M. Kozek, F. Luca, P. Pollack, and C. Pomerance, <a href="https://math.dartmouth.edu/~carlp/KozekLucaPollackPomeranceIJNTv4.pdf">Harmonious numbers</a>, IJNT, to appear.
%H XiKun Li, JunLi Li, Bin Liu and CongFeng Qiao, <a href="http://dx.doi.org/10.1007/s11433-011-4395-9">The parametric symmetry and numbers of the entangled class of 2 × M × N system</a>, Science China Physics, Mechanics & Astronomy, Volume 54, Number 8, 1471-1475, DOI: 10.1007/s11433-011-4395-9.
%H Paul Pollack and Carl Pomerance, <a href="https://doi.org/10.1090/btran/10">Some problems of Erdős on the sum-of-divisors function</a>, For Richard Guy on his 99th birthday: May his sequence be unbounded, Trans. Amer. Math. Soc. Ser. B, Vol. 3 (2016), pp. 1-26; <a href="http://pollack.uga.edu/reversal-errata.pdf">Errata</a>.
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>.
%H N. J. A. Sloane and Thomas Wieder, <a href="http://arXiv.org/abs/math.CO/0307064">The Number of Hierarchical Orderings</a>, Order 21 (2004), 83-89.
%H J. J. Sylvester, The collected mathematical papers of James Joseph Sylvester, <a href="http://www.hti.umich.edu/cgi/t/text/text-idx?sid=b88432273f115fb346725f1a42422e19;c=umhistmath;idno=AAS8085.0002.001">vol. 2</a>, <a href="http://www.hti.umich.edu/cgi/t/text/text-idx?sid=b88432273f115fb346725f1a42422e19;c=umhistmath;idno=AAS8085.0003.001">vol. 3</a>, <a href="http://www.hti.umich.edu/cgi/t/text/text-idx?sid=b88432273f115fb346725f1a42422e19;c=umhistmath;idno=AAS8085.0004.001">vol. 4</a>.
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F G.f.: Product_{k >= 1} 1/(1-x^k)^p(k), where p(k) = number of partitions of k = A000041. [Cayley]
%F a(n) = (1/n)*Sum_{k = 1..n} a(n-k)*b(k), n > 1, a(0) = 1, b(k) = Sum_{d|k} d*numbpart(d), where numbpart(d) = number of partitions of d, cf. A061259. - _Vladeta Jovovic_, Apr 21 2001
%F Logarithmic derivative yields A061259 (equivalent to above formula from Vladeta Jovovic). - _Paul D. Hanna_, Sep 05 2012
%F a(n) = Sum_{k=1..A000041(n)} A001055(A215366(n,k)) = number of factorizations of Heinz numbers of integer partitions of n. - _Gus Wiseman_, Dec 19 2016
%F a(n) = |{m>=1 : n = Sum_{k=1..A001222(m)} A056239(A112798(m,k)+1)}| = number of normalized twice-prime-factored multiset partitions (see A275024) whose total sum of parts is n. - _Gus Wiseman_, Dec 19 2016
%e G.f. = 1 + x + 3*x^2 + 6*x^3 + 15*x^4 + 28*x^5 + 66*x^6 + 122*x^7 + ...
%e a(3) = 6 because we have (111) = (111) = (11)(1) = (1)(1)(1), (12) = (12) = (1)(2), (3) = (3).
%e The a(4)=14 multiset partitions whose total sum of parts is 4 are:
%e ((4)),
%e ((13)), ((1)(3)),
%e ((22)), ((2)(2)),
%e ((112)), ((1)(12)), ((2)(11)), ((1)(1)(2)),
%e ((1111)), ((1)(111)), ((11)(11)), ((1)(1)(11)), ((1)(1)(1)(1)). - _Gus Wiseman_, Dec 19 2016
%p with(combstruct); SetSetSetU := [T, {T=Set(S), S=Set(U,card >= 1), U=Set(Z,card >=1)},unlabeled];
%p # second Maple program:
%p with(numtheory): with(combinat):
%p a:= proc(n) option remember; `if`(n=0, 1, add(add(d*
%p numbpart(d), d=divisors(j))*a(n-j), j=1..n)/n)
%p end:
%p seq(a(n), n=0..35); # _Alois P. Heinz_, Dec 19 2016
%t m = 32; f[x_] = Product[1/(1-x^k)^PartitionsP[k], {k, 1, m}]; CoefficientList[ Series[f[x], {x, 0, m-1}], x] (* _Jean-François Alcover_, Jul 19 2011, after g.f. *)
%o (Haskell) Following Vladeta Jovovic:
%o a001970 n = a001970_list !! (n-1)
%o a001970_list = 1 : f 1 [1] where
%o f x ys = y : f (x + 1) (y : ys) where
%o y = sum (zipWith (*) ys a061259_list) `div` x
%o -- _Reinhard Zumkeller_, Oct 31 2015
%o (PARI) {a(n) = if( n<0, 0, polcoeff( 1 / prod(k=1, n, 1 - numbpart(k) * x^k + x * O(x^n)), n))}; /* _Michael Somos_, Dec 20 2016 */
%o (Python)
%o from sympy.core.cache import cacheit
%o from sympy import npartitions, divisors
%o @cacheit
%o def a(n): return 1 if n == 0 else sum([sum([d*npartitions(d) for d in divisors(j)])*a(n - j) for j in range(1, n + 1)]) / n
%o [a(n) for n in range(51)] # _Indranil Ghosh_, Aug 19 2017, after Maple code
%o # (Sage) # uses[EulerTransform from A166861]
%o b = BinaryRecurrenceSequence(0, 1, 1)
%o a = EulerTransform(EulerTransform(b))
%o print([a(n) for n in range(36)]) # _Peter Luschny_, Nov 17 2022
%Y Related to A001383 via generating function.
%Y The multiplicative version (factorizations) is A050336.
%Y The ordered version (sequences of partitions) is A055887.
%Y Row-sums of A061260.
%Y Main diagonal of A055885.
%Y We have A271619(n) <= a(n) <= A063834(n).
%Y Column k=3 of A290353.
%Y The strict case is A316980.
%Y Cf. A000041, A061259, A006171, A061255, A061256, A061257, A089292, A000219.
%Y Cf. A089300.
%Y Cf. A001055, A072233, A112798, A275024.
%K nonn,nice,easy
%O 0,3
%A _N. J. A. Sloane_
%E Additional comments from _Valery A. Liskovets_
%E Sylvester references from _Barry Cipra_, Oct 07 2003
|
