A001247 -id:A001247 - cp's OEIS frontend

A384968 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete bipartite graph using exactly k interchangeable colors, 2 <= k <= 2*n.

1, 1, 2, 1, 1, 6, 11, 6, 1, 1, 14, 61, 86, 50, 12, 1, 1, 30, 275, 770, 927, 530, 150, 20, 1, 1, 62, 1141, 5710, 12160, 12632, 6987, 2130, 355, 30, 1, 1, 126, 4571, 38626, 134981, 228382, 209428, 110768, 34902, 6580, 721, 42, 1, 1, 254, 18061, 248766, 1367310, 3553564, 4989621, 4093126, 2061782, 655788, 132958, 16996, 1316, 56, 1

Offset: 1

Andrew Howroyd, Jun 18 2025

Permuting the colors does not change the coloring. T(n,k) is the number of ways to partition the vertices into k independent sets.

			Triangle begins (n >= 1, k >= 2):
  1;
  1,  2,    1;
  1,  6,   11,    6,     1;
  1, 14,   61,   86,    50,    12,    1;
  1, 30,  275,  770,   927,   530,  150,   20,   1;
  1, 62, 1141, 5710, 12160, 12632, 6987, 2130, 355, 30, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..2500 (rows 1..50)
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Eric Weisstein's World of Mathematics, Vertex Coloring.

Row sums are A001247.
Columns k=2..5 are A000012, A000918, A384980, A384981.
Cf. A008277, A212084, A274310.

T(n,k) = sum(j=1, k-1, stirling(n,j,2)*stirling(n,k-j,2))
for(n=1, 7, print(vector(2*n-1,k,T(n,k+1))))

T(n,k) = Sum_{j=1..k-1} Stirling2(n,j)*Stirling2(n,k-j).

T(n,k) = A274310(2*n-1, k-1).

A152525 a(n) is the number of unordered pairs of disjoint set partitions of an n-element set.

Original entry on oeis.org

0, 0, 1, 7, 65, 811, 12762, 244588, 5574956, 148332645, 4538695461, 157768581675, 6167103354744, 268758895112072, 12961171404183498, 687270616305277589, 39843719438374998543, 2512873126513271758171, 171643113190082528007702, 12647168303374365311984284

Offset: 0

David Pasino, Dec 06 2008, Dec 08 2008

nonn

			From _Gus Wiseman_, Dec 09 2018: (Start)
