

A001970


Functional determinants; partitions of partitions; Euler transform applied twice to all 1's sequence.
(Formerly M2576 N1019)


199



1, 1, 3, 6, 14, 27, 58, 111, 223, 424, 817, 1527, 2870, 5279, 9710, 17622, 31877, 57100, 101887, 180406, 318106, 557453, 972796, 1688797, 2920123, 5026410, 8619551, 14722230, 25057499, 42494975, 71832114, 121024876, 203286806, 340435588, 568496753, 946695386
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 2dimensional 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 nonisomorphic multiset partitions of weight n with all constant blocks. The strict case is A089259. For example, nonisomorphic 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 nonisomorphic multiset partitions by weight.
A279784 counts twicepartitions of type PPR, factorizations A295935.
Constant partitions are ranked by primepowers: A000961, A023894, A054685, A246655, A355743.
(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), 313317; Collected Mathematical Papers. Vols. 113, Cambridge Univ. Press, London, 18891897, Vol. 2, p. 219.
V. A. Liskovets, Counting rooted initially connected directed graphs. Vesci Akad. Nauk. BSSR, ser. fiz.mat., No 5, 2332 (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), 119140. 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. 331334. Reprinted in Collected Papers, Vol. 2, pp. 3033.


LINKS

T. D. Noe and 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), 89102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89102.
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, 137158 (1979).
L. Kaylor, D. Offner, Counting matrices over a finite field with all eigenvalues in the field, Involve, a Journal of Mathematics, Vol. 7 (2014), No. 5, 627645. [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, 14711475, DOI: 10.1007/s1143301143959.
P. Pollack and C. Pomerance, Some problems of Erdos on the sumofdivisors function, For Richard Guy on his 99th birthday: May his sequence be unbounded, 2015, to appear.
N. J. A. Sloane, Transforms
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 8389.
J. J. Sylvester, The collected mathematical papers of James Joseph Sylvester, vol. 2, vol. 3, vol. 4.
Index entries for sequences related to rooted trees


FORMULA

G.f.: Product_{k >= 1} 1/(1x^k)^p(k), where p(k) = number of partitions of k = A000041. [Cayley]
a(n) = (1/n)*Sum_{k = 1..n} a(nk)*b(k), n > 1, a(0) = 1, b(k) = Sum_{dk} 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 twiceprimefactored 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(nj), j=1..n)/n)
end:
seq(a(n), n=0..35); # Alois P. Heinz, Dec 19 2016


MATHEMATICA

m = 32; f[x_] = Product[1/(1x^k)^PartitionsP[k], {k, 1, m}]; CoefficientList[ Series[f[x], {x, 0, m1}], x] (* JeanFrançois Alcover, Jul 19 2011, after g.f. *)


PROG

(Haskell) Following Vladeta Jovovic:
a001970 n = a001970_list !! (n1)
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

Related to A001383 via generating function.
The multiplicative version (factorizations) is A050336.
The ordered version (sequences of partitions) is A055887.
Rowsums of A061260.
We have A271619(n) <= a(n) <= A063834(n).
Column k=3 of A290353.
The strict case is A316980.
Cf. A000041, A061259, A006171, A061255, A061256, A061257, A089292, A000219.
Cf. A089300.
Cf. A001055, A072233, A112798, A275024.
Sequence in context: A279474 A282756 A030012 * A006951 A224840 A356804
Adjacent sequences: A001967 A001968 A001969 * A001971 A001972 A001973


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane


EXTENSIONS

Additional comments from Valery A. Liskovets
Sylvester references from Barry Cipra, Oct 07 2003


STATUS

approved



