A051296 INVERT transform of factorial numbers.

1, 1, 3, 11, 47, 231, 1303, 8431, 62391, 524495, 4960775, 52223775, 605595319, 7664578639, 105046841127, 1548880173119, 24434511267863, 410503693136559, 7315133279097607, 137787834979031839, 2734998201208351479, 57053644562104430735, 1247772806059088954855

Offset: 0

Author

Leroy Quet

Keywords

• easy
• nonn

Comments

a(n) = Sum[ a1!a2!...ak! ] where (a1,a2,...,ak) ranges over all compositions of n. a(n) = number of trees on [0,n] rooted at 0, consisting entirely of filaments and such that the non-root labels on each filament, when arranged in order, form an interval of integers. A filament is a maximal path (directed away from the root) whose interior vertices all have outdegree 1 and which terminates at a leaf. For example with n=3, a(n) = 11 counts all n^(n-2) = 16 trees on [0,3] except the 3 trees {0->1, 1->2, 1->3}, {0->2, 2->1, 2->3}, {0->3, 3->1, 3->2} (they fail the all-filaments test) and the 2 trees {0->2, 0->3, 3->1}, {0->2, 0->1, 1->3} (they fail the interval-of-integers test). - David Callan, Oct 24 2004

a(n) is the number of lists of "unlabeled" permutations whose total length is n. "Unlabeled" means each permutation is on an initial segment of the positive integers (cf. A090238). Example: with dashes separating permutations, a(3) = 11 counts 123, 132, 213, 231, 312, 321, 1-12, 1-21, 12-1, 21-1, 1-1-1. - David Callan, Sep 20 2007

Number of compositions of n where there are k! sorts of part k. - Joerg Arndt, Aug 04 2014

Examples

			a(4) = 47 = 1*24 + 1*6 + 3*2 + 11*1.
a(4) = 47, the upper left term of M^4.
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974.

Links

• Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..440 (first 200 terms from Alois P. Heinz)
• Jean-Paul Bultel, Ali Chouria, Jean-Gabriel Luque, and Olivier Mallet, Word symmetric functions and the Redfield-Polya theorem, hal-00793788, 2013.
• Louis Comtet, Sur les coefficients de l'inverse de la série formelle Sum n! t^n, Comptes Rend. Acad. Sci. Paris, A 275 (1972), 569-572.
• Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, Catalan-Spitzer permutations, arXiv:2310.06288 [math.CO], 2023. See p. 20.
• Richard J. Martin, and Michael J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica: 35:3 (2015), 309-315.
• Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 7.

Crossrefs

Cf. A051295, row sums of A090238.

Cf. A000142, A292778.

Programs

Maple

a:= proc(n) option remember; `if`(n<1, 1,
      add(a(n-i)*factorial(i), i=1..n))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jul 28 2015

Mathematica

CoefficientList[Series[Sum[Sum[k!*x^k, {k, 1, 20}]^n, {n, 0, 20}], {x, 0, 20}], x] (* Geoffrey Critzer, Mar 22 2009 *)

Sage

h = lambda x: 1/(1-x*hypergeometric((1, 2), (), x))
taylor(h(x),x,0,22).list() # Peter Luschny, Jul 28 2015

Sage

def A051296_list(len):
    R, C = [1], [1]+[0]*(len-1)
    for n in (1..len-1):
        for k in range(n, 0, -1):
            C[k] = C[k-1] * k
        C[0] = sum(C[k] for k in (1..n))
        R.append(C[0])
    return R
print(A051296_list(23)) # Peter Luschny, Feb 21 2016

Formula

G.f.: 1/(1-Sum_{n>=1} n!*x^n).

a(0) = 1; a(n) = Sum_{k=1..n} a(n-k)*k! for n>0.

a(n) = Sum_{k>=0} A090238(n, k). - Philippe Deléham, Feb 05 2004

From Gary W. Adamson, Sep 26 2011: (Start)

a(n) is the upper left term of M^n, M = an infinite square production matrix as follows:

1, 1, 0, 0, 0, 0, ...

2, 0, 2, 0, 0, 0, ...

3, 0, 0, 3, 0, 0, ...

4, 0, 0, 0, 4, 0, ...

5, 0, 0, 0, 0, 5, ...

... (End)

G.f.: 1 + x/(G(0) - 2*x) where G(k) = 1 + (k+1)*x - x*(k+2)/G(k+1); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 26 2012

a(n) ~ n! * (1 + 2/n + 7/n^2 + 35/n^3 + 216/n^4 + 1575/n^5 + 13243/n^6 + 126508/n^7 + 1359437/n^8 + 16312915/n^9 + 217277446/n^10), for coefficients see A260530. - Vaclav Kotesovec, Jul 28 2015

From Peter Bala, May 26 2017: (Start)

G.f. as an S-fraction: A(x) = 1/(1 - x/(1 - 2*x/(1 - x/(1 - 3*x/(1 - 2*x/(1 - 4*x/(1 - 3*x/(1 - n*x/(1 - (n - 1)*x/(1 - ...)))))))))). Cf. S-fraction for the o.g.f. of A000142.

A(x) = 1/(1 - x/(1 - x - x/(1 - 2*x/(1 - 2*x/(1 - 3*x/(1 - 3*x/(1 - 4*x/(1 - 4*x/(1 - ... ))))))))). (End)

Extensions

Entry revised by David Callan, Sep 20 2007