A007840 Number of factorizations of permutations of n letters into ordered cycles.

1, 1, 3, 14, 88, 694, 6578, 72792, 920904, 13109088, 207360912, 3608233056, 68495486640, 1408631978064, 31197601660080, 740303842925184, 18738231641600256, 503937595069600896, 14349899305396086912, 431322634732516137216, 13646841876634025159424

Offset

0,3

Comments

a(n) is the number of ways to seat n people at an unspecified number of circular tables and then linearly order the nonempty tables. - Geoffrey Critzer, Mar 18 2009

The terms of this sequence for n >= 1 are the row sums of A008275^2, the unsigned version of A039814. - Peter Bala, Jul 22 2014

Signed sequence is the base for an Appell sequence of polynomials with the e.g.f. e^(x*t)/[log(1+t) + 1] = exp(P(.,x),t) that is the umbral compositional inverse for A238385, reverse of A111492, i.e., umbrally evaluated UP(n,P(.,t))= x^n = P(n,UP(.,t)) where UP(n,t) are the polynomials of A238385. Umbrally evaluated means letting (A(.,t))^n = A(n,t) after substituting A for the independent variable of the polynomial. - Tom Copeland, Nov 15 2014

a(n) is the number of unimodal rooted forests on n labeled nodes (i.e., those forests that avoid the patterns 213 and 312). - Kassie Archer, Aug 30 2018

Number of permutations of [n] where fixed points at index j are j-colored and all other points are unicolored. - Alois P. Heinz, Apr 24 2020

Links

Alois P. Heinz, Table of n, a(n) for n = 0..420

K. Anders and K. Archer, Rooted forests that avoid sets of permutations, arXiv:1607.03046 [math.CO], 2016-2017.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 119.

W. S. Gray and M. Thitsa, System Interconnections and Combinatorial Integer Sequences, in: System Theory (SSST), 2013 45th Southeastern Symposium on, Date of Conference: 11-11 March 2013, Digital Object Identifier: 10.1109/SSST.2013.6524939.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 122

Marin Knežević, Vedran Krčadinac, and Lucija Relić, Matrix products of binomial coefficients and unsigned Stirling numbers, arXiv:2012.15307 [math.CO], 2020.

A. Knopfmacher and J. N. Ridley, Reciprocal sums over partitions and compositions, SIAM J. Discrete Math. 6 (1993), no. 3, 388-399.

Chanchal Kumar and Amit Roy, Integer Sequences and Monomial Ideals, arXiv:2003.10098 [math.CO], 2020.

Formula

a(n) = Sum_{k=1..n} k! * s(n, k), s(n, k) = unsigned Stirling number of first kind; E.g.f. 1/(1+log(1-z)).

For n>0, a(n) is the permanent of the n X n matrix with entries a(i, i) = i and a(i, j) = 1 elsewhere. - Philippe Deléham, Dec 09 2003

a(n) = A052860(n)/n for n >= 1.

a(n) = n!*Sum_{k=0..n-1} a(k)/k!/(n-k) for n >= 1 with a(0)=1. - Paul D. Hanna, Jul 19 2006

E.g.f.: B(A(x)) where B(x) = 1/(1-x) and A(x) = log(1/(1-x)). - Geoffrey Critzer, Mar 18 2009

a(n) = D^n(1/(1-x)) evaluated at x = 0, where D is the operator exp(x)*d/dx. Cf. A006252. - Peter Bala, Nov 25 2011

E.g.f.: 1/(1+log(1-x)) = 1/(1 - x/(1 - x/(2 - x/(3 - 4*x/(4 - 4*x/(5 - 9*x/(6 - 9*x/(7 - 16*x/(8 - 16*x/(9 - ...)))))))))), a continued fraction. - Paul D. Hanna, Dec 31 2011

a(n) ~ n! * exp(n)/(exp(1)-1)^(n+1). - Vaclav Kotesovec, Jun 21 2013

Maple

a:= proc(n) a(n):= n!*`if`(n=0, 1, add(a(k)/(k!*(n-k)), k=0..n-1)) end:
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 06 2012

Mathematica

Table[Sum[Abs[StirlingS1[n, k]] k!, {k, 0, n}], {n, 0, 20}] (* Geoffrey Critzer, Mar 18 2009 *)

Prog

(PARI) a(n)=n!*polcoeff(1/(1+log(1-x +x*O(x^n))), n) /* Paul D. Hanna, Jul 19 2006 */
(PARI) {a(n)=local(CF=1+x*O(x)); for(k=0, n-1, CF=1/((n-k)-((n-k+1)\2)^2*x*CF)); n!*polcoeff(1/(1-x*CF), n)} /* Paul D. Hanna, Jul 19 2006 */
(Sage)
def A007840_list(len):
    f, R, C = 1, [1], [1]+[0]*len
    for n in (1..len):
        f *= n
        for k in range(n, 0, -1):
            C[k] = -C[k-1]*((k-1)/k if k>1 else 1)
        C[0] = sum((-1)^k*C[k] for k in (1..n))
        R.append(C[0]*f)
    return R
print(A007840_list(20)) # Peter Luschny, Feb 21 2016

Crossrefs

Cf. A052860. Row sums of unsigned version of A039814.

Cf. A238385, A111492.

Sequence in context: A199548 A355294 A038170 * A007549 A367973 A081005

Adjacent sequences: A007837 A007838 A007839 * A007841 A007842 A007843

Keyword

nonn

Author

Arnold Knopfmacher

Extensions

Extended June 1995

Status

approved