login
A simple grammar: rooted ordered set partitions.
18

%I #63 Feb 01 2024 12:10:04

%S 0,1,2,9,52,375,3246,32781,378344,4912515,70872610,1124723193,

%T 19471590876,365190378735,7376016877334,159620144556645,

%U 3684531055645648,90366129593683035,2346673806524446218,64325158601880061137,1856031746386568222660,56231443721132068265415

%N A simple grammar: rooted ordered set partitions.

%C Recurrence (see Mathematica line) is similar to that for Genocchi numbers A001469. - _Wouter Meeussen_, Jan 09 2001

%C Stirling transform of A024167(n) = [ 1, 1, 5, 14, 94, ...] is a(n) = [ 1, 2, 9, 52, 375, ...]. Stirling transform of a(n) = [ 0, 2, 9, 52, 375, ...] is A087301(n+1) = [ 0, 2, 3, 20, ...]. - _Michael Somos_, Mar 04 2004

%C Starting with offset 1 = the right border of triangle A208744. - _Gary W. Adamson_, Mar 05 2012

%C a(n) is the number of ordered set partitions of {1,2,...,n} such that the first block is a singleton. - _Geoffrey Critzer_, Jul 22 2013

%C Ramanujan gives a method of finding a continued fraction of the solution x of an equation 1 = x + a2*x^2 + ... and uses log(2) as the solution of 1 = x + x^2/2 + x^3/6 + ... as an example giving the sequence of simplified convergents as 0/1, 1/1, 2/3, 9/13, 52/75, 375/541, ... of which the sequence of numerators is this sequence while A000670 is the denominators. - _Michael Somos_, Jun 19 2015

%D S. Ramanujan, Notebooks, Tata Institute of Fundamental Research, Bombay 1957 Vol. 1, see page 19.

%H Vincenzo Librandi, <a href="/A052882/b052882.txt">Table of n, a(n) for n = 0..200</a>

%H Samuele Giraudo, <a href="http://arxiv.org/abs/1306.6938">Combinatorial operads from monoids</a>, arXiv preprint arXiv:1306.6938 [math.CO], 2013.

%H Jia Huang and Erkko Lehtonen, <a href="https://arxiv.org/abs/2401.15786">Associative-commutative spectra for some varieties of groupoids</a>, arXiv:2401.15786 [math.CO], 2024. See p. 14.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=855">Encyclopedia of Combinatorial Structures 855</a>

%H Srinivasa Ramanujan, <a href="http://www.imsc.res.in/~rao/ramanujan/NoteBooks/NoteBook2/chapterII/page10.htm">Notebook entry</a>

%F E.g.f.: x / (2 - exp(x)).

%F a(n) = n * A000670(n-1) if n>0.

%F a(n) = (1/2)*sum(k=0, n-1, B_k*A000629(k)*binomial(n, k)) where B_k is the k-th Bernoulli number. - _Benoit Cloitre_, Oct 19 2005

%F a(n) ~ n!/(2*(log(2))^n). - _Vaclav Kotesovec_, Aug 09 2013

%F a(0) = 0, a(1) = 1; a(n) = n! * [x^n] exp(x)*Sum_{k=1..n-1} a(k)*x^k/k!. - _Ilya Gutkovskiy_, Oct 17 2017

%e G.f. = x + 2*x^2 + 9*x^3 + 52*x^4 + 375*x^5 + 3246*x^6 + 32781*x^7 + ...

%p spec := [S,{C=Sequence(B),B=Set(Z,1 <= card),S=Prod(Z,C)},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

%p with(combinat): a:=n-> add(add(add((-1)^(k-i)*binomial(k, i)*i^(n-1), i=0..n-1), k=0..n-1), m=0..n-1): seq(a(n), n=0..20); # _Zerinvary Lajos_, Jun 03 2007

%p # next Maple program:

%p b:= proc(n, k) option remember;

%p `if`(n<1, k!, k*b(n-1, k)+b(n-1, k+1))

%p end:

%p a:= n-> b(n-1, 0)*n:

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Apr 15 2023

%t a[1] := 1; a[n_] := a[n]=Sum[ Binomial[n, m] a[ n-m], {m, 1, n-1}]

%t Range[0, 30]!* CoefficientList[Series[x/(2 - Exp[x]),{x, 0, 30}], x] (* _Vincenzo Librandi_, Dec 06 2012 *)

%t a[ n_] := If[ n < 2, Boole[n == 1], n PolyLog[ 1 - n, 1/2] / 2]; (* _Michael Somos_, Jun 19 2015 *)

%t a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ x / (2 - Exp@x), {x, 0, n}]]; (* _Michael Somos_, Jun 19 2015 *)

%t Fubini[n_, r_] := Sum[k!*Sum[(-1)^(i+k+r)*(i+r)^(n-r)/(i!*(k-i-r)!), {i, 0, k-r}], {k, r, n}]; Fubini[0, 1] = 1; a[n_] := n*Fubini[n-1, 1]; Table[ a[n], {n, 0, 18}] (* _Jean-François Alcover_, Mar 30 2016 *)

%o (PARI) {a(n) = if( n<0, 0, n! * polcoeff( subst( x / (1 - y), y, exp(x + x*O(x^n)) - 1), n))};

%o (Python)

%o from math import factorial

%o from sympy.functions.combinatorial.numbers import stirling

%o def A052882(n): return n*sum(factorial(k)*stirling(n-1,k) for k in range(n)) # _Chai Wah Wu_, Apr 15 2023

%Y Cf. A001469.

%Y Cf. A000629, A000670, A024167, A087301.

%Y Cf. A108744.

%K easy,nonn

%O 0,3

%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000