A339742 -id:A339742 - cp's OEIS frontend

A000085 Number of self-inverse permutations on n letters, also known as involutions; number of standard Young tableaux with n cells.

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, 211799312, 997313824, 4809701440, 23758664096, 119952692896, 618884638912, 3257843882624, 17492190577600, 95680443760576, 532985208200576, 3020676745975552

Offset: 0

N. J. A. Sloane and J. H. Conway

a(n) is also the number of n X n symmetric permutation matrices.
a(n) is also the number of matchings (Hosoya index) in the complete graph K(n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 25 2001
a(n) is also the number of independent vertex sets and vertex covers in the n-triangular graph. - Eric W. Weisstein, May 22 2017
Equivalently, this is the number of graphs on n labeled nodes with degrees at most 1. - Don Knuth, Mar 31 2008
a(n) is also the sum of the degrees of the irreducible representations of the symmetric group S_n. - Avi Peretz (njk(AT)netvision.net.il), Apr 01 2001
a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2. - Karol A. Penson, Apr 22 2003
Number of tableaux on the edges of the star graph of order n, S_n (sometimes T_n). - Roberto E. Martinez II, Jan 09 2002
The Hankel transform of this sequence is A000178 (superfactorials). Sequence is also binomial transform of the sequence 1, 0, 1, 0, 3, 0, 15, 0, 105, 0, 945, ... (A001147 with interpolated zeros). - Philippe Deléham, Jun 10 2005
Row sums of the exponential Riordan array (e^(x^2/2),x). - Paul Barry, Jan 12 2006
a(n) is the number of nonnegative lattice paths of upsteps U = (1,1) and downsteps D = (1,-1) that start at the origin and end on the vertical line x = n in which each downstep (if any) is marked with an integer between 1 and the height of its initial vertex above the x-axis. For example, with the required integer immediately preceding each downstep, a(3) = 4 counts UUU, UU1D, UU2D, U1DU. - David Callan, Mar 07 2006
Equals row sums of triangle A152736 starting with offset 1. - Gary W. Adamson, Dec 12 2008
Proof of the recurrence relation a(n) = a(n-1) + (n-1)*a(n-2): number of involutions of [n] containing n as a fixed point is a(n-1); number of involutions of [n] containing n in some cycle (j, n), where 1 <= j <= n-1, is (n-1) times the number of involutions of [n] containing the cycle (n-1 n) = (n-1)*a(n-2). - Emeric Deutsch, Jun 08 2009
Number of ballot sequences (or lattice permutations) of length n. A ballot sequence B is a string such that, for all prefixes P of B, h(i) >= h(j) for i < j, where h(x) is the number of times x appears in P. For example, the ballot sequences of length 4 are 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1231, and 1234. The string 1221 does not appear in the list because in the 3-prefix 122 there are two 2's but only one 1. (Cf. p. 176 of Bruce E. Sagan: "The Symmetric Group"). - Joerg Arndt, Jun 28 2009
Number of standard Young tableaux of size n; the ballot sequences are obtained as a length-n vector v where v_k is the (number of the) row in which the number r occurs in the tableaux. - Joerg Arndt, Jul 29 2012
Number of factorial numbers of length n-1 with no adjacent nonzero digits. For example the 10 such numbers (in rising factorial radix) of length 3 are 000, 001, 002, 003, 010, 020, 100, 101, 102, and 103. - Joerg Arndt, Nov 11 2012
Also called restricted Stirling numbers of the second kind (see Mezo). - N. J. A. Sloane, Nov 27 2013
a(n) is the number of permutations of [n] that avoid the consecutive patterns 123 and 132. Proof. Write a self-inverse permutation in standard cycle form: smallest entry in each cycle in first position, first entries decreasing. For example, (6,7)(3,4)(2)(1,5) is in standard cycle form. Then erase parentheses. This is a bijection to the permutations that avoid consecutive 123 and 132 patterns. - David Callan, Aug 27 2014
Getu (1991) says these numbers are also known as "telephone numbers". - N. J. A. Sloane, Nov 23 2015
a(n) is the number of elements x in the symmetric group S_n such that x^2 = e where e is the identity. - Jianing Song, Aug 22 2018 [Edited on Jul 24 2025]
a(n) is the number of congruence orbits of upper-triangular n X n matrices on skew-symmetric matrices, or the number of Borel orbits in largest sect of the type DIII symmetric space SO_{2n}(C)/GL_n(C). Involutions can also be thought of as fixed-point-free partial involutions. See [Bingham and Ugurlu] link. - Aram Bingham, Feb 08 2020
From Thomas Anton, Apr 20 2020: (Start)
Apparently a(n) = b*c where b is odd iff a(n+b) (when a(n) is defined) is divisible by b.
Apparently a(n) = 2^(f(n mod 4)+floor(n/4))*q where f:{0,1,2,3}->{0,1,2} is given by f(0),f(1)=0, f(2)=1 and f(3)=2 and q is odd. (End)
From Iosif Pinelis, Mar 12 2021: (Start)
a(n) is the n-th initial moment of the normal distribution with mean 1 and variance 1. This follows because the moment generating function of that distribution is the e.g.f. of the sequence of the a(n)'s.
The recurrence a(n) = a(n-1) + (n-1)*a(n-2) also follows, by writing E(Z+1)^n=EZ(Z+1)^(n-1)+E(Z+1)^(n-1), where Z is a standard normal random variable, and then taking the first of the latter two integrals by parts. (End)

			Sequence starts 1, 1, 2, 4, 10, ... because possibilities are {}, {A}, {AB, BA}, {ABC, ACB, BAC, CBA}, {ABCD, ABDC, ACBD, ADCB, BACD, BADC, CBAD, CDAB, DBCA, DCBA}. - _Henry Bottomley_, Jan 16 2001
G.f. = 1 + x + 2*x^2 + 4*x^4 + 10*x^5 + 26*x^6 + 76*x^7 + 232*x^8 + 764*x^9 + ...
From _Gus Wiseman_, Jan 08 2021: (Start)
The a(4) = 10 standard Young tableaux:
  1 2 3 4
.
  1 2   1 3   1 2 3   1 2 4   1 3 4
  3 4   2 4   4       3       2
.
  1 2   1 3   1 4
  3     2     2
  4     4     3
.
  1
  2
  3
  4
The a(0) = 1 through a(4) = 10 set partitions into singletons or pairs:
  {}  {{1}}  {{1,2}}    {{1},{2,3}}    {{1,2},{3,4}}
             {{1},{2}}  {{1,2},{3}}    {{1,3},{2,4}}
                        {{1,3},{2}}    {{1,4},{2,3}}
                        {{1},{2},{3}}  {{1},{2},{3,4}}
                                       {{1},{2,3},{4}}
                                       {{1,2},{3},{4}}
                                       {{1},{2,4},{3}}
                                       {{1,3},{2},{4}}
                                       {{1,4},{2},{3}}
                                       {{1},{2},{3},{4}}
(End)

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 32, 911.
S. Chowla, The asymptotic behavior of solutions of difference equations, in Proceedings of the International Congress of Mathematicians (Cambridge, MA, 1950), Vol. I, 377, Amer. Math. Soc., Providence, RI, 1952.
W. Fulton, Young Tableaux, Cambridge, 1997.
D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 5.1.4, p. 65.
L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181.
T. Muir, A Treatise on the Theory of Determinants. Dover, NY, 1960, p. 6.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 86.
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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.10.

Alois P. Heinz, Table of n, a(n) for n = 0..800 (first 101 terms from T. D. Noe)
Ahmad Zainy Al-Yasry, Short Steps in Noncommutative Geometry, arXiv:1901.03640 [math.OA], 2019.
T. Amdeberhan and V. H. Moll, Involutions and their progenies, 2014.
David Applegate and N. J. A. Sloane, The Gift Exchange Problem arXiv:0907.0513 [math.CO], 2009.
Joerg Arndt, Generating Random Permutations, PhD thesis, Australian National University, Canberra, Australia, (2010).
Joerg Arndt, Matters Computational (The Fxtbook), pp. 279-280.
C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
D. Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 1-21.
C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
E. A. Bender and S. G. Williamson, Foundations of Combinatorics with Applications (see Chap. 2, Example 2.9, pp. 47-48, including Theorem 2.2, a derived formula for a(n)). [From _Rick L. Shepherd_, Sep 02 2009]
S. Bilotta, E. Pergola, R. Pinzani, and S. Rinaldi, Recurrence relations versus succession rules, arXiv preprint arXiv:1301.2967 [cs.DM], 2013. - From _N. J. A. Sloane_, Feb 12 2013
S. Bilotta, E. Pergola, R. Pinzani, and S. Rinaldi, Recurrence Relations, Succession Rules, and the Positivity Problem, in Language and Automata Theory and Applications, 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings, Pages 499-510, Lecture Notes Comp. Sci. Vol. 8977.
Aram Bingham and Özlem Uğurlu, Sects, rooks, pyramids, partitions and paths for type DIII clans, arXiv:1907.08875 [math.CO], 2019.
Anders Björner and Richard P. Stanley, A combinatorial miscellany, 2010.
P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp, Combinatorial field theories via boson normal ordering, arXiv:quant-ph/0405103, 2004-2006. The title of this paper in the arXiv was later changed to "Some useful combinatorial formulas for bosonic operators"
P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp, Some useful combinatorial formulas for bosonic operators, J. Math. Phys. 46, 052110 (2005) (6 pages).
Tobias Boege and Thomas Kahle, Construction Methods for Gaussoids, arXiv:1902.11260 [math.CO], 2019.
D. Bundala, M. Codish, L. Cruz-Filipe et al., Optimal-Depth Sorting Networks, arXiv preprint arXiv:1412.5302 [cs.DS], 2014.
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
D. Castellanos, A generalization of Binet's formula and some of its consequences, Fib. Quart., 27 (1989), 424-438.
C.-O. Chow, Counting involutory, unimodal and alternating signed permutations, Discr. Math. 306 (2006), 2222-2228.
S. Chowla, and I.N. Hernstein, W.K. Moore, On recursions connected with symmetric groups. I, Canadian Journal of Mathematics, 3 (1951), 328-334.
M. Codish, L. Cruz-Filipe and P. Schneider-Kamp, The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes, arXiv preprint arXiv:1404.0948 [cs.DS], 2014.
Tom Copeland, Infinitesimal Generators, the Pascal Pyramid, and the Witt and Virasoro Algebras
Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908 [math.CO], 2012.
I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, et al., Enumeration of idempotents in diagram semigroups and algebras, arXiv preprint arXiv:1408.2021 [math.GR], 2014.
I. Dolinka, J. East, and R. D. Gray, Motzkin monoids and partial Brauer monoids, arXiv preprint arXiv:1512.02279 [math.GR], 2015-2016.
R. Donaghey, Binomial self-inverse sequences and tangent coefficients, J. Combin. Theory, Series A, 21 (1976), 155-163.
S. Dulucq and J.-G. Penaud, Cordes, arbres et permutations, Discrete Math. 117 (1993), no. 1-3, 89-105.
Shalosh B. Ekhad, Manuel Kauers, and Doron Zeilberger, The O(1/n^85) Asymptotic expansion of OEIS sequence A85, arxiv preprint arXiv:2410.16334 [math.CO], October 2024.
Shalosh B. Ekhad and Doron Zeilberger, Computational and Theoretical Challenges on Counting Solid Standard Young Tableaux
Shalosh B. Ekhad and Doron Zeilberger, Computational and Theoretical Challenges on Counting Solid Standard Young Tableaux, [Local copy, pdf file only, no active links]
Shalosh B. Ekhad and Doron Zeilberger, Computational and Theoretical Challenges on Counting Solid Standard Young Tableaux, arXiv preprint arXiv:1202.6229 [math.CO], 2012. [This is a different document from the one with the same title on Doron Zeilberger's web site]
Shalosh B. Ekhad, Manuel Kauers, and Doron Zeilberger, The O(1/n^85) Asymptotic expansion of OEIS sequence A85, arXiv:2410.16334 [math.CO], 2024.
FindStat - Combinatorial Statistic Finder, Standard Young tableaux
Amy M. Fu and Frank Z. K. Li, Joint Distributions of Permutation Statistics and the Parabolic Cylinder Functions, arXiv:1809.07465 [math.CO], 2018.
Mohammad Ganjtabesh, Armin Morabbi and Jean-Marc Steyaert, Enumerating the number of RNA structures
S. Garrabrant and I. Pak, Counting with irrational tiles, arXiv:1407.8222 [math.CO], 2014.
S. Getu, Evaluating determinants via generating functions, Mathematics Magazine 64 (1991), 45-53.
J. Gilder, Rooks inviolate revisited II, Math. Gaz., 70 (1986), 44-45.
A. M. Goyt, Avoidance of partitions of a 3-element set, arXiv:math/0603481 [math.CO], 2006.
Greenhill, Catherine; McKay, Brendan D., Counting loopy graphs with given degree, Linear Algebra Appl. 436, No. 4, 901-926 (2012)
H. Gupta, Enumeration of symmetric matrices, Duke Math. J., 35 (1968), vol 3, 653-659
H. Gupta, Enumeration of symmetric matrices (annotated scanned copy)
C. Gutschwager, Reduced Kronecker products which are multiplicity free or contain only a few components, Eur. J. Combinat. 31 (2010) 1996-2005 doi:10.1016/j.ejc.2010.05.008, Remark 2.13.
T. Halverson and M. Reeks, Gelfand Models for Diagram Algebras, arXiv preprint arXiv:1302.6150 [math.RT], 2013.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
A. Horzela, P. Blasiak, G. E. H. Duchamp, K. A. Penson and A. I. Solomon, A product formula and combinatorial field theory, arXiv:quant-ph/0409152, 2004.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 17
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 22
András Kaszanyitzky, The GraftalLace Cellular Automaton, arXiv:1805.11532 [nlin.CG], 2018.
Manuel Kauers, Doron Zeilberger, Counting Standard Young Tableaux With Restricted Runs, arXiv:2006.10205 [math.CO], 2020.
Dongsu Kim and Jang Soo Kim, A combinatorial approach to the power of 2 in the number of involutions, J. Comb. Theory Ser. A 117 (8) (2010): 1082-1094
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 227.
P. L. Krapivsky and J. M. Luck, Coverage fluctuations in theater models, arXiv:1902.04365 [cond-mat.stat-mech], 2019.
M. B. Kutler and C. R. Vinroot, On q-Analogs of Recursions for the Number of Involutions and Prime Order Elements in Symmetric Groups, JIS 13 (2010) #10.3.6.
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181. [Annotated scan of pages 180 and 181 only]
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Steven Linton, James Propp, Tom Roby, and Julian West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.
E. Lucas, Théorie des Nombres, Gauthier-Villars, Paris, 1891, Vol. 1, p. 221.
E. Lucas, Théorie des nombres (annotated scans of a few selected pages)
T. Mansour and M. Shattuck, Partial matchings and pattern avoidance, Appl. Anal. Discrete Math. (to appear, 2012); - From _N. J. A. Sloane_, Jan 04 2013
I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637 [math.CO], 2013 and J. Int. Seq. 17 (2014) #14.1.1.
F. L. Miksa, L. Moser and M. Wyman, Restricted partitions of finite sets, Canad. Math. Bull., 1 (1958), 87-96.
L. Moser and M. Wyman, On solutions of x^d = 1 in symmetric groups, Canad. J. Math., 7 (1955), 159-168.
T. Mueller, Finite group actions and asymptotic expansion of e^P(z), Combinatorica, 17 (4) (1997), 523-554.
Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
I. Pak, G. Panova, and E. Vallejo, Kronecker products, characters, partitions, and the tensor square conjectures, arXiv:1304.0738 [math.CO], 2013.
D. Panyushev, On the orbits of a Borel subgroup in abelian ideals, arXiv preprint arXiv:1407.6857 [math.AG], 2014.
P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
R. Petuchovas, Asymptotic analysis of the cyclic structure of permutations, arXiv:1611.02934 [math.CO], p. 6, 2016.
R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.
J. L. Ramírez and G. N. Rubiano, Properties and Generalizations of the Fibonacci Word Fractal, The Mathematica Journal, Vol. 16 (2014).
J. Riordan, Letter to N. J. A. Sloane, Feb 03 1975 (with notes by njas)
R. W. Robinson, Counting arrangements of bishops, Lect. Notes Math. 560 (1976), 198-214. See D_n.
H. A. Rothe, Ueber Permutationen, in Beziehung auf die Stellen ihrer Elemente. Anwendung der daraus abgeleiteten Sätze auf das Eliminationsproblem, in Carl Hindenberg, ed., Sammlung Combinatorisch-Analytischer Abhandlungen, pp. 263-305, Bey G. Fleischer dem jüngern, 1800; see p. 282.
Ahmad Sabri and Vincent Vajnovszki, Exhaustive generation for ballot sequences in lexicographic and Gray code order, CEUR Workshop Proceedings, 2018.
Ahmad Sabri and Vincent Vajnovszki, On the exhaustive generation of generalized ballot sequences in lexicographic and Gray code order, Pure Mathematics and Applications (2019) Vol. 28, Issue 1, 109-119.
A. I. Solomon, P. Blasiak, G. Duchamp, A. Horzela and K. A. Penson, Combinatorial physics, normal order and model Feynman graphs, arXiv:quant-ph/0310174, 2003.
Bridget Eileen Tenner, Star factorizations and noncrossing partitions, arXiv:2004.03286 [math.CO], 2020.
Robert F. Tichy and Stephan Wagner, Extremal Problems for Topological Indices in Combinatorial Chemistry, Journal of Computational Biology. September 2005, 12(7): 1004-1013.
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Hosoya Index
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Permutation Involution
Eric Weisstein's World of Mathematics, Triangular Graph
Eric Weisstein's World of Mathematics, Vertex Cover
Eric Weisstein's World of Mathematics, Young Tableau
Allan Wentink, Symmetry with Independent Blocks, on the late Ralph E. Griswold webpage of sample-chapters of an unfinished book about weaving, http://www.cs.arizona.edu/patterns/weaving/webdocs.html. [Cached copy]
Wikipedia, Telephone numbers.
Wikipedia, Young tableau.
Index entries for "core" sequences
Index entries for sequences related to Young tableaux.
Index entries for related partition-counting sequences

Cf. A001147, A001470, A053529, A099174, A136281-A136283, A001680, A001681.
See also A005425 for another version of the switchboard problem.
Equals 2 * A001475(n-1) for n>1.
First column of array A099020.
A069943(n+1)/A069944(n+1) = a(n)/A000142(n) in lowest terms.
Cf. A152736, A128229. - Gary W. Adamson, Dec 12 2008
Diagonal of A182172. - Alois P. Heinz, May 30 2012
Cf. A001813, A006882, A135401, A297708. - Manfred Scheucher, Jan 07 2018
Row sums of: A047884, A049403, A096713 (absolute value), A100861, A104556 (absolute value), A111924, A117506 (M_4 numbers), A122848, A238123.
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A322661 counts labeled covering half-loop-graphs.
A339742 counts factorizations into distinct primes or squarefree semiprimes.
Cf. A000110, A000258, A000700, A000701, A321729, A321730, A321737.

a000085 n = a000085_list !! n
  a000085_list = 1 : 1 : zipWith (+)
    (zipWith (*) [1..] a000085_list) (tail a000085_list) -- Reinhard Zumkeller, May 16 2013

A000085 := proc(n) option remember; if n=0 then 1 elif n=1 then 1 else procname(n-1)+(n-1)*procname(n-2); fi; end;
with(combstruct):ZL3:=[S,{S=Set(Cycle(Z,card<3))}, labeled]:seq(count(ZL3,size=n),n=0..25); # Zerinvary Lajos, Sep 24 2007
with (combstruct):a:=proc(m) [ZL, {ZL=Set(Cycle(Z, m>=card))}, labeled]; end: A:=a(2):seq(count(A, size=n), n=0..25); # Zerinvary Lajos, Jun 11 2008

<Roger L. Bagula, Oct 06 2006 *)
With[{nn=30},CoefficientList[Series[Exp[x+x^2/2],{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, May 28 2013 *)
a[ n_] := Sum[(2 k - 1)!! Binomial[ n, 2 k], {k, 0, n/2}]; (* Michael Somos, Jun 01 2013 *)
a[ n_] := If[ n < 0, 0, HypergeometricU[ -n/2, 1/2, -1/2] / (-1/2)^(n/2)]; (* Michael Somos, Jun 01 2013 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[ x + x^2 / 2], {x, 0, n}]]; (* Michael Somos, Jun 01 2013 *)
Table[(I/Sqrt[2])^n HermiteH[n, -I/Sqrt[2]], {n, 0, 100}] (* Emanuele Munarini, Mar 02 2016 *)
a[n_] := Sum[StirlingS1[n, k]*2^k*BellB[k, 1/2], {k, 0, n}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jul 18 2017, after Emanuele Munarini *)
RecurrenceTable[{a[n] == a[n-1] + (n-1)*a[n-2], a[0] == 1, a[1] == 1}, a, {n, 0, 20}] (* Joan Ludevid, Jun 17 2022 *)
sds[{}]:={{}};sds[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sds[Complement[set,s]]]/@Cases[Subsets[set,{1,2}],{i,_}]; Table[Length[sds[Range[n]]],{n,0,10}] (* Gus Wiseman, Jan 11 2021 *)

B(n,x):=sum(stirling2(n,k)*x^k,k,0,n);
  a(n):=sum(stirling1(n,k)*2^k*B(k,1/2),k,0,n);
  makelist(a(n),n,0,40); /* Emanuele Munarini, May 16 2014 */

makelist((%i/sqrt(2))^n*hermite(n,-%i/sqrt(2)),n,0,12); /* Emanuele Munarini, Mar 02 2016 */

{a(n) = if( n<0, 0, n! * polcoeff( exp( x + x^2 / 2 + x * O(x^n)), n))}; /* Michael Somos, Nov 15 2002 */

N=66; x='x+O('x^N); egf=exp(x+x^2/2); Vec(serlaplace(egf)) \\ Joerg Arndt, Mar 07 2013

from math import factorial
def A000085(n): return sum(factorial(n)//(factorial(n-(k<<1))*factorial(k)*(1<>1)+1)) # Chai Wah Wu, Aug 31 2023

A000085 = lambda n: hypergeometric([-n/2,(1-n)/2], [], 2)
[simplify(A000085(n)) for n in range(28)] # Peter Luschny, Aug 21 2014

def a85(n): return sum(factorial(n) / (factorial(n-2*k) * 2**k * factorial(k)) for k in range(1+n//2))
for n in range(100): print(n, a85(n)) # Manfred Scheucher, Jan 07 2018

D-finite with recurrence a(0) = a(1) = 1, a(n) = a(n-1) + (n-1)*a(n-2) for n>1.
E.g.f.: exp(x+x^2/2).
a(n) = a(n-1) + A013989(n-2) = A013989(n)/(n+1) = 1+A001189(n).
a(n) = Sum_{k=0..floor(n/2)} n!/((n-2*k)!*2^k*k!).
a(m+n) = Sum_{k>=0} k!*binomial(m, k)*binomial(n, k)*a(m-k)*a(n-k). - Philippe Deléham, Mar 05 2004
For n>1, a(n) = 2*(A000900(n) + A000902(floor(n/2))). - Max Alekseyev, Oct 31 2015
The e.g.f. y(x) satisfies y^2 = y''y' - (y')^2.
a(n) ~ c*(n/e)^(n/2)exp(n^(1/2)) where c=2^(-1/2)exp(-1/4). [Chowla]
a(n) = HermiteH(n, 1/(sqrt(2)*i))/(-sqrt(2)*i)^n, where HermiteH are the Hermite polynomials. - Karol A. Penson, May 16 2002
a(n) = Sum_{k=0..n} A001498((n+k)/2, (n-k)/2)(1+(-1)^(n-k))/2. - Paul Barry, Jan 12 2006
For asymptotics see the Robinson paper.
a(n) = Sum_{m=0..n} A099174(n,m). - Roger L. Bagula, Oct 06 2006
O.g.f.: A(x) = 1/(1-x-1*x^2/(1-x-2*x^2/(1-x-3*x^2/(1-... -x-n*x^2/(1- ...))))) (continued fraction). - Paul D. Hanna, Jan 17 2006
From Gary W. Adamson, Dec 29 2008: (Start)
a(n) = (n-1)*a(n-2) + a(n-1); e.g., a(7) = 232 = 6*26 + 76.
Starting with offset 1 = eigensequence of triangle A128229. (End)
a(n) = (1/sqrt(2*Pi))*Integral_{x=-oo..oo} exp(-x^2/2)*(x+1)^n. - Groux Roland, Mar 14 2011
Row sums of |A096713|. a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator sqrt(1+2*x)*d/dx. Cf. A047974 and A080599. - Peter Bala, Dec 07 2011
From Sergei N. Gladkovskii, Dec 03 2011 - Oct 28 2013: (Start)
Continued fractions:
E.g.f.: 1+x*(2+x)/(2*G(0)-x*(2+x)) where G(k)=1+x*(x+2)/(2+2*(k+1)/G(k+1)).
G.f.: 1/(U(0) - x) where U(k) = 1 + x*(k+1) - x*(k+1)/(1 - x/U(k+1)).
G.f.: 1/Q(0) where Q(k) = 1 + x*k - x/(1 - x*(k+1)/Q(k+1)).
G.f.: -1/(x*Q(0)) where Q(k) = 1 - 1/x - (k+1)/Q(k+1).
G.f.: T(0)/(1-x) where T(k) = 1 - x^2*(k+1)/( x^2*(k+1) - (1-x)^2/T(k+1)). (End)
a(n) ~ (1/sqrt(2)) * exp(sqrt(n)-n/2-1/4) * n^(n/2) * (1 + 7/(24*sqrt(n))). - Vaclav Kotesovec, Mar 07 2014
a(n) = Sum_{k=0..n} s(n,k)*(-1)^(n-k)*2^k*B(k,1/2), where the s(n,k) are (signless) Stirling numbers of the first kind, and the B(n,x) = Sum_{k=0..n} S(n,k)*x^k are the Stirling polynomials, where the S(n,k) are the Stirling numbers of the second kind. - Emanuele Munarini, May 16 2014
a(n) = hyper2F0([-n/2,(1-n)/2],[],2). - Peter Luschny, Aug 21 2014
0 = a(n)*(+a(n+1) + a(n+2) - a(n+3)) + a(n+1)*(-a(n+1) + a(n+2)) for all n in Z. - Michael Somos, Aug 22 2014
From Peter Bala, Oct 06 2021: (Start)
a(n+k) == a(n) (mod k) for all n >= 0 and all positive odd integers k.
Hence for each odd k, the sequence obtained by taking a(n) modulo k is a periodic sequence and the exact period divides k. For example, taking a(n) modulo 7 gives the purely periodic sequence [1, 1, 2, 4, 3, 5, 6, 1, 1, 2, 4, 3, 5, 6, 1, 1, 2, 4, 3, 5, 6, ...] of period 7. For similar results see A047974 and A115329. (End)

A381633 Number of ways to partition the prime indices of n into sets with distinct sums.

Original entry on oeis.org

1, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 1, 1, 2, 2, 0, 1, 1, 1, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 4, 1, 0, 2, 2, 2, 1, 1, 2, 2, 0, 1, 5, 1, 1, 1, 2, 1, 0, 0, 1, 2, 1, 1, 0, 2, 0, 2, 2, 1, 3, 1, 2, 1, 0, 2, 5, 1, 1, 2, 4, 1, 0, 1, 2, 1, 1, 2, 5, 1, 0, 0, 2, 1, 4, 2, 2, 2

Offset: 1

Gus Wiseman, Mar 09 2025

nonn

First differs from A050326 at 30, 60, 70, 90, ...
First differs from A339742 at 42, 66, 78, 84, ...
First differs from A381634 at a(210) = 12, A381634(210) = 10.
Also the number of factorizations on n into squarefree numbers > 1 with distinct sums of prime indices.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798, sum A056239.

			The A050320(60) = 6 ways to partition {1,1,2,3} into sets are:
  {{1},{1,2,3}}
  {{1,2},{1,3}}
  {{1},{1},{2,3}}
  {{1},{2},{1,3}}
  {{1},{3},{1,2}}
  {{1},{1},{2},{3}}
Of these, only the following have distinct block-sums:
  {{1},{1,2,3}}
  {{1,2},{1,3}}
  {{1},{2},{1,3}}
So a(60) = 3.

Without distinct block-sums we have A050320, after sums A381078 (lower A381454).
For distinct blocks instead of sums we have A050326, after sums A381441, see A358914.
Taking block-sums (and sorting) gives A381634.
For constant instead of strict blocks we have A381635, see A381716, A381636.
Positions of 0 are A381806, superset of A293243.
Positions of 1 are A381870, superset of A293511.
More on set multipartitions with distinct sums: A279785, A381717, A381718.
More on set multipartitions: A089259, A116540, A270995, A296119, A318360.
A000041 counts integer partitions, strict A000009.
A001055 count multiset partitions of prime indices, see A317141 (upper), A300383 (lower).
A003963 gives product of prime indices.
A055396 gives least prime index, greatest A061395.
A056239 adds up prime indices, row sums of A112798.
A265947 counts refinement-ordered pairs of integer partitions.
Cf. A000720, A001222, A002846, A005117, A213242, A299202, A300385, A317142, A317143, A321469.

hwt[n_]:=Total[Cases[FactorInteger[n],{p_,k_}:>PrimePi[p]*k]];
sfacs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#,d]&)/@Select[sfacs[n/d],Min@@#>=d&],{d,Select[Rest[Divisors[n]],SquareFreeQ]}]];
Table[Length[Select[sfacs[n],UnsameQ@@hwt/@#&]],{n,100}]

A339741 Products of distinct primes or squarefree semiprimes.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 26, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 50, 51, 52, 53, 55, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 82, 83, 84

Offset: 1

Gus Wiseman, Dec 23 2020

nonn

First differs from A212167 in lacking 1080, with prime indices {1,1,1,2,2,2,3}.
First differs from A335433 in lacking 72 (see example).
A squarefree semiprime (A006881) is a product of any two distinct prime numbers.
The following are equivalent characteristics for any positive integer n:
(1) the prime factors of n can be partitioned into distinct singletons and strict pairs, i.e., into a set of half-loops and edges;
(2) n can be factored into distinct primes or squarefree semiprimes;
(3) the prime signature of n is half-loop-graphical.

			The sequence of terms together with their prime indices begins:
       1: {}           20: {1,1,3}        39: {2,6}
       2: {1}          21: {2,4}          41: {13}
       3: {2}          22: {1,5}          42: {1,2,4}
       5: {3}          23: {9}            43: {14}
       6: {1,2}        26: {1,6}          44: {1,1,5}
       7: {4}          28: {1,1,4}        45: {2,2,3}
      10: {1,3}        29: {10}           46: {1,9}
      11: {5}          30: {1,2,3}        47: {15}
      12: {1,1,2}      31: {11}           50: {1,3,3}
      13: {6}          33: {2,5}          51: {2,7}
      14: {1,4}        34: {1,7}          52: {1,1,6}
      15: {2,3}        35: {3,4}          53: {16}
      17: {7}          36: {1,1,2,2}      55: {3,5}
      18: {1,2,2}      37: {12}           57: {2,8}
      19: {8}          38: {1,8}          58: {1,10}
For example, we have 36 = (2*3*6), so 36 is in the sequence. On the other hand, a complete list of all strict factorizations of 72 is: (2*3*12), (2*4*9), (2*36), (3*4*6), (3*24), (4*18), (6*12), (8*9), (72). Since none of these consists of only primes or squarefree semiprimes, 72 is not in the sequence. A complete list of all factorizations of 1080 into primes or squarefree semiprimes is:
  (2*2*2*3*3*3*5)
  (2*2*2*3*3*15)
  (2*2*3*3*3*10)
  (2*2*3*3*5*6)
  (2*2*3*6*15)
  (2*3*3*6*10)
  (2*3*5*6*6)
  (2*6*6*15)
  (3*6*6*10)
  (5*6*6*6)
Since none of these is strict, 1080 is not in the sequence.

Eric Weisstein's World of Mathematics, Degree Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

See link for additional cross-references.
Allowing only primes gives A013929.
Not allowing primes gives A339561.
Complement of A339740.
Positions of positive terms in A339742.
Allowing squares of primes gives the complement of A339840.
Unlabeled multiset partitions of this type are counted by A339888.
A001055 counts factorizations.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A339841 have exactly one factorization into primes or semiprimes.
Cf. A001221, A005117, A028260, A030229, A050320, A112798, A309356, A320663, A320893, A320924, A338899.

sqps[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[sqps[n/d],Min@@#>d&]],{d,Select[Divisors[n],PrimeQ[#]||SquareFreeQ[#]&&PrimeOmega[#]==2&]}]];
Select[Range[100],sqps[#]!={}&]

A122848 Exponential Riordan array (1, x(1+x/2)).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 3, 1, 0, 0, 3, 6, 1, 0, 0, 0, 15, 10, 1, 0, 0, 0, 15, 45, 15, 1, 0, 0, 0, 0, 105, 105, 21, 1, 0, 0, 0, 0, 105, 420, 210, 28, 1, 0, 0, 0, 0, 0, 945, 1260, 378, 36, 1, 0, 0, 0, 0, 0, 945, 4725, 3150, 630, 45, 1, 0, 0, 0, 0, 0, 0, 10395, 17325, 6930, 990, 55, 1, 0, 0

Offset: 0

Paul Barry, Sep 14 2006

Entries are Bessel polynomial coefficients. Row sums are A000085. Diagonal sums are A122849. Inverse is A122850. Product of A007318 and A122848 gives A100862.
T(n,k) is the number of self-inverse permutations of {1,2,...,n} having exactly k cycles. - Geoffrey Critzer, May 08 2012
Bessel numbers of the second kind. For relations to the Hermite polynomials and the Catalan (A033184 and A009766) and Fibonacci (A011973, A098925, and A092865) matrices, see Yang and Qiao. - Tom Copeland, Dec 18 2013.
Also the inverse Bell transform of the double factorial of odd numbers Product_{k= 0..n-1} (2*k+1) (A001147). For the definition of the Bell transform see A264428 and for cross-references A265604. - Peter Luschny, Dec 31 2015

			Triangle begins:
    1
    0    1
    0    1    1
    0    0    3    1
    0    0    3    6    1
    0    0    0   15   10    1
    0    0    0   15   45   15    1
    0    0    0    0  105  105   21    1
    0    0    0    0  105  420  210   28    1
    0    0    0    0    0  945 1260  378   36    1
From _Gus Wiseman_, Jan 12 2021: (Start)
As noted above, a(n) is the number of set partitions of {1..n} into k singletons or pairs. This is also the number of set partitions of subsets of {1..n} into n - k pairs. In the first case, row n = 5 counts the following set partitions:
  {{1},{2,3},{4,5}}  {{1},{2},{3},{4,5}}  {{1},{2},{3},{4},{5}}
  {{1,2},{3},{4,5}}  {{1},{2},{3,4},{5}}
  {{1,2},{3,4},{5}}  {{1},{2,3},{4},{5}}
  {{1,2},{3,5},{4}}  {{1,2},{3},{4},{5}}
  {{1},{2,4},{3,5}}  {{1},{2},{3,5},{4}}
  {{1},{2,5},{3,4}}  {{1},{2,4},{3},{5}}
  {{1,3},{2},{4,5}}  {{1},{2,5},{3},{4}}
  {{1,3},{2,4},{5}}  {{1,3},{2},{4},{5}}
  {{1,3},{2,5},{4}}  {{1,4},{2},{3},{5}}
  {{1,4},{2},{3,5}}  {{1,5},{2},{3},{4}}
  {{1,4},{2,3},{5}}
  {{1,4},{2,5},{3}}
  {{1,5},{2},{3,4}}
  {{1,5},{2,3},{4}}
  {{1,5},{2,4},{3}}
In the second case, we have:
  {{1,2},{3,4}}  {{1,2}}  {}
  {{1,2},{3,5}}  {{1,3}}
  {{1,2},{4,5}}  {{1,4}}
  {{1,3},{2,4}}  {{1,5}}
  {{1,3},{2,5}}  {{2,3}}
  {{1,3},{4,5}}  {{2,4}}
  {{1,4},{2,3}}  {{2,5}}
  {{1,4},{2,5}}  {{3,4}}
  {{1,4},{3,5}}  {{3,5}}
  {{1,5},{2,3}}  {{4,5}}
  {{1,5},{2,4}}
  {{1,5},{3,4}}
  {{2,3},{4,5}}
  {{2,4},{3,5}}
  {{2,5},{3,4}}
(End)

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Peter Bala, Generalized Dobinski formulas
Richell O. Celeste, Roberto B. Corcino, and Ken Joffaniel M. Gonzales, Two Approaches to Normal Order Coefficients, Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.5.
Tom Copeland, Infinitesimal Generators, the Pascal Pyramid, and the Witt and Virasoro Algebras
H. Han and S. Seo, Combinatorial proofs of inverse relations and log-concavity for Bessel numbers, Eur. J. Combinat. 29 (7) (2008) 1544-1554. [From _R. J. Mathar_, Mar 20 2009]
Robert S. Maier, Boson Operator Ordering Identities from Generalized Stirling and Eulerian Numbers, arXiv:2308.10332 [math.CO], 2023. See p. 18.
S. Yang and Z. Qiao, The Bessel Numbers and Bessel Matrices, Journal of Mathematical Research & Exposition, July, 2011, Vol. 31, No. 4, pp. 627-636. [From _Tom Copeland_, Dec 18 2013]

Cf. A001497, A008275, A039755, A096713, A104556, A113278, A130757.
Row sums are A000085.
Column sums are A001515.
Same as A049403 but with a first column k = 0.
The same set partitions counted by number of pairs are A100861.
Reversing rows gives A111924 (without column k = 0).
A047884 counts standard Young tableaux by size and greatest row length.
A238123 counts standard Young tableaux by size and least row length.
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A322661 counts labeled covering half-loop-graphs.
A339742 counts factorizations into distinct primes or squarefree semiprimes.
Cf. A000110, A000258, A320732, A321729, A339741, A339887.

# The function BellMatrix is defined in A264428.
BellMatrix(n -> `if`(n<2,1,0), 9); # Peter Luschny, Jan 27 2016

t[n_, k_] := k!*Binomial[n, k]/((2 k - n)!*2^(n - k)); Table[ t[n, k], {n, 0, 11}, {k, 0, n}] // Flatten
(* Second program: *)
rows = 12;
t = Join[{1, 1}, Table[0, rows]];
T[n_, k_] := BellY[n, k, t];
Table[T[n, k], {n, 0, rows}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 23 2018,after Peter Luschny *)
sbs[{}]:={{}};sbs[set:{i_,_}]:=Join@@Function[s,(Prepend[#1,s]&)/@sbs[Complement[set,s]]]/@Cases[Subsets[set],{i}|{i,_}];
Table[Length[Select[sbs[Range[n]],Length[#]==k&]],{n,0,6},{k,0,n}] (* Gus Wiseman, Jan 12 2021 *)

{T(n,k)=if(2*kn, 0, n!/(2*k-n)!/(n-k)!*2^(k-n))} /* Michael Somos, Oct 03 2006 */

# uses[inverse_bell_transform from A265605]
multifact_2_1 = lambda n: prod(2*k + 1 for k in (0..n-1))
inverse_bell_matrix(multifact_2_1, 9) # Peter Luschny, Dec 31 2015

Number triangle T(n,k) = k!*C(n,k)/((2k-n)!*2^(n-k)).
T(n,k) = A001498(k,n-k). - Michael Somos, Oct 03 2006
E.g.f.: exp(y(x+x^2/2)). - Geoffrey Critzer, May 08 2012
Triangle equals the matrix product A008275*A039755. Equivalently, the n-th row polynomial R(n,x) is given by the Type B Dobinski formula R(n,x) = exp(-x/2)*Sum_{k>=0} P(n,2*k+1)*(x/2)^k/k!, where P(n,x) = x*(x-1)*...*(x-n+1) denotes the falling factorial polynomial. Cf. A113278. - Peter Bala, Jun 23 2014
From Daniel Checa, Aug 28 2022: (Start)
E.g.f. for the m-th column: (x^2/2+x)^m/m!.
T(n,k) = T(n-1,k-1) + (n-1)*T(n-2,k-1) for n>1 and k=1..n, T(0,0) = 1. (End)

A381634 Number of multisets that can be obtained by taking the sum of each block of a set multipartition (multiset of sets) of the prime indices of n with distinct block-sums.

Original entry on oeis.org

Offset: 1

Gus Wiseman, Mar 06 2025

nonn

First differs from A050326 at a(30) = 4, A050326(30) = 5.
First differs from A339742 at a(42) = 5, A339742(42) = 4.
First differs from A381441 at a(30) = 4, A381441(30) = 5.
First differs from A381633 at a(210) = 10, A381633(210) = 12.
Also the number of multisets that can be obtained by taking the sums of prime indices of each factor in a factorization of n into squarefree numbers > 1 with distinct sums of prime indices (A056239).
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
A multiset partition con be regarded as an arrow in the ranked poset of integer partitions. For example, we have {{1},{1,2},{1,3},{1,2,3}}: {1,1,1,1,2,2,3,3} -> {1,3,4,6}, or (33221111) -> (6431) (depending on notation).
Set multipartitions with distinct block-sums are generally not transitive. For example, we have arrows: {{1},{1,2}}: {1,1,2} -> {1,3} and {{1,3}}: {1,3} -> {4}, but there is no arrow {1,1,2} -> {4}.

			The prime indices of 120 are {1,1,2,3}, with 3 ways:
  {{1},{1,2,3}}
  {{1,2},{1,3}}
  {{1},{2},{1,3}}
with block-sums: {1,6}, {3,4}, {1,2,4}, so a(120) = 3.
The prime indices of 210 are {1,2,3,4}, with 12 ways:
  {{1,2,3,4}}
  {{1},{2,3,4}}
  {{2},{1,3,4}}
  {{3},{1,2,4}}
  {{4},{1,2,3}}
  {{1,2},{3,4}}
  {{1,3},{2,4}}
  {{1},{2},{3,4}}
  {{1},{3},{2,4}}
  {{1},{4},{2,3}}
  {{2},{3},{1,4}}
  {{1},{2},{3},{4}}
with block-sums: {10}, {1,9}, {2,8}, {3,7}, {4,6}, {3,7}, {4,6}, {1,2,7}, {1,3,6}, {1,4,5}, {2,3,5}, {1,2,3,4}, of which 10 are distinct, so a(210) = 10.

Without distinct block-sums we have A381078 (lower A381454), before sums A050320.
For distinct blocks instead of sums we have A381441, before sums A050326, see A358914.
Before taking sums we had A381633.
Positions of 0 are A381806.
Positions of 1 are A381870, superset of A293511.
More on set multipartitions with distinct sums: A279785, A381717, A381718.
A001055 counts multiset partitions, see A317141 (upper), A300383 (lower).
A003963 gives product of prime indices.
A055396 gives least prime index, greatest A061395.
A056239 adds up prime indices, row sums of A112798.
A265947 counts refinement-ordered pairs of integer partitions.
Cf. A000720, A001222, A002846, A005117, A116540, A213242, A213385, A213427, A299202, A300385, A317142, A317143, A318360.

hwt[n_]:=Total[Cases[FactorInteger[n],{p_,k_}:>PrimePi[p]*k]];
sfacs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#,d]&)/@Select[sfacs[n/d],Min@@#>=d&],{d,Select[Rest[Divisors[n]],SquareFreeQ]}]];
Table[Length[Union[Sort[hwt/@#]&/@Select[sfacs[n],UnsameQ@@hwt/@#&]]],{n,100}]

A339657 Heinz numbers of non-loop-graphical partitions of even numbers.

Original entry on oeis.org

7, 13, 19, 21, 22, 29, 34, 37, 39, 43, 46, 49, 52, 53, 55, 57, 61, 62, 66, 71, 76, 79, 82, 85, 87, 89, 91, 94, 101, 102, 107, 111, 113, 115, 116, 117, 118, 121, 129, 130, 131, 133, 134, 136, 138, 139, 146, 148, 151, 154, 155, 156, 159, 163, 165, 166, 169, 171

Offset: 1

Gus Wiseman, Dec 18 2020

nonn

Equals the image of A181819 applied to the set of terms of A320892.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.
An integer partition is loop-graphical if it comprises the multiset of vertex-degrees of some graph with loops, where a loop is an edge with two equal vertices. Loop-graphical partitions are counted by A339656, with Heinz numbers A339658.
The following are equivalent characteristics for any positive integer n:
(1) the prime factors of n can be partitioned into distinct pairs, i.e., into a set of edges and loops;
(2) n can be factored into distinct semiprimes;
(3) the prime signature of n is loop-graphical.

			The sequence of terms together with their prime indices begins:
      7: {4}         57: {2,8}      107: {28}
     13: {6}         61: {18}       111: {2,12}
     19: {8}         62: {1,11}     113: {30}
     21: {2,4}       66: {1,2,5}    115: {3,9}
     22: {1,5}       71: {20}       116: {1,1,10}
     29: {10}        76: {1,1,8}    117: {2,2,6}
     34: {1,7}       79: {22}       118: {1,17}
     37: {12}        82: {1,13}     121: {5,5}
     39: {2,6}       85: {3,7}      129: {2,14}
     43: {14}        87: {2,10}     130: {1,3,6}
     46: {1,9}       89: {24}       131: {32}
     49: {4,4}       91: {4,6}      133: {4,8}
     52: {1,1,6}     94: {1,15}     134: {1,19}
     53: {16}       101: {26}       136: {1,1,1,7}
     55: {3,5}      102: {1,2,7}    138: {1,2,9}
For example, the three loop-multigraphs with degrees y = (5,2,1) are:
  {{1,1},{1,1},{1,2},{2,3}}
  {{1,1},{1,1},{1,3},{2,2}}
  {{1,1},{1,2},{1,2},{1,3}},
but since none of these is a loop-graph (they have multiple edges), the Heinz number 66 is in the sequence.

Eric Weisstein's World of Mathematics, Graphical partition.

A320892 has these prime shadows (see A181819).
A321728 is conjectured to be the version for half-loops {x} instead of loops {x,x}.
A339655 counts these partitions.
A339658 ranks the complement, counted by A339656.
A001358 lists semiprimes, with odd and even terms A046315 and A100484.
A006881 lists squarefree semiprimes, with odd and even terms A046388 and A100484.
A101048 counts partitions into semiprimes.
A320655 counts factorizations into semiprimes.
A320656 counts factorizations into squarefree semiprimes.
A339844 counts loop-graphical partitions by length.
factorizations of n into distinct primes or squarefree semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A209816 counts multigraphical partitions (A320924).
- A339655 counts non-loop-graphical partitions of 2n (A339657 [this sequence]).
- A339656 counts loop-graphical partitions (A339658).
- A339617 counts non-graphical partitions of 2n (A339618).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A001221, A001222, A007717, A056239, A112798, A320732, A338898, A338912, A338913, A339742, A339839.

spsbin[{}]:={{}};spsbin[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsbin[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpsbin[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@spsbin[Range[Length[set]]]];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[50],EvenQ[Length[nrmptn[#]]]&&Select[mpsbin[nrmptn[#]],UnsameQ@@#&]=={}&]

A300061 = A339657 \/ A339658.

A339888 Number of non-isomorphic multiset partitions of weight n into singletons or strict pairs.

Original entry on oeis.org

1, 1, 3, 5, 13, 23, 55, 104, 236, 470, 1039, 2140, 4712, 9962, 21961, 47484, 105464, 232324, 521338, 1167825, 2651453, 6031136, 13863054, 31987058, 74448415, 174109134, 410265423, 971839195, 2317827540, 5558092098, 13412360692, 32542049038, 79424450486

Offset: 0

Gus Wiseman, Jan 09 2021

nonn

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 13 multiset partitions:
  {{1}}  {{1,2}}    {{1},{2,3}}    {{1,2},{1,2}}
         {{1},{1}}  {{2},{1,2}}    {{1,2},{3,4}}
         {{1},{2}}  {{1},{1},{1}}  {{1,3},{2,3}}
                    {{1},{2},{2}}  {{1},{1},{2,3}}
                    {{1},{2},{3}}  {{1},{2},{1,2}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{1},{1},{1}}
                                   {{1},{1},{2},{2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

The version for set partitions is A000085, with ordered version A080599.
The case of integer partitions is 1 + A004526(n), ranked by A003586.
Non-isomorphic multiset partitions are counted by A007716.
The case without singletons is A007717.
The version allowing non-strict pairs (x,x) is A320663.
A001190 counts rooted trees with out-degrees <= 2, ranked by A292050.
A339742 counts factorizations into distinct primes or squarefree semiprimes.
A339887 counts factorizations into primes or squarefree semiprimes.
Cf. A001055, A007718, A316983, A319616, A320656, A321729, A339740, A339741.

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
gs(v) = {sum(i=2, #v, sum(j=1, i-1, my(g=gcd(v[i], v[j])); g*x^(2*v[i]*v[j]/g))) + sum(i=1, #v, my(r=v[i]); (1 + (1+r)%2)*x^r + ((r-1)\2)*x^(2*r))}
a(n)={if(n==0, 1, my(s=0); forpart(p=n, s+=permcount(p)*EulerT(Vec(gs(p) + O(x*x^n), -n))[n]); s/n!)} \\ Andrew Howroyd, Apr 16 2021

Terms a(11) and beyond from Andrew Howroyd, Apr 16 2021

A339661 Number of factorizations of n into distinct squarefree semiprimes.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0

Offset: 1

Gus Wiseman, Dec 19 2020

nonn

A squarefree semiprime (A006881) is a product of any two distinct prime numbers.

Also the number of strict multiset partitions of the multiset of prime factors of n, into distinct strict pairs.

			The a(n) factorizations for n = 210, 1260, 4620, 30030, 69300 are respectively 3, 2, 6, 15, 7:
  (6*35)   (6*10*21)  (6*10*77)   (6*55*91)    (6*10*15*77)
  (10*21)  (6*14*15)  (6*14*55)   (6*65*77)    (6*10*21*55)
  (14*15)             (6*22*35)   (10*33*91)   (6*10*33*35)
                      (10*14*33)  (10*39*77)   (6*14*15*55)
                      (10*21*22)  (14*33*65)   (6*15*22*35)
                      (14*15*22)  (14*39*55)   (10*14*15*33)
                                  (15*22*91)   (10*15*21*22)
                                  (15*26*77)
                                  (21*22*65)
                                  (21*26*55)
                                  (22*35*39)
                                  (26*33*35)
                                  (6*35*143)
                                  (10*21*143)
                                  (14*15*143)

Antti Karttunen, Table of n, a(n) for n = 1..69300
Index entries for sequences computed from exponents in factorization of n

Dirichlet convolution of A008836 (Liouville's lambda) with A339742.
A050326 allows all squarefree numbers, non-strict case A050320.
A320656 is the not necessarily strict version.
A320911 lists all (not just distinct) products of squarefree semiprimes.
A322794 counts uniform factorizations, such as these.
A339561 lists positions of nonzero terms.
A001055 counts factorizations, with strict case A045778.
A001358 lists semiprimes, with squarefree case A006881.
A320655 counts factorizations into semiprimes, with strict case A322353.
The following count vertex-degree partitions and give their Heinz numbers:
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A209816 counts multigraphical partitions (A320924).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
- A339617 counts non-graphical partitions of 2n (A339618).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001221, A005117, A007716, A028260, A280710, A300061, A320658, A320659, A320923, A330974.

bfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[bfacs[n/d],Min@@#>d&]],{d,Select[Rest[Divisors[n]],SquareFreeQ[#]&&PrimeOmega[#]==2&]}]];
Table[Length[bfacs[n]],{n,100}]

A280710(n) = (bigomega(n)==2*issquarefree(n)); \\ From A280710.
A339661(n, u=(1+n)) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1) && (dA280710(d), s += A339661(n/d, d))); (s)); \\ Antti Karttunen, May 02 2022

a(n) = Sum_{d|n} (-1)^A001222(d) * A339742(n/d).

More terms and secondary offset added by Antti Karttunen, May 02 2022

A339839 Number of factorizations of n into distinct primes or semiprimes.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 0, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 4, 1, 0, 2, 2, 2, 2, 1, 2, 2, 2, 1, 4, 1, 2, 2, 2, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 5, 1, 2, 2, 0, 2, 4, 1, 2, 2, 4, 1, 2, 1, 2, 2, 2, 2, 4, 1, 1, 0, 2, 1, 5, 2, 2, 2, 2, 1, 5, 2, 2, 2, 2, 2, 0, 1, 2, 2, 2, 1, 4, 1, 2, 4

Offset: 1

Gus Wiseman, Dec 20 2020

nonn

A semiprime (A001358) is a product of any two prime numbers.

			The a(n) factorizations for n = 6, 16, 30, 60, 180, 210, 240, 420:
  6    5*6    4*15    4*5*9    6*35     4*6*10    2*6*35
  2*3  2*15   6*10    2*6*15   10*21    2*4*5*6   3*4*35
       3*10   2*5*6   2*9*10   14*15    2*3*4*10  4*5*21
       2*3*5  3*4*5   3*4*15   5*6*7              4*7*15
              2*3*10  3*6*10   2*3*35             5*6*14
                      2*3*5*6  2*5*21             6*7*10
                               2*7*15             2*10*21
                               3*5*14             2*14*15
                               3*7*10             2*5*6*7
                               2*3*5*7            3*10*14
                                                  3*4*5*7
                                                  2*3*5*14
                                                  2*3*7*10

Antti Karttunen, Table of n, a(n) for n = 1..100000
Index entries for sequences computed from exponents in factorization of n

A008966 allows only primes.
A320732 is the non-strict version.
A339742 does not allow squares of primes.
A339840 lists the positions of zeros.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A013929 cannot be factored into distinct primes.
A293511 are a product of distinct squarefree numbers in exactly one way.
A320663 counts non-isomorphic multiset partitions into singletons or pairs.
A339841 have exactly one factorization into primes or semiprimes.
The following count factorizations:
- A001055 into all positive integers > 1.
- A320655 into semiprimes.
- A320656 into squarefree semiprimes.
- A322353 into distinct semiprimes.
- A339839 [this sequence] into distinct primes or semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A000569 counts graphical partitions (A320922).
- A339656 counts loop-graphical partitions (A339658).
Cf. A000070, A001222, A028260, A320893, A338898, A339617, A339661, A339740, A339741, A339846.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],UnsameQ@@#&&SubsetQ[{1,2},PrimeOmega/@#]&]],{n,100}]

A339839(n, u=(1+n)) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1) && (dA339839(n/d, d))); (s)); \\ Antti Karttunen, Feb 10 2023

a(n) = Sum_{d|n squarefree} A322353(n/d).

Data section extended up to a(105) by Antti Karttunen, Feb 10 2023

A339740 Non-products of distinct primes or squarefree semiprimes.

Original entry on oeis.org

4, 8, 9, 16, 24, 25, 27, 32, 40, 48, 49, 54, 56, 64, 72, 80, 81, 88, 96, 104, 108, 112, 121, 125, 128, 135, 136, 144, 152, 160, 162, 169, 176, 184, 189, 192, 200, 208, 216, 224, 232, 240, 243, 248, 250, 256, 272, 288, 289, 296, 297, 304, 320, 324, 328, 336

Offset: 1

Gus Wiseman, Dec 20 2020

nonn

Differs from A293243 and A212164 in having 1080, with prime indices {1,1,1,2,2,2,3} and factorization into distinct squarefree numbers 2*3*6*30.

			The sequence of terms together with their prime indices begins:
      4: {1,1}             80: {1,1,1,1,3}
      8: {1,1,1}           81: {2,2,2,2}
      9: {2,2}             88: {1,1,1,5}
     16: {1,1,1,1}         96: {1,1,1,1,1,2}
     24: {1,1,1,2}        104: {1,1,1,6}
     25: {3,3}            108: {1,1,2,2,2}
     27: {2,2,2}          112: {1,1,1,1,4}
     32: {1,1,1,1,1}      121: {5,5}
     40: {1,1,1,3}        125: {3,3,3}
     48: {1,1,1,1,2}      128: {1,1,1,1,1,1,1}
     49: {4,4}            135: {2,2,2,3}
     54: {1,2,2,2}        136: {1,1,1,7}
     56: {1,1,1,4}        144: {1,1,1,1,2,2}
     64: {1,1,1,1,1,1}    152: {1,1,1,8}
     72: {1,1,1,2,2}      160: {1,1,1,1,1,3}
For example, a complete list of strict factorizations of 72 is: (2*3*12), (2*4*9), (2*36), (3*4*6), (3*24), (4*18), (6*12), (8*9), (72); but since none of these consists of only primes or squarefree semiprimes, 72 is in the sequence.

A013929 allows only primes.
A320894 does not allow primes (but omega is assumed even).
A339741 is the complement.
A339742 has zeros at these positions.
A339840 allows squares of primes.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A320663 counts non-isomorphic multiset partitions into singletons or pairs.
A339841 have exactly one factorization into primes or semiprimes.
The following count factorizations:
- A001055 into all positive integers > 1.
- A050326 into distinct squarefree numbers.
- A320655 into semiprimes.
- A320656 into squarefree semiprimes.
- A320732 into primes or semiprimes.
- A322353 into distinct semiprimes.
- A339661 into distinct squarefree semiprimes.
- A339839 into distinct primes or semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339617 counts non-graphical partitions of 2n (A339618).
- A321728 is conjectured to count non-half-loop-graphical partitions of n.
The following count partitions/factorizations of even length and give their Heinz numbers:
- A027187/A339846 counts all of even length (A028260).
- A096373/A339737 cannot be partitioned into strict pairs (A320891).
- A338915/A339662 cannot be partitioned into distinct pairs (A320892).
- A339559/A339564 cannot be partitioned into distinct strict pairs (A320894).
Cf. A001221, A005117, A050320, A320893, A320911, A320912, A320922, A320924, A339113, A339561.

sqps[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[sqps[n/d],Min@@#>d&]],{d,Select[Divisors[n],PrimeQ[#]||SquareFreeQ[#]&&PrimeOmega[#]==2&]}]];
Select[Range[100],sqps[#]=={}&]

cp's OEIS Frontend

A000085 Number of self-inverse permutations on n letters, also known as involutions; number of standard Young tableaux with n cells.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

Maxima

PARI

PARI

Python

Sage

Sage

Formula

A381633 Number of ways to partition the prime indices of n into sets with distinct sums.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A339741 Products of distinct primes or squarefree semiprimes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A122848 Exponential Riordan array (1, x(1+x/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A381634 Number of multisets that can be obtained by taking the sum of each block of a set multipartition (multiset of sets) of the prime indices of n with distinct block-sums.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A339657 Heinz numbers of non-loop-graphical partitions of even numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A339888 Number of non-isomorphic multiset partitions of weight n into singletons or strict pairs.

Views

Author

Keywords

Examples