The a(3) = 7 unordered pairs:
  {{1},{2},{3}}| {{1,2,3}}
   {{1},{2,3}} |{{1,2},{3}}
   {{1},{2,3}} |{{1,3},{2}}
   {{1,2},{3}} |{{1,3},{2}}
   {{1},{2,3}} | {{1,2,3}}
   {{1,2},{3}} | {{1,2,3}}
   {{1,3},{2}} | {{1,2,3}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..200
Frank Ruskey and Jennifer Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.
Frank Ruskey, Jennifer Woodcock and Yuji Yamauchi, Counting and computing the Rand and block distances of pairs of set partitions, Journal of Discrete Algorithms, Volume 16, October 2012, Pages 236-248. - From _N. J. A. Sloane_, Oct 03 2012

Cf. A000110, A000258, A001247, A008277, A048993, A059849, A060639, A181939, A193297, A318393, A322441, A322442, A320768.

a:= n-> add(binomial(n,k)*binomial(combinat[bell](k),2)*
        add(Stirling2(n-k,j)*(-1)^j, j=0..n-k), k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, May 27 2018

Array[Sum[Binomial[#, k] Sum[(-1)^j*StirlingS2[# - k, j], {j, 0, # - k}] Binomial[BellB@ k, 2], {k, 0, #}] &, 20, 0] (* Michael De Vlieger, May 27 2018 *)

a000110(n) = polcoeff( sum( k=0, n, prod( i=1, k, x / (1 - i*x)), x^n * O(x)), n);
a(n) = sum(k=0, n, binomial(n,k) * sum(j=0, n-k, (-1)^j*stirling(n-k,j, 2) * binomial(a000110(k),2))); \\ Michel Marcus, May 27 2018

a(n) = Sum_{k=0..n} binomial(n,k) * (Sum_{j=0..n-k} (-1)^j*A048993(n-k,j)) * binomial(A000110(k),2).
That is, summed on k from 0 to n, the number of k-element subsets of an n-element set, times the alternating sum of row n-k of Stirling2 numbers starting with +S(n-k, 0), times the number of pairs of partitions of k elements.
Obtained by inverting (binomial(A000110(n), 2)) = (Sum_{k=0..n} binomial(n,k)*A000110(n-k)*a(k)), which in turn is gotten by considering that a pair of conjoint partitions is gotten by choosing a partition of a subset and then choosing a pair of disjoint partitions of the complement.

A318398 Number of triples of set partitions of {1,2,...,n} whose meet is {{1},{2},...,{n}}.

Original entry on oeis.org

1, 7, 103, 2707, 110857, 6517129, 521167549, 54510591469, 7235648605909, 1190181847444189, 237953165658759679, 56905537750421669449, 16059682765076576965879, 5287171379685771887014489, 2010360123437921314268936809, 875173620070717892287441139989

Offset: 1

Gus Wiseman, Aug 25 2018

nonn

			The a(2) = 7 triples:
  {{1},{2}} {{1},{2}} {{1},{2}}
  {{1},{2}} {{1},{2}}  {{1,2}}
  {{1},{2}}  {{1,2}}  {{1},{2}}
  {{1},{2}}  {{1,2}}   {{1,2}}
   {{1,2}}  {{1},{2}} {{1},{2}}
   {{1,2}}  {{1},{2}}  {{1,2}}
   {{1,2}}   {{1,2}}  {{1},{2}}

Cf. A000110, A000258, A001247, A008277, A048994, A059849, A060639, A181939, A318389, A318391, A318393, A318399.

Table[Sum[StirlingS1[n,k]*BellB[k]^3,{k,0,n}],{n,10}]

a(n) = Sum_{k = 0..n} s(n,k)*B(k)^3 where s = A048994 and B = A000110.

A318815 Number of triples of set partitions of {1,2,...,n} whose join is {{1,2,...,n}}.

Original entry on oeis.org

1, 7, 103, 2773, 117697, 7167619, 590978941, 63385879261, 8584707943381, 1434654097736101, 290409845948305321, 70125579500764771585, 19940633217840575968969, 6603748351832744611210549, 2522614472277243822293033719, 1102166886808604068546379343289

Offset: 1

Gus Wiseman, Sep 04 2018

nonn

			The a(2) = 7 triples:
  {{1},{2}} {{1},{2}}  {{1,2}}
  {{1},{2}}  {{1,2}}  {{1},{2}}
  {{1},{2}}  {{1,2}}   {{1,2}}
   {{1,2}}  {{1},{2}} {{1},{2}}
   {{1,2}}  {{1},{2}}  {{1,2}}
   {{1,2}}   {{1,2}}  {{1},{2}}
   {{1,2}}   {{1,2}}   {{1,2}}

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

Cf. A000110, A000258, A001247, A008277, A048994, A059849, A060639, A181939, A318389, A318391, A318393, A318398, A318399.

nn=10;Table[n!*SeriesCoefficient[Log[1+Sum[BellB[n]^3*x^n/n!,{n,nn}]],{x,0,n}],{n,nn}]

Logarithmic transform of A000110(n)^3.

a(n) = Bell(n)^3 - (1/n) * Sum_{k=1..n-1} binomial(n,k) * Bell(n-k)^3 * k * a(k). - Ilya Gutkovskiy, Jan 17 2020

A069471 Stirling transform of squares of Bell numbers: a(0)=1, a(n) = Sum_{k=1..n} Stirling2(n,k)*(bell(k))^2.

Original entry on oeis.org

1, 1, 5, 38, 404, 5640, 98769, 2099606, 52883390, 1549218221, 52014755913, 1977659061064, 84305075757125, 3995485979209678, 209005906088572893, 11992147240091361387, 750583356339067110013, 50998365413706734478011

Offset: 0

Karol A. Penson, Mar 25 2002

nonn

G. C. Greubel, Table of n, a(n) for n = 0..250

Cf. A000110, A001247, A008277.

Join[{1}, Table[Sum[StirlingS2[n, k]*BellB[k]^2, {k, 1, n}], {n, 1, 50}]] (* G. C. Greubel, May 23 2018 *)

A095799 Bell triangle A011971 squared.

Original entry on oeis.org

1, 3, 4, 15, 21, 25, 107, 149, 200, 225, 1054, 1420, 1909, 2479, 2704, 13684, 17814, 23313, 30439, 38505, 41209, 224071, 283592, 360853, 461015, 587641, 727920, 769129, 4471699, 5535812, 6881856, 8590990, 10758160, 13443289, 16370471, 17139600

Offset: 1

Gary W. Adamson, Jun 06 2004

			T(3,2) = 21, because M = [1; 1 2; 2 3 5; ...], M^2 = [1; 3 4; 15 21 25; ...] and M^2[3,2] = 21.
Triangle begins:
:     1;
:     3,     4;
:    15,    21,    25;
:   107,   149,   200,   225;
:  1054,  1420,  1909,  2479,  2704;
: 13684, 17814, 23313, 30439, 38505, 41209;

Alois P. Heinz, Rows n = 1..45, flattened

Cf. A011971. Diagonal gives A001247 for n>0.

with(combinat): A:= proc(n, k) option remember; `if`(k<=n, add(binomial(k, i) *bell(n-k+i), i=0..k), 0) end: M:= proc(n) option remember; Matrix(n, (i, j)-> A(i-1, j-1)) end: T:= (n, k)-> (M(n)^2)[n, k]: seq(seq(T(n, k), k=1..n), n=1..10); # Alois P. Heinz, Oct 12 2009

max = 10; M = Table[If[k > n, 0, Sum[Binomial[k, i] BellB[n-k+i], {i, 0, k} ]], {n, 0, max-1}, {k, 0, max-1}];
T = M.M;
Table[T[[n]][[1 ;; n]], {n, 1, max}] // Flatten (* Jean-François Alcover, May 24 2016 *)

Let M = the Bell triangle (A011971) as an infinite lower triangle matrix. Then T(n,k) = M^2[n,k].

Edited, corrected and extended by Alois P. Heinz, Oct 12 2009

A217143 Sum of squares of Bell numbers (A000110).

Original entry on oeis.org

1, 2, 6, 31, 256, 2960, 44169, 813298, 17952898, 465148507, 13915349132, 474372594032, 18228772272441, 782443669319410, 37224994809379094, 1949799331997896119, 111783178753323665728, 6978369826387194664144, 472207139326449254997425

Offset: 0

Emanuele Munarini, Sep 27 2012

nonn

Cf. A000110, A005001, A087650, A217144.

Partial sums of A001247.

[&+[Bell(i)^2: i in [0..n]]: n in [0..20]]; // Bruno Berselli, Sep 27 2012

Accumulate[BellB[Range[0, 20]]^2] (* Bruno Berselli, Sep 27 2012 *)

makelist(sum(belln(k)^2,k,0,n),n,0,30);

from itertools import accumulate, islice
def A217143_gen(): # generator of terms
    yield 1
    blist, b, c = (1,), 1, 1
    while True:
        blist = list(accumulate(blist, initial=(b:=blist[-1])))
        yield (c := c+b**2)
A217143_list = list(islice(A217143_gen(),20)) # Chai Wah Wu, Jun 22 2022

a(n) = Sum_{k=0..n} Bell(k)^2.

A318395 Number of nonnegative integer matrices with values summing to n, up to transposition and permutation of rows and columns.

Original entry on oeis.org

1, 1, 3, 7, 21, 54, 167, 491, 1586, 5132, 17442, 60399, 216172, 790436, 2965333, 11365813, 44536775, 178107679, 726716229, 3022464373, 12807206008, 55253891494, 242585471236, 1083255591604, 4917631017573, 22685090928596, 106291554085987, 505653658171936, 2441383079595849

Offset: 0

Gus Wiseman, Aug 25 2018

nonn

Also the number of non-isomorphic pairs of set partitions of {1,...,n}.

			Inequivalent representatives of the a(3) = 7 nonnegative integer matrices:
  [3]   [1 2]   [1 1 1]   [1 0]   [0 1]   [1 0 0]   [1 0 0]
                          [0 2]   [1 1]   [0 1 1]   [0 1 0]
                                                    [0 0 1]
Non-isomorphic representatives of the a(3) = 7 pairs of set partitions:
    {{1,2,3}}     {{1,2,3}}
    {{1,2,3}}    {{1},{2,3}}
    {{1,2,3}}   {{1},{2},{3}}
   {{1},{2,3}}   {{1},{2,3}}
   {{1},{2,3}}   {{2},{1,3}}
   {{1},{2,3}}  {{1},{2},{3}}
  {{1},{2},{3}} {{1},{2},{3}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A000110, A000258, A001247, A007716, A008277, A049311, A059849, A060639, A116540, A181939, A316983, A318393.

a(n) = (A007716(n) + A316983(n))/2. - Andrew Howroyd, Sep 03 2018

a(6)-a(25) from Andrew Howroyd, Sep 03 2018

Terms a(26) and beyond from Andrew Howroyd, Mar 29 2020

A337053 a(n) = exp(2) * Sum_{i>=0} Sum_{j>=0} (-1)^(i+j) * (ij)^n / (i! j!).

Original entry on oeis.org

1, 1, 0, 1, 1, 4, 81, 81, 2500, 71289, 170569, 4752400, 314388361, 2553584089, 12138750976, 3868290439209, 98777141491561, 74627448683524, 77548359598953721, 6456459980629467081, 96370747288471888164, 738333256838429983201, 526354651474052521626801

Offset: 0

Ilya Gutkovskiy, Aug 12 2020

nonn

Squares of complementary Bell numbers.

Cf. A000587, A001247, A121869.

Table[Exp[2] Sum[Sum[(-1)^(i + j) (i j)^n/(i! j!), {j, 0, Infinity}], {i, 0, Infinity}], {n, 0, 22}]
Table[BellB[n, -1]^2, {n, 0, 22}]

a(n) = A000587(n)^2.

A354458 Number of commuting pairs of equivalence relations on [n].

Original entry on oeis.org

1, 1, 4, 19, 117, 864, 7459, 73749, 818960, 10078023

Offset: 0

Geoffrey Critzer, May 30 2022

More precisely, a(n) is the number of ordered pairs (S,T) of equivalence relations on [n] such that S*T=T*S where the operation * is composition of relations. The composition of equivalence relations is not generally an equivalence relation. S*T=T*S if and only if S*T is the smallest equivalence relation that contains both S and T.

			Let S = 1/24/3 and T = 13/2/4 be equivalence relations on [4]. Then S*T = T*S = 13/24 so (S,T) is an example of a commuting pair of equivalence relations (as well as (T,S) ).

Cf. A001247, A000110.

Needs["Combinatorica`"];f[partition_] := Normal[SparseArray[ Level[Map[Tuples[#, 2] &, partition], {2}] -> 1]]; Table[er = Map[f,SetPartitions[n]]; Length[Level[
   Table[Select[er, Clip[er[[i]].#] == Clip[#.er[[i]]] &], {i, 1,Length[er]}], {2}]], {n, 0, 8}]

a(9) from Vaclav Kotesovec, May 31 2022

cp's OEIS Frontend

A384968 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete bipartite graph using exactly k interchangeable colors, 2 <= k <= 2*n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A152525 a(n) is the number of unordered pairs of disjoint set partitions of an n-element set.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A318398 Number of triples of set partitions of {1,2,...,n} whose meet is {{1},{2},...,{n}}.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A318815 Number of triples of set partitions of {1,2,...,n} whose join is {{1,2,...,n}}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A069471 Stirling transform of squares of Bell numbers: a(0)=1, a(n) = Sum_{k=1..n} Stirling2(n,k)*(bell(k))^2.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A095799 Bell triangle A011971 squared.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A217143 Sum of squares of Bell numbers (A000110).

Views

Author

Keywords

Crossrefs

Programs

Magma

Mathematica

Maxima

Python

Formula

A318395 Number of nonnegative integer matrices with values summing to n, up to transposition and permutation of rows and columns.

Views

Author

Keywords

Comments

Examples

A337053 a(n) = exp(2) * Sum_{i>=0} Sum_{j>=0} (-1)^(i+j) * (ij)^n / (i! j!).