OFFSET
0,3
COMMENTS
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.
Equivalently (Cayley), a(n) = number of 2-dimensional partitions of n. E.g., for n = 4 we have:
4 31 3 22 2 211 21 2 2 1111 111 11 11 1
1 2 1 11 1 1 11 1 1
1 1 1
1
Also total number of different species of singularity for conjugate functions with n letters (Sylvester).
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
From Gus Wiseman, Jul 30 2022: (Start)
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:
{{1}} {{1,1}} {{1,1,1}}
{{1},{1}} {{1},{1,1}}
{{1},{2}} {{1},{2,2}}
{{1},{1},{1}}
{{1},{2},{2}}
{{1},{2},{3}}
A000688 counts factorizations into prime powers.
A007716 counts non-isomorphic multiset partitions by weight.
(End)
REFERENCES
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.
V. A. Liskovets, Counting rooted initially connected directed graphs. Vesci Akad. Nauk. BSSR, ser. fiz.-mat., No 5, 23-32 (1969), MR44 #3927.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
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.
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.
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 0..5000 (first 500 terms from T. D. Noe)
Pieter Belmans, Segre symbols, 2016.
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 148
R. Kaneiwa, An asymptotic formula for Cayley's double partition function p(2; n), Tokyo J. Math. 2, 137-158 (1979).
L. Kaylor and D. Offner, Counting matrices over a finite field with all eigenvalues in the field, Involve, a Journal of Mathematics, Vol. 7 (2014), No. 5, 627-645. [DOI]
M. Kozek, F. Luca, P. Pollack, and C. Pomerance, Harmonious pairs, 2014.
M. Kozek, F. Luca, P. Pollack, and C. Pomerance, Harmonious numbers, IJNT, to appear.
XiKun Li, JunLi Li, Bin Liu and CongFeng Qiao, The parametric symmetry and numbers of the entangled class of 2 × M × N system, Science China Physics, Mechanics & Astronomy, Volume 54, Number 8, 1471-1475, DOI: 10.1007/s11433-011-4395-9.
Paul Pollack and Carl Pomerance, Some problems of Erdős on the sum-of-divisors function, For Richard Guy on his 99th birthday: May his sequence be unbounded, Trans. Amer. Math. Soc. Ser. B, Vol. 3 (2016), pp. 1-26; Errata.
N. J. A. Sloane, Transforms.
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.
FORMULA
G.f.: Product_{k >= 1} 1/(1-x^k)^p(k), where p(k) = number of partitions of k = A000041. [Cayley]
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
Logarithmic derivative yields A061259 (equivalent to above formula from Vladeta Jovovic). - Paul D. Hanna, Sep 05 2012
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
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
EXAMPLE
G.f. = 1 + x + 3*x^2 + 6*x^3 + 15*x^4 + 28*x^5 + 66*x^6 + 122*x^7 + ...
a(3) = 6 because we have (111) = (111) = (11)(1) = (1)(1)(1), (12) = (12) = (1)(2), (3) = (3).
The a(4)=14 multiset partitions whose total sum of parts is 4 are:
((4)),
((13)), ((1)(3)),
((22)), ((2)(2)),
((112)), ((1)(12)), ((2)(11)), ((1)(1)(2)),
((1111)), ((1)(111)), ((11)(11)), ((1)(1)(11)), ((1)(1)(1)(1)). - Gus Wiseman, Dec 19 2016
MAPLE
with(combstruct); SetSetSetU := [T, {T=Set(S), S=Set(U, card >= 1), U=Set(Z, card >=1)}, unlabeled];
# second Maple program:
with(numtheory): with(combinat):
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*
numbpart(d), d=divisors(j))*a(n-j), j=1..n)/n)
end:
seq(a(n), n=0..35); # Alois P. Heinz, Dec 19 2016
MATHEMATICA
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. *)
PROG
(Haskell) Following Vladeta Jovovic:
a001970 n = a001970_list !! (n-1)
a001970_list = 1 : f 1 [1] where
f x ys = y : f (x + 1) (y : ys) where
y = sum (zipWith (*) ys a061259_list) `div` x
-- Reinhard Zumkeller, Oct 31 2015
(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 */
(Python)
from sympy.core.cache import cacheit
from sympy import npartitions, divisors
@cacheit
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
[a(n) for n in range(51)] # Indranil Ghosh, Aug 19 2017, after Maple code
# (Sage) # uses[EulerTransform from A166861]
b = BinaryRecurrenceSequence(0, 1, 1)
a = EulerTransform(EulerTransform(b))
print([a(n) for n in range(36)]) # Peter Luschny, Nov 17 2022
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
Additional comments from Valery A. Liskovets
Sylvester references from Barry Cipra, Oct 07 2003
STATUS
approved