A000296 -id:A000296 - cp's OEIS frontend

A324013 Number of self-complementary set partitions of {1, ..., n} with no singletons.

1, 0, 1, 1, 4, 3, 15, 16, 75, 89, 428, 571, 2781, 4060, 20093, 31697, 159340, 268791, 1372163, 2455804, 12725447, 24012697, 126238060, 249880687, 1332071241, 2754348360, 14881206473, 32029000641, 175297058228, 391548016475, 2169832010759

Offset: 0

Gus Wiseman, Feb 12 2019

nonn

The complement of a set partition pi of {1, ..., n} is defined as n + 1 - pi (elementwise) on page 3 of Callan. For example, the complement of {{1,5},{2},{3,6},{4}} is {{1,4},{2,6},{3},{5}}.

			The  a(3) = 1 through a(6) = 15 self-complementary set partitions with no singletons:
  {{123}}  {{1234}}    {{12345}}    {{123456}}
           {{12}{34}}  {{135}{24}}  {{123}{456}}
           {{13}{24}}  {{15}{234}}  {{124}{356}}
           {{14}{23}}               {{1256}{34}}
                                    {{1346}{25}}
                                    {{135}{246}}
                                    {{145}{236}}
                                    {{16}{2345}}
                                    {{12}{34}{56}}
                                    {{13}{25}{46}}
                                    {{14}{25}{36}}
                                    {{15}{26}{34}}
                                    {{16}{23}{45}}
                                    {{16}{24}{35}}
                                    {{16}{25}{34}}

Andrew Howroyd, Table of n, a(n) for n = 0..500
David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.

