OFFSET
0,3
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
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.
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)
EXAMPLE
a(4) = 47 = 1*24 + 1*6 + 3*2 + 11*1.
a(4) = 47, the upper left term of M^4.
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 *)
PROG
(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
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
EXTENSIONS
Entry revised by David Callan, Sep 20 2007
STATUS
approved