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

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

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.

A279784 counts twice-partitions of type PPR, factorizations A295935.

Constant partitions are ranked by prime-powers: 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), 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.

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/(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

Related to A001383 via generating function.

The multiplicative version (factorizations) is A050336.

The ordered version (sequences of partitions) is A055887.

Row-sums of A061260.

Main diagonal of A055885.

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: A365073 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