Cf. A000110, A000296, A080107 (self-complementary), A086365, A124323, A324012 (self-conjugate).

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
cmp[stn_]:=Union[Sort[Max@@Join@@stn+1-#]&/@stn];
Table[Select[sps[Range[n]],And[cmp[#]==Sort[#],Count[#,{_}]==0]&]//Length,{n,0,10}]

seq(n)={my(x=x+O(x*x^(n\2)), p=exp((exp(2*x)-3)/2-x+exp(x)), q=(exp(x)-1)*p); vector(n+1, n, my(c=(n-1)\2); c!*polcoef(if(n%2, p, q), c))} \\ Andrew Howroyd, Feb 16 2022

From Andrew Howroyd, Feb 16 2022: (Start)
a(2*n) = A086365(n-1) for n > 0.
a(2*n) = n!*[x^n] exp((exp(2*x) - 3)/2 - x + exp(x));
a(2*n+1) = n!*[x^n] (exp(x) - 1)*exp((exp(2*x) - 3)/2 - x + exp(x)).
(End)

Terms a(13) and beyond from Andrew Howroyd, Feb 16 2022

A335867 a(n) = exp(-n) * Sum_{k>=0} n^k * (k - 1)^n / k!.

Original entry on oeis.org

1, 0, 3, 29, 397, 6879, 144751, 3587100, 102351929, 3305310065, 119186370091, 4746969337923, 206966647324933, 9804683604806908, 501491905963040903, 27544070654283355889, 1616869985889305862385, 101020181695996141703335, 6693303018177050431484035, 468770856837303230888704208

Offset: 0

Ilya Gutkovskiy, Jun 27 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Bell Polynomial

Cf. A000296, A217924, A242817, A334240, A335868.

Table[n! SeriesCoefficient[Exp[n (Exp[x] - 1) - x], {x, 0, n}], {n, 0, 19}]
Table[Sum[(-1)^(n - k) Binomial[n, k] BellB[k, n], {k, 0, n}], {n, 0, 19}]

a(n) = n! * [x^n] exp(n*(exp(x) - 1) - x).

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n,k) * BellPolynomial_k(n).

A361781 A(n,k) is the n-th term of the k-th inverse binomial transform of the Bell numbers (A000110); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 0, 2, 1, -1, 1, 5, 1, -2, 2, 1, 15, 1, -3, 5, -3, 4, 52, 1, -4, 10, -13, 7, 11, 203, 1, -5, 17, -35, 36, -10, 41, 877, 1, -6, 26, -75, 127, -101, 31, 162, 4140, 1, -7, 37, -139, 340, -472, 293, -21, 715, 21147, 1, -8, 50, -233, 759, -1573, 1787, -848, 204, 3425, 115975

Offset: 0

Alois P. Heinz, Mar 23 2023

			Square array A(n,k) begins:
    1,   1,   1,    1,     1,      1,       1,       1, ...
    1,   0,  -1,   -2,    -3,     -4,      -5,      -6, ...
    2,   1,   2,    5,    10,     17,      26,      37, ...
    5,   1,  -3,  -13,   -35,    -75,    -139,    -233, ...
   15,   4,   7,   36,   127,    340,     759,    1492, ...
   52,  11, -10, -101,  -472,  -1573,   -4214,   -9685, ...
  203,  41,  31,  293,  1787,   7393,   23711,   63581, ...
  877, 162, -21, -848, -6855, -35178, -134873, -421356, ...

Alois P. Heinz, Antidiagonals n = 0..150, flattened

Columns k=0-5 give: A000110, A000296, A126617, A346738, A346739, A346740.
Rows n=0-2 give: A000012, A024000, A160457.
Main diagonal gives A290219.
Antidiagonal sums give A361380.
Cf. A108087.

T:= func< n,k | (&+[(-k)^j*Binomial(n,j)*Bell(n-j): j in [0..n]]) >;
A361781:= func< n,k | T(k, n-k) >;
[A361781(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jun 12 2024

A:= proc(n, k) option remember; uses combinat;
      add(binomial(n, j)*(-k)^j*bell(n-j), j=0..n)
    end:
seq(seq(A(n, d-n), n=0..d), d=0..10);
# second Maple program:
b:= proc(n, m) option remember;
     `if`(n=0, 1, b(n-1, m+1)+m*b(n-1, m))
    end:
A:= (n, k)-> b(n, -k):
seq(seq(A(n, d-n), n=0..d), d=0..10);

T[n_, k_]:= T[n, k]= If[k==0, BellB[n], Sum[(-k)^j*Binomial[n,j]*BellB[n-j], {j,0,n}]];
A361781[n_, k_]= T[k, n-k];
Table[A361781[n,k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Jun 12 2024 *)

def T(n,k): return sum( (-k)^j*binomial(n,j)*bell_number(n-j) for j in range(n+1))
def A361781(n, k): return T(k, n-k)
flatten([[A361781(n, k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Jun 12 2024

E.g.f. of column k: exp(exp(x) - k*x - 1).

A(n,k) = Sum_{j=0..n} (-k)^j*binomial(n,j)*Bell(n-j).

A367785 Expansion of e.g.f. exp(exp(3*x) - x - 1).

Original entry on oeis.org

1, 2, 13, 89, 772, 7745, 87949, 1109288, 15332539, 229840361, 3706130914, 63857565095, 1169261937973, 22646779177898, 462143532144937, 9902312863237637, 222119823632283628, 5202170552214520637, 126914730275907871201, 3218552632981994910248, 84686139239808135094879, 2307953474037054591248501

Offset: 0

Ilya Gutkovskiy, Nov 30 2023

nonn

Cf. A000110, A000296, A124311, A247452, A284859, A284860, A330605, A367744, A367786.

nmax = 21; CoefficientList[Series[Exp[Exp[3 x] - x - 1], {x, 0, nmax}], x] Range[0, nmax]!
a[0] = 1; a[n_] := a[n] = -a[n - 1] + Sum[Binomial[n - 1, k - 1] 3^k a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 21}]
Table[Sum[(-1)^(n - k) Binomial[n, k] 3^k BellB[k], {k, 0, n}], {n, 0, 21}]

my(x='x+O('x^30)); Vec(serlaplace(exp(exp(3*x) - x - 1))) \\ Michel Marcus, Nov 30 2023

a(n) = exp(-1) * Sum_{k>=0} (3*k-1)^n / k!.
a(0) = 1; a(n) = -a(n-1) + Sum_{k=1..n} binomial(n-1,k-1) * 3^k * a(n-k).
a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n,k) * 3^k * Bell(k).

A370945 Number T(n,k) of partitions of [n] whose singletons sum to k; triangle T(n,k), n>=0, 0<=k<=A000217(n), read by rows.

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 4, 1, 1, 2, 2, 2, 1, 1, 0, 0, 1, 11, 4, 4, 5, 5, 6, 3, 3, 3, 3, 2, 1, 1, 0, 0, 1, 41, 11, 11, 15, 15, 19, 20, 13, 10, 11, 8, 8, 5, 4, 4, 3, 2, 1, 1, 0, 0, 1, 162, 41, 41, 52, 52, 63, 67, 78, 41, 45, 39, 39, 33, 30, 20, 17, 14, 10, 10, 6, 5, 4, 3, 2, 1, 1, 0, 0, 1

Offset: 0

Alois P. Heinz, Mar 06 2024

			T(4,0) = 4: 1234, 12|34, 13|24, 14|23.
T(4,1) = 1: 1|234.
T(4,2) = 1: 134|2.
T(4,3) = 2: 124|3, 1|2|34.
T(4,4) = 2: 123|4, 1|24|3.
T(4,5) = 2: 1|23|4, 14|2|3.
T(4,6) = 1: 13|2|4.
T(4,7) = 1: 12|3|4.
T(4,10) = 1: 1|2|3|4.
Triangle T(n,k) begins:
   1;
   0, 1;
   1, 0, 0, 1;
   1, 1, 1, 1, 0, 0, 1;
   4, 1, 1, 2, 2, 2, 1, 1, 0, 0, 1;
  11, 4, 4, 5, 5, 6, 3, 3, 3, 3, 2, 1, 1, 0, 0, 1;
  ...

Alois P. Heinz, Rows n = 0..50, flattened
Wikipedia, Partition of a set

Column k=0 gives A000296.
Row sums give A000110.
Row lengths give A000124.
Reversed rows converge to A370946.
T(n,n) gives A370947.
Cf. A000217, A053632, A105479, A369596.

h:= proc(n) option remember; `if`(n=0, 1,
      add(h(n-j)*binomial(n-1, j-1), j=2..n))
    end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, h(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
    end:
T:= (n, k)-> b(k, min(n, k), n):
seq(seq(T(n, k), k=0..n*(n+1)/2), n=0..7);

h[n_] := h[n] = If[n == 0, 1,
    Sum[h[n-j]*Binomial[n-1, j-1], {j, 2, n}]];
b[n_, i_, m_] := b[n, i, m] = If[n > i*(i + 1)/2, 0,
    If[n == 0, h[m], b[n, i - 1, m] + b[n - i, Min[n - i, i - 1], m - 1]]];
T[n_, k_] := b[k, Min[n, k], n];
Table[Table[T[n, k], { k, 0, n*(n + 1)/2}], {n, 0, 7}] // Flatten (* Jean-François Alcover, Mar 12 2024, after Alois P. Heinz *)

Sum_{k=0..A000217(n)} k * T(n,k) = A105479(n+1).
T(n,A161680(n)) = A370946(n).
T(n,A000217(n)) = 1.

A097762 Number of different partitions of the set {1, 2, ..., n} into an odd number of blocks such that each block contains at least 2 elements.

Original entry on oeis.org

0, 1, 1, 1, 1, 16, 106, 491, 1919, 7771, 40261, 264892, 1871728, 12988977, 88413417, 612354549, 4492798353, 35529920764, 299329573882, 2625719242667, 23612697535919, 216981233646783, 2047084700918445, 19952633715109592

Offset: 1

Isabel C. Lugo (izzycat(AT)gmail.com), Aug 23 2004

			a(6)=16 since we can partition a set of six labeled elements into one non-singleton block in 1 way and into three non-singleton blocks (each necessarily of size 2) in 15 ways; thus a(6) = 1+15 = 16.

Alois P. Heinz, Table of n, a(n) for n = 1..500

Cf. A000296, A097763.

seq(coeff(series(sinh(exp(x)-x-1),x=0,25),x^i)*i!, i=1..24);
# second Maple program:
with(combinat):
b:= proc(n, i, t) option remember; `if`(n=0, t,
      `if`(i<2, 0, add(multinomial(n, n-i*j, i$j)/j!*
       b(n-i*j, i-1, irem(t+j, 2)), j=0..n/i)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=1..30);  # Alois P. Heinz, Mar 08 2015

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_, t_] := b[n, i, t] = If[n == 0, t, If[i < 2, 0, Sum[multinomial[n, Join[{n - i*j}, Array[i&, j]]]/j!*b[n - i*j, i - 1, Mod[t + j, 2]], {j, 0, n/i}]]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Jan 10 2016, after Alois P. Heinz *)

E.g.f.: sinh(exp(x)-x-1).

A097763 Number of different partitions of the set {1, 2, ..., n} into an even number of blocks such that each block contains at least 2 elements.

Original entry on oeis.org

0, 0, 0, 3, 10, 25, 56, 224, 1506, 9951, 57992, 315425, 1761552, 11022180, 78474748, 603715831, 4771273414, 38070877273, 309146434240, 2598546954268, 22887194502518, 211388690471531, 2031261113410564, 20121026325645745

Offset: 1

Isabel C. Lugo (izzycat(AT)gmail.com), Aug 23 2004

a(n) = A000296(n) - A097762(n).

			a(6)=25 since we can partition a set of six elements into two non-singleton blocks, either of sizes four and two (15 ways) or three and three (10 ways); a(6)=15+10=25.

Alois P. Heinz, Table of n, a(n) for n = 1..500

Cf. A000296, A097762.

seq(coeff(series(cosh(exp(x)-x-1),x=0,25),x^i)*i!, i=1..24);
# second Maple program:
with(combinat):
b:= proc(n, i, t) option remember; `if`(n=0, t,
      `if`(i<2, 0, add(multinomial(n, n-i*j, i$j)/j!*
       b(n-i*j, i-1, irem(t+j, 2)), j=0..n/i)))
    end:
a:= n-> b(n$2, 1):
seq(a(n), n=1..30);  # Alois P. Heinz, Mar 08 2015

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_, t_] := b[n, i, t] = If[n == 0, t, If[i < 2, 0, Sum[multinomial[n, Join[{n - i*j}, Array[i &, j]]]/j!*b[n - i*j, i - 1, Mod[t + j, 2]], {j, 0, n/i}]]]; a[n_] := b[n, n, 1];  Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Jan 10 2016, after Alois P. Heinz *)

Exponential generating function: cosh(exp(x)-x-1).

A182931 Generalized Bell numbers; square array read by ascending antidiagonals, A(n, k) for n >= 0 and k >= 1.

Original entry on oeis.org

1, 1, 1, 2, 0, 1, 5, 1, 0, 1, 15, 1, 0, 0, 1, 52, 4, 1, 0, 0, 1, 203, 11, 1, 0, 0, 0, 1, 877, 41, 1, 1, 0, 0, 0, 1, 4140, 162, 11, 1, 0, 0, 0, 0, 1, 21147, 715, 36, 1, 1, 0, 0, 0, 0, 1, 115975, 3425, 92, 1, 1, 0, 0, 0, 0, 0, 1, 678570, 17722, 491, 36, 1, 1, 0, 0, 0, 0, 0, 1

Offset: 1

Peter Luschny, Apr 05 2011

			Array starts:
[k=      1       2       3       4       5]
[n=0]    1,      1,      1,      1,      1,
[n=1]    1,      0,      0,      0,      0,
[n=2]    2,      1,      0,      0,      0,
[n=3]    5,      1,      1,      0,      0,
[n=4]   15,      4,      1,      1,      0,
[n=5]   52,     11,      1,      1,      1,
[n=6]  203,     41,     11,      1,      1,
[n=7]  877,    162,     36,      1,      1,
[n=8] 4140,    715,     92,     36,      1,
   A000110,A000296,A006505,A057837,A057814, ...

E. A. Enneking and J. C. Ahuja, Generalized Bell numbers, Fib. Quart., 14 (1976), 67-73.
Peter Luschny, Set partitions

Cf. A000110, A000296, A006505, A057837, A057814, A097147.

Row sums are A097147 for n >= 1.

egf := k -> exp(exp(x)*(1-GAMMA(k,x)/GAMMA(k)));
T := (n,k) -> n!*coeff(series(egf(k),x,n+1),x,n):
seq(print(seq(T(n,k),k=1..8)),n=0..8);

egf[k_] := Exp[Exp[x] (1 - Gamma[k, x]/Gamma[k])];
T[n_, k_] := n! SeriesCoefficient[egf[k], {x, 0, n}];
Table[T[n-k+1, k], {n, 0, 11}, {k, 1, n+1}] // Flatten (* Jean-François Alcover, Aug 13 2019 *)

E.g.f.: exp(exp(x)*(1-Gamma(k,x)/Gamma(k))); Gamma(k,x) the incomplete Gamma function.

A184177 Number of set partitions of {1,2,...,n} having no blocks of the form {i,i+1,i+2}.

Original entry on oeis.org

1, 1, 2, 4, 13, 46, 184, 805, 3840, 19775, 109180, 642382, 4007712, 26399764, 182939900, 1329327991, 10100670183, 80053631844, 660328296777, 5657449573120, 50255253534312, 462096537041953, 4391648990609487, 43079839534282880

Offset: 0

Emeric Deutsch, Feb 09 2011

nonn

a(n) = A184176(n,0).

			a(3) = 4 because we have 1-2-3, 1-23, 12-3, and 13-2.
a(4) = 13 because among the 15 (= Bell(4)) partitions of {1,2,3,4} only 123-4 and 1-234 have adjacent blocks of size 3.

Cf. A184176, A124323, A000296, A184174, A184175.

with(combinat): seq(add((-1)^j*binomial(n-2*j, j)*bell(n-3*j), j = 0 .. floor((1/3)*n)), n = 0 .. 23);

a(n) = Sum_{j=0..floor(n/3)} (-1)^j * binomial(n-2j,j) * Bell(n-3j,j).

A255706 Number of length-n word structures with no consecutive nonrepeated letters.

Original entry on oeis.org

1, 1, 1, 4, 11, 38, 151, 655, 3112, 16000, 88285, 519592, 3244512, 21400146, 148530179, 1081222613, 8231314455, 65369494593, 540322688516, 4639020151529, 41295634331020, 380514484523095, 3623898600072459, 35622399584611476, 360965731323718242

Offset: 0

Danny Rorabaugh, Mar 02 2015

nonn

Consider all free words generated over a countably infinite alphabet. Two words are of the same structure provided there is a permutation of the alphabet that sends one word to the other.

The number a(n) only counts length-n structures that satisfy the following: For every positive i

			For n = 2 the a(2) = 1 structure is: aa.
For n = 3 the a(3) = 4 structures are: aaa, aab, aba, abb.
For n = 4 the a(4) = 11 structures are: aaaa, aaab, aaba, aabb, abaa, abab, abac, abba, abbb, abbc, abcb. The structure aabc, for example, is not counted because the word aabc contains bc and the letters b and c each only appear once in aabc.

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

Cf. A000110, A000296.

with(combinat):
g:= proc(n) option remember; `if`(n=0, 1, bell(n-1)-g(n-1)) end:
a:= n-> add(g(n-j)*binomial(n+1-j, j), j=0..(n+1)/2):
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 03 2015

g[n_] := g[n] = If[n==0, 1, BellB[n-1] - g[n-1]]; a[n_] := Sum[g[n-j] * Binomial[n+1-j, j], {j, 0, (n+1)/2}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 26 2017, after Alois P. Heinz *)

def a(n):
    words = SetPartitions(range(n))
    count = len(words)
    for word in words:
        singles = []
        for letter in word:
        if len(letter)==1:
            singles.append(letter[0])
        singles.sort()
        for i in range(len(singles) - 1):
            if (singles[i] + 1)==singles[i + 1]:
                count -= 1
                break
    return count

a(n) = Sum_{j=0..(n+1)/2} A000296(n-j)*C(n+1-j,j). - Alois P. Heinz, Mar 03 2015

a(11)-a(24) from Alois P. Heinz, Mar 03 2015

Previous Showing 91-100 of 131 results. Next

cp's OEIS Frontend

A324013 Number of self-complementary set partitions of {1, ..., n} with no singletons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A335867 a(n) = exp(-n) * Sum_{k>=0} n^k * (k - 1)^n / k!.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A361781 A(n,k) is the n-th term of the k-th inverse binomial transform of the Bell numbers (A000110); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A367785 Expansion of e.g.f. exp(exp(3*x) - x - 1).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

A370945 Number T(n,k) of partitions of [n] whose singletons sum to k; triangle T(n,k), n>=0, 0<=k<=A000217(n), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A097762 Number of different partitions of the set {1, 2, ..., n} into an odd number of blocks such that each block contains at least 2 elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A097763 Number of different partitions of the set {1, 2, ..., n} into an even number of blocks such that each block contains at least 2 elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A182931 Generalized Bell numbers; square array read by ascending antidiagonals, A(n, k) for n >= 0 and k >= 1.