A005046
Number of partitions of a 2n-set into even blocks.
Original entry on oeis.org
1, 1, 4, 31, 379, 6556, 150349, 4373461, 156297964, 6698486371, 337789490599, 19738202807236, 1319703681935929, 99896787342523081, 8484301665702298804, 802221679220975886631, 83877585692383961052499, 9640193854278691671399436, 1211499609050804749310115589
Offset: 0
- Louis Comtet, Analyse Combinatoire Tome II, pages 61-62.
- Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 225, 3rd line of table.
- CRC Standard Mathematical Tables and Formulae, 30th ed. 1996, p. 42.
- L. B. W. Jolley, Summation of Series. 2nd ed., Dover, NY, 1961, p. 150.
- L. Lovasz, Combinatorial Problems and Exercises, North-Holland, 1993, pp. 15.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- Alois P. Heinz, Table of n, a(n) for n = 0..250 (first 51 terms from T. D. Noe)
- C. Ahmed, P. Martin, and V. Mazorchuk, On the number of principal ideals in d-tonal partition monoids, arXiv preprint arXiv:1503.06718 [math.CO], 2015-2019.
- Steven R. Finch, Moments of sums, April 23, 2004 [Cached copy, with permission of the author]
- Vladimir Victorovich Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
- J. Riordan, Letter, Jul 06 1978
- J. Shallit, Letter to N. J. A. Sloane, Jan 13 1976.
- Sebastian Volz, Design and Implementation of Efficient Algorithms for Operations on Partitions of Sets, Bachelor Thesis, Saarland Univ. (Germany, 2023). See p. 45.
See
A156289 for the table of partitions of a 2n-set into k even blocks.
-
a:= proc(n) option remember;
`if`(n=0, 1, add(binomial(2*n-1, 2*k-1) *a(n-k), k=1..n))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Apr 12 2011
# second Maple program:
a := n -> add(binomial(2*n,k)*(-1)^k*BellB(k,1/2)*BellB(2*n-k,1/2), k=0..2*n):
seq(a(n), n=0..18); # after Emanuele Munarini,_Peter Luschny_, Sep 10 2017
B := BellMatrix(n -> modp(n, 2), 31): # defined in A264428.
seq(add(k, k in B[2*n + 1]),n=0..15); # Peter Luschny, Aug 13 2019
-
NestList[ Factor[ D[#, {x, 2}]] &, Exp[ Cosh[x] - 1], 16] /. x -> 0
a[0] = 1; a[n_] := Sum[Sum[(i-k)^(2*n)*Binomial[2*k, i]*(-1)^i, {i, 0, k-1}]/(2^(k-1)*k!), {k, 1, 2*n}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Apr 07 2015, after Vladimir Kruchinin *)
Table[Sum[BellY[2 n, k, 1 - Mod[Range[2 n], 2]], {k, 0, 2 n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)
With[{nn=40},Abs[Take[CoefficientList[Series[Exp[Cos[x]-1],{x,0,nn}],x] Range[0,nn]!,{1,-1,2}]]] (* Harvey P. Dale, Feb 06 2017 *)
-
a(n):= sum(1/k!*sum(binomial(k,m)/(2^(m-1))*sum(binomial(m,j) *(2*j-m)^(2*n), j,0,m/2)*(-1)^(k-m), m,0,k), k,1,2*n); /* Vladimir Kruchinin, Aug 05 2010 */
-
a(n):=sum(sum((i-k)^(2*n)*binomial(2*k,i)*(-1)^(i),i,0,k-1)/(2^(k-1)*k!),k,1,2*n); /* Vladimir Kruchinin, Oct 04 2012 */
-
from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def a(n): return 1 if n==0 else sum(binomial(2*n - 1, 2*k - 1)*a(n - k) for k in range(1, n + 1))
print([a(n) for n in range(21)]) # Indranil Ghosh, Sep 11 2017, after Maple program by Alois P. Heinz
A008299
Triangle T(n,k) of associated Stirling numbers of second kind, n >= 2, 1 <= k <= floor(n/2).
Original entry on oeis.org
1, 1, 1, 3, 1, 10, 1, 25, 15, 1, 56, 105, 1, 119, 490, 105, 1, 246, 1918, 1260, 1, 501, 6825, 9450, 945, 1, 1012, 22935, 56980, 17325, 1, 2035, 74316, 302995, 190575, 10395, 1, 4082, 235092, 1487200, 1636635, 270270, 1, 8177, 731731, 6914908, 12122110
Offset: 2
There are 3 ways of partitioning a set N of cardinality 4 into 2 blocks each of cardinality at least 2, so T(4,2)=3.
Table begins:
1;
1;
1, 3;
1, 10;
1, 25, 15;
1, 56, 105;
1, 119, 490, 105;
1, 246, 1918, 1260;
1, 501, 6825, 9450, 945;
1, 1012, 22935, 56980, 17325;
1, 2035, 74316, 302995, 190575, 10395;
1, 4082, 235092, 1487200, 1636635, 270270;
1, 8177, 731731, 6914908, 12122110, 4099095, 135135;
...
Reading the table by diagonals produces the triangle A134991.
- L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.
- Frank Avery Haight, "Handbook of the Poisson distribution," John Wiley, 1967. See pages 6,7, but beware of errors. [Haight on page 7 gives five different ways to generate these numbers (see link)].
- J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 76.
- S. Roman, The Umbral Calculus, Dover Publications, New York (2005), pp. 129-130.
- Vincenzo Librandi and Alois P. Heinz, Rows n = 2..200, flattened (rows n = 2..104 from Vincenzo Librandi)
- Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
- Peter Bala, Diagonals of triangles with generating function exp(t*F(x)).
- J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
- J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers, Electronic Journal of Combinatorics 22(3) (2015), #P3.37.
- Fufa Beyene, Jörgen Backelin, Roberto Mantaci, and Samuel A. Fufa, Set Partitions and Other Bell Number Enumerated Objects, J. Int. Seq., Vol. 26 (2023), Article 23.1.8.
- Gilles Bonnet and Anna Gusakova, Concentration inequalities for Poisson U-statistics, arXiv:2404.16756 [math.PR], 2024. See p. 17.
- E. Rodney Canfield, J. William Helton, and Jared A. Hughes, Uniform Convergence of an Asymptotic Approximation to Associated Stirling Numbers, arXiv:2409.01489 [math.CO], 2024. See p. 12.
- Tom Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms
- Tom Copeland, Short note on Lagrange inversion
- Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus. II. A compendium of results, arXiv:2305.01100 [math.CO], 2023. See p. 3.
- Daniel W. Cranston and Chun-Hung Liu, Proper Conflict-free Coloring of Graphs with Large Maximum Degree, arXiv:2211.02818 [math.CO], 2022.
- Gesualdo Delfino and Jacopo Viti, Potts q-color field theory and scaling random cluster model, arXiv:1104.4323 [hep-th], 2011.
- Ming-Jian Ding and Jiang Zeng, Proof of an explicit formula for a series from Ramanujan's Notebooks via tree functions, arXiv:2307.00566 [math.CO], 2023.
- A. E. Fekete, Apropos two notes on notation, Amer. Math. Monthly, 101 (1994), 771-778.
- F. A. Haight, Handbook of the Poisson distribution, John Wiley, 1967 [Annotated scan of page 7 only. Note that there is an error in the table.]
- Mathematics Stack Exchange, Mahler polynomials and the zeros of the incomplete gamma function, a Mathematics Stack Exchange question by Tom Copeland, Jan 06 2016.
- R. Paris, A uniform asymptotic expansion for the incomplete gamma function, Journal of Computational and Applied Mathematics, 148 (2002), p. 223-239 (See 332. From Tom Copeland, Jan 03 2016).
- Andrew Elvey Price and Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.
- E. G. Santos, Counting non-attacking chess pieces placements: Bishops and Anassas, arXiv:2411.16492 [math.CO], 2024. See p. 2.
- L. M. Smiley, Completion of a Rational Function Sequence of Carlitz, arXiv:math/0006106 [math.CO], 2000.
- M. Z. Spivey, On Solutions to a General Combinatorial Recurrence, J. Int. Seq. 14 (2011) # 11.9.7.
- Erik Vigren and Andreas Dieckmann, A New Result in Form of Finite Triple Sums for a Series from Ramanujan’s Notebooks, Symmetry (2022) Vol. 14, No. 6, 1090.
- Eric Weisstein's World of Mathematics, Mahler polynomial
- Wikipedia, Mahler polynomials
-
A008299 := proc(n,k) local i,j,t1; if k<1 or k>floor(n/2) then t1 := 0; else
t1 := add( (-1)^i*binomial(n, i)*add( (-1)^j*(k - i - j)^(n - i)/(j!*(k - i - j)!), j = 0..k - i), i = 0..k); fi; t1; end; # N. J. A. Sloane, Dec 06 2016
G:= exp(lambda*(exp(x)-1-x)):
S:= series(G,x,21):
seq(seq(coeff(coeff(S,x,n)*n!,lambda,k),k=1..floor(n/2)),n=2..20); # Robert Israel, Jan 15 2020
T := proc(n, k) option remember; if n < 0 then return 0 fi; if k = 0 then return k^n fi; k*T(n-1, k) + (n-1)*T(n-2, k-1) end:
seq(seq(T(n,k), k=1..n/2), n=2..9); # Peter Luschny, Feb 11 2021
-
t[n_, k_] := Sum[ (-1)^i*Binomial[n, i]*Sum[ (-1)^j*(k - i - j)^(n - i)/(j!*(k - i - j)!), {j, 0, k - i}], {i, 0, k}]; Flatten[ Table[ t[n, k], {n, 2, 14}, {k, 1, Floor[n/2]}]] (* Jean-François Alcover, Oct 13 2011, after David Wasserman *)
Table[Sum[Binomial[n, k - j] StirlingS2[n - k + j, j] (-1)^(j + k), {j, 0, k}], {n, 15}, {k, n/2}] // Flatten (* Eric W. Weisstein, Nov 13 2018 *)
-
{T(n, k) = if( n < 1 || 2*k > n, n==0 && k==0, sum(i=0, k, (-1)^i * binomial( n, i) * sum(j=0, k-i, (-1)^j * (k-i-j)^(n-i) / (j! * (k-i-j)!))))}; /* Michael Somos, Oct 19 2014 */
-
{ T(n,k) = sum(i=0,min(n,k), (-1)^i * binomial(n,i) * stirling(n-i,k-i,2) ); } /* Max Alekseyev, Feb 27 2017 */
Formula and cross-references from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 14 2000
A056857
Triangle read by rows: T(n,c) = number of successive equalities in set partitions of n.
Original entry on oeis.org
1, 1, 1, 2, 2, 1, 5, 6, 3, 1, 15, 20, 12, 4, 1, 52, 75, 50, 20, 5, 1, 203, 312, 225, 100, 30, 6, 1, 877, 1421, 1092, 525, 175, 42, 7, 1, 4140, 7016, 5684, 2912, 1050, 280, 56, 8, 1, 21147, 37260, 31572, 17052, 6552, 1890, 420, 72, 9, 1, 115975, 211470, 186300, 105240, 42630, 13104, 3150, 600, 90, 10, 1
Offset: 1
Winston C. Yang (winston(AT)cs.wisc.edu), Aug 31 2000
For example {1, 2, 1, 2, 2, 3} is a set partition of {1, 2, 3, 4, 5, 6} and has 1 successive equality, at i = 4.
Triangle begins:
1;
1, 1;
2, 2, 1;
5, 6, 3, 1;
15, 20, 12, 4, 1;
52, 75, 50, 20, 5, 1;
203, 312, 225, 100, 30, 6, 1;
...
From _Paul Barry_, Apr 23 2009: (Start)
Production matrix is
1, 1;
1, 1, 1;
1, 2, 1, 1;
1, 3, 3, 1, 1;
1, 4, 6, 4, 1, 1;
1, 5, 10, 10, 5, 1, 1;
1, 6, 15, 20, 15, 6, 1, 1;
1, 7, 21, 35, 35, 21, 7, 1, 1;
1, 8, 28, 56, 70, 56, 28, 8, 1, 1; ... (End)
- W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [Apparently unpublished]
- Alois P. Heinz, Rows n = 1..141, flattened
- H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. See Table III.
- H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. [Annotated scanned copy]
- Fufa Beyene, Jörgen Backelin, Roberto Mantaci, and Samuel A. Fufa, Set Partitions and Other Bell Number Enumerated Objects, J. Int. Seq., Vol. 26 (2023), Article 23.1.8.
- A. Hennessy and Paul Barry, Generalized Stirling Numbers, Exponential Riordan Arrays, and Orthogonal Polynomials, J. Int. Seq. 14 (2011) # 11.8.2, Corollary 17.
- G. Hurst and A. Schultz, An elementary (number theory) proof of Touchard's congruence, arXiv:0906.0696v2 [math.CO], 2009.
- A. O. Munagi, Set partitions with successions and separations, Intl. J. Math. Math. Sci. 2005 (2005) 451-463.
- M. Spivey, A generalized recurrence for Bell numbers, J. Int. Seq., 11 (2008), no. 2, Article 08.2.5
- W. Yang, Bell numbers and k-trees, Disc. Math. 156 (1996) 247-252.
-
with(combinat): A056857:=(n,c)->binomial(n-1,c)*bell(n-1-c): for n from 1 to 11 do seq(A056857(n,c),c=0..n-1) od; # yields sequence in triangular form; Emeric Deutsch, Nov 10 2006
with(linalg): # Yields sequence in matrix form:
A056857_matrix := n -> subs(exp(1)=1, exponential(exponential(
matrix(n,n,[seq(seq(`if`(j=k+1,j,0),k=0..n-1),j=0..n-1)])))):
A056857_matrix(8); # Peter Luschny, Apr 18 2011
-
t[n_, k_] := BellB[n-1-k]*Binomial[n-1, k]; Flatten[ Table[t[n, k], {n, 1, 11}, {k, 0, n-1}]](* Jean-François Alcover, Apr 25 2012, after Emeric Deutsch *)
-
B(n) = sum(k=0, n, stirling(n, k, 2));
tabl(nn)={for(n=1, nn, for(k=0, n - 1, print1(B(n - 1 - k) * binomial(n - 1, k),", ");); print(););};
tabl(12); \\ Indranil Ghosh, Mar 19 2017
-
from sympy import bell, binomial
for n in range(1,12):
print([bell(n - 1 - k) * binomial(n - 1, k) for k in range(n)]) # Indranil Ghosh, Mar 19 2017
-
def a(n): return (-1)^n / factorial(n)
@cached_function
def p(n, m):
R = PolynomialRing(QQ, "x")
if n == 0: return R(a(m))
return R((m + x)*p(n - 1, m) - (m + 1)*p(n - 1, m + 1))
for n in range(11): print(p(n, 0).list()) # Peter Luschny, Jun 18 2023
A003436
Number of inequivalent labeled Hamiltonian circuits on n-octahedron. Interlacing chords joining 2n points on circle.
Original entry on oeis.org
1, 0, 1, 4, 31, 293, 3326, 44189, 673471, 11588884, 222304897, 4704612119, 108897613826, 2737023412199, 74236203425281, 2161288643251828, 67228358271588991, 2225173863019549229, 78087247031912850686, 2896042595237791161749, 113184512236563589997407
Offset: 0
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- Vincenzo Librandi, Table of n, a(n) for n = 0..200
- F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994
- Kenneth P. Bogart and Peter G. Doyle, Nonsexist solution of the menage problem, Amer. Math. Monthly 93:7 (1986), 514-519.
- Robert Cori and G. Hetyei, Counting partitions of a fixed genus, arXiv preprint arXiv:1710.09992 [math.CO], 2017.
- M. Hazewinkel and V. V. Kalashnikov, Counting Interlacing Pairs on the Circle, CWI report AM-R9508 (1995)
- Evgeniy Krasko, Igor Labutin, and Alexander Omelchenko, Enumeration of Labelled and Unlabelled Hamiltonian Cycles in Complete k-partite Graphs, arXiv:1709.03218 [math.CO], 2017.
- E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, arXiv preprint arXiv:1601.05073 [math.CO], 2016.
- E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, The Electronic Journal of Combinatorics, 24(3) (2017), #P3.43.
- D. Singmaster, Hamiltonian circuits on the n-dimensional octahedron, J. Combinatorial Theory Ser. B 19 (1975), no. 1, 1-4.
- Gus Wiseman, The a(5) = 293 interlacing chord diagrams.
Cf.
A000179,
A000296,
A000699,
A001147,
A005493,
A170941,
A190823,
A278990,
A306386,
A306419,
A322402,
A324011,
A324172,
A324173.
-
A003436 := proc(n) local k;
if n = 0 then 1
elif n = 1 then 0
else add( (-1)^k*binomial(n,k)*2*n/(2*n-k)*2^k*(2*n-k)!/2^n/n!,k=0..n) ;
end if;
end proc: # R. J. Mathar, Dec 11 2013
A003436 := n-> `if`(n<2, 1-n, (-1)^n*2*hypergeom([n, -n], [], 1/2)):
seq(simplify(A003436(n)), n=0..18); # Peter Luschny, Nov 10 2016
-
a[n_] := (2*n-1)!! * Hypergeometric1F1[-n, 1-2*n, -2]; a[1] = 0;
Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Apr 05 2013 *)
twounifll[{}]:={{}};twounifll[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@twounifll[Complement[set,s]]]/@Table[{i,j},{j,If[i==1,Select[set,2<#i+1&]]}];
Table[Length[twounifll[Range[n]]],{n,0,14,2}] (* Gus Wiseman, Feb 27 2019 *)
A052848
Number of ordered set partitions with a designated element in each block and no block containing less than two elements.
Original entry on oeis.org
1, 0, 2, 3, 28, 125, 1146, 8827, 94200, 1007001, 12814390, 172114151, 2584755636, 41436880069, 721702509906, 13397081295795, 266105607506416, 5605474012933169, 125164378600050798, 2948082261121889983, 73122068527848758700, 1903894649651935410141
Offset: 0
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
-
spec := [S,{B=Prod(Z,C),C=Set(Z,1 <= card),S=Sequence(B)},labeled]: seq(combstruct[count](spec, size=n), n=0..20);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1,
add(a(n-j)*binomial(n, j)*j, j=2..n))
end:
seq(a(n), n=0..25); # Alois P. Heinz, May 11 2016
-
nn=20; a=x Exp[x]; First[Range[0,nn]! CoefficientList[Series[1/(1-x (Exp[x]-1+y)), {x,0,nn}], {y,x}]] Range[0,nn]! (* Geoffrey Critzer, Dec 07 2012 *)
-
a(n):=n!*sum((k!*stirling2(n-k,k))/(n-k)!,k,0,n/2); /* Vladimir Kruchinin, Nov 16 2011 */
A169985
Round phi^n to the nearest integer.
Original entry on oeis.org
1, 2, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803
Offset: 0
a(4) = 7 because we have: {}, {1}, {2}, {3}, {4}, {1,3}, {2,4}. - _Geoffrey Critzer_, Sep 23 2013
- Danny Rorabaugh, Table of n, a(n) for n = 0..4000
- John Machacek and George D. Nasr, Transversal and Paving Positroids, arXiv:2401.02053 [math.CO], 2024. See p. 23.
- Shaoxiong (Steven) Yuan, Generalized Identities of Certain Continued Fractions, arXiv:1907.12459 [math.NT], 2019.
- Index entries for linear recurrences with constant coefficients, signature (1,1).
-
Concatenation([1,2], List([2..40], n-> Lucas(1,-1,n)[2] )); # G. C. Greubel, Jul 09 2019
-
[Round(Sqrt(Fibonacci(2*n) + 2*Fibonacci(2*n-1))): n in [0..40]]; // Vincenzo Librandi, Apr 16 2015
-
nn=34; CoefficientList[Series[(1+x-x^3)/(1-x-x^2),{x,0,nn}],x] (* Geoffrey Critzer, Sep 23 2013 *)
Round[GoldenRatio^Range[0,40]] (* Harvey P. Dale, Jul 13 2014 *)
Table[If[n<=1, n+1, LucasL[n]], {n, 0, 40}] (* G. C. Greubel, Jul 09 2019 *)
-
my(x='x+O('x^40)); Vec((1+x-x^3)/(1-x-x^2)) \\ G. C. Greubel, Feb 13 2019
-
from gmpy2 import isqrt, fib2
def A169985(n): return int((m:=isqrt(k:=(lambda x:(x[1]<<1)+x[0])(fib2(n<<1))))+(k-m*(m+1)>=1)) # Chai Wah Wu, Jun 19 2024
-
[round(golden_ratio^n) for n in range(40)] # Danny Rorabaugh, Apr 16 2015
A097514
Number of partitions of an n-set without blocks of size 2.
Original entry on oeis.org
1, 1, 1, 2, 6, 17, 53, 205, 871, 3876, 18820, 99585, 558847, 3313117, 20825145, 138046940, 959298572, 6974868139, 52972352923, 419104459913, 3446343893607, 29405917751526, 259930518212766, 2376498296500063, 22441988298860757, 218615700758838253
Offset: 0
-
g:=exp(exp(x)-1-x^2/2): gser:=series(g,x=0,31): 1,seq(n!*coeff(gser,x^n),n=1..29); # Emeric Deutsch, Nov 18 2004
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(`if`(
j=2, 0, a(n-j)*binomial(n-1, j-1)), j=1..n))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Mar 18 2015
-
a[n_] := a[n] = If[n == 0, 1, Sum[If[j == 2, 0, a[n-j]*Binomial[n-1, j-1]], {j, 1, n}]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 13 2015, after Alois P. Heinz *)
A124323
Triangle read by rows: T(n,k) is the number of partitions of an n-set having k singleton blocks (0<=k<=n).
Original entry on oeis.org
1, 0, 1, 1, 0, 1, 1, 3, 0, 1, 4, 4, 6, 0, 1, 11, 20, 10, 10, 0, 1, 41, 66, 60, 20, 15, 0, 1, 162, 287, 231, 140, 35, 21, 0, 1, 715, 1296, 1148, 616, 280, 56, 28, 0, 1, 3425, 6435, 5832, 3444, 1386, 504, 84, 36, 0, 1, 17722, 34250, 32175, 19440, 8610, 2772, 840, 120, 45, 0, 1
Offset: 0
T(4,2)=6 because we have 12|3|4, 13|2|4, 14|2|3, 1|23|4, 1|24|3 and 1|2|34 (if we take {1,2,3,4} as our 4-set).
Triangle starts:
1
0 1
1 0 1
1 3 0 1
4 4 6 0 1
11 20 10 10 0 1
41 66 60 20 15 0 1
162 287 231 140 35 21 0 1
715 1296 1148 616 280 56 28 0 1
3425 6435 5832 3444 1386 504 84 36 0 1
From _Gus Wiseman_, Feb 13 2019: (Start)
Row n = 5 counts the following set partitions by number of singletons:
{{1234}} {{1}{234}} {{1}{2}{34}} {{1}{2}{3}{4}}
{{12}{34}} {{123}{4}} {{1}{23}{4}}
{{13}{24}} {{124}{3}} {{12}{3}{4}}
{{14}{23}} {{134}{2}} {{1}{24}{3}}
{{13}{2}{4}}
{{14}{2}{3}}
... and the following set partitions by number of cyclical adjacencies:
{{13}{24}} {{1}{2}{34}} {{1}{234}} {{1234}}
{{1}{24}{3}} {{1}{23}{4}} {{12}{34}}
{{13}{2}{4}} {{12}{3}{4}} {{123}{4}}
{{1}{2}{3}{4}} {{14}{2}{3}} {{124}{3}}
{{134}{2}}
{{14}{23}}
(End)
From _Paul Barry_, Apr 23 2009: (Start)
Production matrix is
0, 1,
1, 0, 1,
1, 2, 0, 1,
1, 3, 3, 0, 1,
1, 4, 6, 4, 0, 1,
1, 5, 10, 10, 5, 0, 1,
1, 6, 15, 20, 15, 6, 0, 1,
1, 7, 21, 35, 35, 21, 7, 0, 1,
1, 8, 28, 56, 70, 56, 28, 8, 0, 1 (End)
- Alois P. Heinz, Rows n = 0..140, flattened
- David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.
- T. Mansour, A. O. Munagi, Set partitions with circular successions, European Journal of Combinatorics, 42 (2014), 207-216.
A250104 is an essentially identical triangle, differing only in row 1.
Cf.
A000126,
A001610,
A032032,
A052841,
A066982,
A080107,
A169985,
A187784,
A324011,
A324014,
A324015.
-
G:=exp(exp(z)-1+(t-1)*z): Gser:=simplify(series(G,z=0,14)): for n from 0 to 11 do P[n]:=sort(n!*coeff(Gser,z,n)) od: for n from 0 to 11 do seq(coeff(P[n],t,k),k=0..n) od; # yields sequence in triangular form
# Program from R. J. Mathar, Jan 22 2015:
A124323 := proc(n,k)
binomial(n,k)*A000296(n-k) ;
end proc:
-
Flatten[CoefficientList[Range[0,10]! CoefficientList[Series[Exp[x y] Exp[Exp[x] - x - 1], {x, 0,10}], x], y]] (* Geoffrey Critzer, Nov 24 2011 *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],Count[#,{}]==k&]],{n,0,9},{k,0,n}] (* _Gus Wiseman, Feb 13 2019 *)
A293037
E.g.f.: exp(1 + x - exp(x)).
Original entry on oeis.org
1, 0, -1, -1, 2, 9, 9, -50, -267, -413, 2180, 17731, 50533, -110176, -1966797, -9938669, -8638718, 278475061, 2540956509, 9816860358, -27172288399, -725503033401, -5592543175252, -15823587507881, 168392610536153, 2848115497132448, 20819319685262839
Offset: 0
-
f:= series(exp(1 + x - exp(x)), x= 0, 101): seq(factorial(n) * coeff(f, x, n), n = 0..30); # Muniru A Asiru, Oct 31 2017
# second Maple program:
b:= proc(n, t) option remember; `if`(n=0, 1-2*t,
add(b(n-j, 1-t)*binomial(n-1, j-1), j=1..n))
end:
a:= n-> b(n+1, 1):
seq(a(n), n=0..35); # Alois P. Heinz, Dec 01 2021
-
m = 26; Range[0, m]! * CoefficientList[Series[Exp[1 + x - Exp[x]], {x, 0, m}], x] (* Amiram Eldar, Jul 06 2020 *)
Table[Sum[Binomial[n, k] * BellB[k, -1], {k, 0, n}], {n, 0, 30}] (* Vaclav Kotesovec, Jul 06 2020 *)
-
my(N=40, x='x+O('x^N)); Vec(serlaplace(exp(-exp(x)+1+x)))
-
a(n) = if(n==0, 1, -sum(k=0, n-2, binomial(n-1, k)*a(k))); \\ Seiichi Manyama, Aug 02 2021
A080107
Number of fixed points of permutation of SetPartitions under {1,2,...,n}->{n,n-1,...,1}. Number of symmetric arrangements of non-attacking rooks on upper half of n X n chessboard.
Original entry on oeis.org
1, 1, 2, 3, 7, 12, 31, 59, 164, 339, 999, 2210, 6841, 16033, 51790, 127643, 428131, 1103372, 3827967, 10269643, 36738144, 102225363, 376118747, 1082190554, 4086419601, 12126858113, 46910207114, 143268057587, 566845074703, 1778283994284, 7186474088735
Offset: 0
Of the set partitions of 4, the following 7 are invariant under 1->4, 2->3, 3->2, 4->1: {{1,2,3,4}}, {{1,2},{3,4}}, {{1,4},{2,3}}, {{1,3},{2,4}}, {{1},{2,3},{4}}, {{1,4},{2},{3}}, {{1},{2},{3},{4}}, so a(4)=7.
For a(4)=7, the row patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD (same as previous example). The loop patterns are AAAA, AAAB, AABB, AABC, ABAB, ABAC, and ABCD. - _Robert A. Russell_, Apr 23 2018
From _Gus Wiseman_, Feb 13 2019: (Start)
The a(1) = 1 through a(5) = 12 self-complementary set partitions:
{{1}} {{12}} {{123}} {{1234}} {{12345}}
{{1}{2}} {{13}{2}} {{12}{34}} {{1245}{3}}
{{1}{2}{3}} {{13}{24}} {{135}{24}}
{{14}{23}} {{15}{234}}
{{1}{23}{4}} {{1}{234}{5}}
{{14}{2}{3}} {{12}{3}{45}}
{{1}{2}{3}{4}} {{135}{2}{4}}
{{14}{25}{3}}
{{15}{24}{3}}
{{1}{24}{3}{5}}
{{15}{2}{3}{4}}
{{1}{2}{3}{4}{5}}
(End)
- D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 765).
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
- Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, Combinatorial Identities for Vacillating Tableaux, arXiv:2308.14183 [math.CO], 2023. See p. 18.
- David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.
- Juan B. Gil and Luiz E. Lopez, Enumeration of symmetric arc diagrams, arXiv:2203.10589 [math.CO], 2022.
- S. V. Pemmaraju and S. S. Skiena, The New Combinatorica, 2001.
- Frank Ruskey, Set Partitions
-
< Range[n, 1, -1]]; t= 1 + RankSetPartition /@ t; t= ToCycles[t]; t= Cases[t, {_Integer}]; Length[t], {n, 7}]
(* second program: *)
QB[n_, q_] := QB[n, q] = Sum[QB[j, q] QBinomial[n-1, j, q], {j, 0, n-1}] // FunctionExpand // Simplify; QB[0, q_]=1; QB[1, q_]=1; Table[cc = CoefficientList[QB[n, q], q]; cc.Table[(-1)^(k+1), {k, 1, Length[cc]}], {n, 0, 30}] (* Jean-François Alcover, Feb 29 2016, after Paul D. Hanna *)
(* Ach[n, k] is the number of achiral color patterns for a row or loop of n
colors containing exactly k different colors *)
Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0],
k Ach[n-2, k] + Ach[n-2, k-1] + Ach[n-2, k-2]]
Table[Sum[Ach[n, k], {k, 0, n}], {n, 0, 30}] (* Robert A. Russell, Apr 23 2018 *)
x[n_] := x[n] = If[n < 2, n+1, 2x[n-1] + (n-1)x[n-2]]; (* A005425 *)
Table[Sum[StirlingS2[Ceiling[n/2], k] x[k-Mod[n, 2]], {k, 0, Ceiling[n/2]}],
{n, 0, 30}] (* Robert A. Russell, Apr 27 2018, after Knuth reference *)
Comments