A016098 -id:A016098 - cp's OEIS frontend

A247491 Number of crossing partitions of {1,2,...,n} that contain no singletons.

0, 0, 0, 0, 1, 5, 26, 126, 624, 3193, 17119, 96668, 576104, 3621982, 23980620, 166805068, 1215842905, 9263445775, 73599067250, 608471202527, 5224252803246, 46499854580107, 428369819029085, 4078345518655015, 40073659206668916, 405885206895408576, 4232705116291188276

Offset: 0

Peter Luschny, Sep 25 2014

nonn

A partition p of the set {1,2,...,n} whose elements are arranged in their natural order, is crossing if there exist four numbers 1 <= i < k < j < l <= n such that i and j are in the same block, k and l are in the same block, but i,j and k,l belong to two different blocks.

Also the number of crossing partitions of {1,2,...,n} that contain no cyclical adjacencies. e.g., a(5) = 5, [13|24|5, 13|25|4, 14|25|3, 14|2|35, 1|24|35]. - Yuchun Ji, Nov 13 2020

			The crossing partitions of {1,2,3,4,5} that contain no singletons are: [13|245], [14|235], [24,135], [25|134], [35|124].

Indranil Ghosh, Table of n, a(n) for n = 0..163
Peter Luschny, Set partitions

Cf. A016098, A005043, A000110, A000296, A247494.

A247491 := n -> (-1)^n-add((-1)^(n-k)*combinat:-bell(k), k = 0..n-1) - (-1)^n*hypergeom([-n, 1/2], [2], 4); seq(round(evalf(A247491(n), 100)), n=0..27);

Table[Sum[(-1)^(n-k)*Binomial[n,k]*(BellB[k]-CatalanNumber[k]), {k,0,n}], {n, 0, 26}] (* Indranil Ghosh, Mar 04 2017 *)

B(n) = sum(k=0, n, stirling(n,k,2));
a(n) = sum(k=0, n, (-1)^(n-k)*binomial(n,k)*(B(k)-binomial(2*k,k)/(k+1))); \\ Indranil Ghosh, Mar 04 2017

A247491 = lambda n: sum((-1)^(n-k)*binomial(n,k)*(bell_number(k) - catalan_number(k)) for k in (0..n))
[A247491(n) for n in range(27)]

a(n) = Sum_{k=0..n} (-1)^(n-k)*C(n,k)*(Bell(k)-Catalan(k)).
a(n) = A000296(n) - A005043(n).
a(n) = A016098(n) - A247494(n); i.e., remove the partitions with cyclical adjacencies from the crossing partitions. - Yuchun Ji, Nov 17 2020

A247494 Number of crossing partitions of {1,2,...,n} that contain singletons.

Original entry on oeis.org

0, 0, 0, 0, 0, 5, 45, 322, 2086, 13092, 82060, 523116, 3429481, 23279555, 164244262, 1206458632, 9228941572, 73471779239, 608000100209, 5222503739340, 46493341311706, 428345495309624, 4078254436854598, 40073317276815681, 405883920183989049, 4232700263388189325

Offset: 0

Peter Luschny, Oct 02 2014

nonn

A partition p of the set {1,2,...,n} whose elements are arranged in their natural order, is crossing if there exist four numbers 1 <= i < k < j < l <= n such that i and j are in the same block, k and l are in the same block, but i,j and k,l belong to two different blocks.

Also number of crossing partitions of {1,2,...,n} that contain cyclical adjacencies. a(5) = 5, [124|35, 134|25, 135|24, 13|245, 14|235]. - Yuchun Ji, Nov 13 2020

			The crossing partitions of {1,2,3,4,5} that contain singletons are: [1|24|35], [2|14|35], [3|14|25], [4|13|25], [5|13|24].

Indranil Ghosh, Table of n, a(n) for n = 0..170
Peter Luschny, Set partitions

Cf. A016098, A005043, A000110, A000296, A106640, A247491.

A247494 := n -> add((-1)^(n-k+1)*combinat:-bell(k+1), k=0..n-1) + (-1)^n*hypergeom([-n,1/2],[2],4) - binomial(2*n,n)/(n+1):
seq(round(evalf(A247494(n),100)), n=0..25);

Table[Sum[(-1)^(n-k+1)*Binomial[n,k]*(BellB[k]-CatalanNumber[k]),{k,0,n-1}],{n,0,25}] (* Indranil Ghosh, Mar 04 2017 *)

B(n) = sum(k=0, n, stirling(n,k,2));
a(n) = sum(k=0, n-1, (-1)^(n-k+1)*binomial(n,k)*(B(k) - binomial(2*k,k)/(k+1))); \\ Indranil Ghosh, Mar 04 2017

A247494 = lambda n: sum((-1)^(n-k+1)*binomial(n,k)*(bell_number(k)-catalan_number(k)) for k in (0..n-1))
[A247494(n) for n in range(26)]

a(n) = Sum_{k = 0..n-1} (-1)^(n-k+1)*binomial(n,k)*(Bell(k)-Catalan(k)).
a(n) = A016098(n) - A247491(n).
a(n) = A000296(n+1) - A106640(n-1), for n>0 (i.e., remove the non-crossing partitions from the cyclical adjacencies partitions). - Yuchun Ji, Nov 11 2020

A306437 Regular triangle read by rows where T(n,k) is the number of non-crossing set partitions of {1, ..., n} in which all blocks have size k.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 2, 0, 1, 1, 0, 0, 0, 1, 1, 5, 3, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 14, 0, 4, 0, 0, 0, 1, 1, 0, 12, 0, 0, 0, 0, 0, 1, 1, 42, 0, 0, 5, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 132, 55, 22, 0, 6, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 429, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Gus Wiseman, Feb 15 2019

			Triangle begins:
  1
  1   1
  1   0   1
  1   2   0   1
  1   0   0   0   1
  1   5   3   0   0   1
  1   0   0   0   0   0   1
  1  14   0   4   0   0   0   1
  1   0  12   0   0   0   0   0   1
  1  42   0   0   5   0   0   0   0   1
  1   0   0   0   0   0   0   0   0   0   1
  1 132  55  22   0   6   0   0   0   0   0   1
Row 6 counts the following non-crossing set partitions (empty columns not shown):
  {{1}{2}{3}{4}{5}{6}}  {{12}{34}{56}}  {{123}{456}}  {{123456}}
                        {{12}{36}{45}}  {{126}{345}}
                        {{14}{23}{56}}  {{156}{234}}
                        {{16}{23}{45}}
                        {{16}{25}{34}}

Germain Kreweras, Sur les partitions non croisées d'un cycle, Discrete Math. 1 333-350 (1972).
Wikipedia, Noncrossing partition.

Row sums are A194560. Column k=2 is A126120. Trisection of column k=3 is A001764.

Cf. A000108, A000110, A000296, A001006, A001263, A001610, A016098, A038041, A061095, A125181, A134264.

T:= (n, k)-> `if`(irem(n, k)=0, binomial(n, n/k)/(n-n/k+1), 0):
seq(seq(T(n,k), k=1..n), n=1..14);  # Alois P. Heinz, Feb 16 2019

Table[Table[If[Divisible[n,d],d/n*Binomial[n,n/d-1],0],{d,n}],{n,15}]

If d|n, then T(n, d) = binomial(n, n/d)/(n - n/d + 1); otherwise T(n, k) = 0 [Theorem 1 of Kreweras].

A189232 Triangle read by rows: Number of crossing set partitions of {1,2,...,n} into k blocks.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 5, 5, 0, 0, 0, 16, 40, 15, 0, 0, 0, 42, 196, 175, 35, 0, 0, 0, 99, 770, 1211, 560, 70, 0, 0, 0, 219, 2689, 6594, 5187, 1470, 126, 0, 0, 0, 466, 8790, 31585, 37233, 17535, 3360, 210, 0, 0

Offset: 1

Peter Luschny, Apr 28 2011

			There are 10 crossing set partitions of {1,2,3,4,5}.
T(5,2) = card{13|245, 14|235, 24|135, 25|134, 35|124} = 5.
T(5,3) = card{1|35|24, 2|14|35, 3|14|25, 4|13|25, 5|13|24} = 5.
[1] 0
[2] 0, 0
[3] 0, 0, 0
[4] 0, 1, 0, 0
[5] 0, 5, 5, 0, 0
[6] 0, 16, 40, 15, 0, 0
[7] 0, 42, 196, 175, 35, 0, 0
[8] 0, 99, 770, 1211, 560, 70, 0, 0

R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999 (Exericses 6.19)

Row sums A016098, A001263.

A189232 := (n,k) -> combinat[stirling2](n,k) - binomial(n,k-1)*binomial(n,k)/n:
for n from 1 to 9 do seq(A189232(n,k), k = 1..n) od;

T[n_, k_] := StirlingS2[n, k] - Binomial[n, k-1] Binomial[n, k]/n;
Table[T[n, k], {n, 1, 10}, {k, 1, n}] (* Jean-François Alcover, Jun 24 2019 *)

T(n,k) = S2(n,k) - C(n,k-1)*C(n,k)/n; S2(n,k) Stirling numbers of the second kind, C(n,k) binomial coefficients.

A326289 a(0) = 0, a(n) = 2^binomial(n,2) - 2^(n - 1).

Original entry on oeis.org

0, 0, 0, 4, 56, 1008, 32736, 2097088, 268435328, 68719476480, 35184372088320, 36028797018962944, 73786976294838204416, 302231454903657293672448, 2475880078570760549798240256, 40564819207303340847894502555648, 1329227995784915872903807060280311808

Offset: 0

Gus Wiseman, Jun 23 2019

nonn

Number of simple graphs with vertices {1..n} containing two edges {a,b}, {c,d} that are weakly crossing, meaning a <= c < b <= d or c <= a < d <= b.

			The a(4) = 56 weakly crossing edge-sets:
  {12,13}  {12,13,14}  {12,13,14,23}  {12,13,14,23,24}  {12,13,14,23,24,34}
  {12,14}  {12,13,23}  {12,13,14,24}  {12,13,14,23,34}
  {12,23}  {12,13,24}  {12,13,14,34}  {12,13,14,24,34}
  {12,24}  {12,13,34}  {12,13,23,24}  {12,13,23,24,34}
  {12,34}  {12,14,23}  {12,13,23,34}  {12,14,23,24,34}
  {13,14}  {12,14,24}  {12,13,24,34}  {13,14,23,24,34}
  {13,23}  {12,14,34}  {12,14,23,24}
  {13,24}  {12,23,24}  {12,14,23,34}
  {13,34}  {12,23,34}  {12,14,24,34}
  {14,24}  {12,24,34}  {12,23,24,34}
  {14,34}  {13,14,23}  {13,14,23,24}
  {23,24}  {13,14,24}  {13,14,23,34}
  {23,34}  {13,14,34}  {13,14,24,34}
  {24,34}  {13,23,24}  {13,23,24,34}
           {13,23,34}  {14,23,24,34}
           {13,24,34}
           {14,23,24}
           {14,23,34}
           {14,24,34}
           {23,24,34}

Cf. A000088, A000108, A002662, A006125, A016098, A054726, A324170.

Cf. A326210, A326244, A326248, A326250, A326257, A326279, A326290.

Table[If[n==0,0,2^Binomial[n,2]-2^(n-1)],{n,0,5}]

A326291 Number of unsortable factorizations of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0

Offset: 1

Gus Wiseman, Jun 24 2019

nonn

A factorization into factors > 1 is unsortable if there is no permutation (c_1,...,c_k) of the factors such that the maximum prime factor of c_i is at most the minimum prime factor of c_{i+1}. For example, the factorization (6*8*27) is sortable because the permutation (8,6,27) satisfies the condition.

			The a(180) = 10 unsortable factorizations:
  (2*3*3*10)  (5*6*6)   (3*60)
              (2*3*30)  (6*30)
              (2*9*10)  (9*20)
              (3*3*20)  (10*18)
              (3*6*10)
Missing from this list are:
  (2*2*3*3*5)  (2*2*5*9)   (4*5*9)   (2*90)   (180)
               (2*3*5*6)   (2*2*45)  (4*45)
               (3*3*4*5)   (2*5*18)  (5*36)
               (2*2*3*15)  (2*6*15)  (12*15)
                           (3*4*15)
                           (3*5*12)

Unsortable set partitions are A058681.
Unsortable normal multiset partitions are A326211.
MM-numbers of unsortable multiset partitions are A326258.
Cf. A000108, A001055, A001519, A016098, A112798, A302242, A324170, A324171.
Cf. A326209, A326212, A326243, A326256, A326257.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Select[facs[n],!OrderedQ[Join@@Sort[primeMS/@#,lexsort]]&]],{n,100}]

A324325 Number of non-crossing multiset partitions of a multiset whose multiplicities are the prime indices of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 5, 9, 7, 7, 11, 11, 12, 16, 14, 15, 26, 22, 21, 29, 19, 30, 33, 31, 30, 66, 38, 42, 52, 56, 42, 47, 45, 57, 82, 77, 67, 77, 67, 101, 98, 135, 64, 137, 97, 176, 104, 109, 109, 118, 105, 231, 213, 97, 127, 181, 139, 297, 173, 385, 195, 269

Offset: 1

Gus Wiseman, Feb 22 2019

nonn

This multiset (row n of A305936) is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

A multiset partition is crossing if it contains two blocks of the form {{...x...y...},{...z...t...}} where x < z < y < t or z < x < t < y.

			The a(16) = 14 non-crossing multiset partitions of the multiset {1,2,3,4}:
  {{1,2,3,4}}
  {{1},{2,3,4}}
  {{2},{1,3,4}}
  {{3},{1,2,4}}
  {{4},{1,2,3}}
  {{1,2},{3,4}}
  {{1,4},{2,3}}
  {{1},{2},{3,4}}
  {{1},{3},{2,4}}
  {{1},{4},{2,3}}
  {{2},{3},{1,4}}
  {{2},{4},{1,3}}
  {{3},{1,2},{4}}
  {{1},{2},{3},{4}}
Missing from this list is {{1,3},{2,4}}.

Cf. A000108, A001055, A001970, A016098, A054726, A099947, A181821, A305936, A306438, A318284, A318285.

Cf. A324167, A324168, A324169, A324170, A324171, A324324, A324326.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

a(n) + A324326(n) = A318284(n).

A326277 Number of crossing normal multiset partitions of weight n.

Original entry on oeis.org

0, 0, 0, 0, 1, 22, 314, 3711, 39947

Offset: 0

Gus Wiseman, Jun 22 2019

A multiset partition is normal if it covers an initial interval of positive integers.

A multiset partition is crossing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < y < t or z < x < t < y.

			The a(5) = 22 crossing normal multiset partitions:
  {{1,3},{1,2,4}}  {{1},{1,3},{2,4}}
  {{1,3},{2,2,4}}  {{1},{2,4},{3,5}}
  {{1,3},{2,3,4}}  {{2},{1,3},{2,4}}
  {{1,3},{2,4,4}}  {{2},{1,4},{3,5}}
  {{1,3},{2,4,5}}  {{3},{1,3},{2,4}}
  {{1,4},{2,3,5}}  {{3},{1,4},{2,5}}
  {{2,4},{1,1,3}}  {{4},{1,3},{2,4}}
  {{2,4},{1,2,3}}  {{4},{1,3},{2,5}}
  {{2,4},{1,3,3}}  {{5},{1,3},{2,4}}
  {{2,4},{1,3,4}}
  {{2,4},{1,3,5}}
  {{2,5},{1,3,4}}
  {{3,5},{1,2,4}}

Crossing simple graphs are A326210.
Normal multiset partitions are A255906.
Non-crossing normal multiset partitions are A324171.
MM-numbers of crossing multiset partitions are A324170.
Cf. A000108, A016098, A054726, A058681.
Cf. A326211, A326212, A326255, A326256, A326258.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

A127745 Counts Bell numbers (except for Catalans) associated with the partition number [n].

Original entry on oeis.org

0, 0, 0, 1, 8, 50, 294, 1717, 10194, 62284, 394346, 2597266, 17827166, 127575414, 951411752, 7386583917, 59623674472, 499648882838, 4340548090590, 39033489125836, 362871600781796, 3482858492844510, 34471940635650958, 351444263328831458

Offset: 1

Alford Arnold, Feb 25 2007

A074664 counts the Bell Numbers associated with the partition number [n]. A000108 counts the corresponding Catalan numbers and here we count the remaining Bell numbers associated with the partition number [n].

			There are 15 Bell objects when n = 4, 14 are also Catalans so a(4) = 1.
There are 52 Bell objects when n = 5, 42 are also Catalans; we know that 5 = 4+1 = 1+4 which accounts for two of the non-Catalan Bells so, a(5) = 52 - 42 - 2 = 8.

Cf. A000041, A000108, A000110, A001399, A016098, A035300, A127743, A074664.

a(n) = A074664(n) - A000108(n-1)

A179315 Nonzero differences A179313(n,k)- A127742(n,k) read along rows.

Original entry on oeis.org

1, 8, 2, 50, 16, 2, 3, 294, 100, 16, 4, 24, 6, 4, 1717, 588, 100, 32, 11, 150, 48, 12, 3, 32, 12, 5, 10194, 3434, 588, 200, 124, 882, 300

Offset: 4

Alford Arnold, Jul 12 2010

Refinement of the nonzero entries of A016098.

			A179313 .begins 1; 1 1; 2 2 1; 6 4 1 3 1; 22 12 4 6 3 4 1; 92 44 12 18
A127742 .begins 1; 1 1; 2 2 1; 5 4 1 3 1; 14 10 4 6 3 4 1; 42 28 10 15
so
This seq begins................1...........8..2............50 16 02 03

Cf. A000041, A016098, A000110, A000108, A179313

Edited and extended by R. J. Mathar, Jul 16 2010

cp's OEIS Frontend

A247491 Number of crossing partitions of {1,2,...,n} that contain no singletons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A247494 Number of crossing partitions of {1,2,...,n} that contain singletons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A306437 Regular triangle read by rows where T(n,k) is the number of non-crossing set partitions of {1, ..., n} in which all blocks have size k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A189232 Triangle read by rows: Number of crossing set partitions of {1,2,...,n} into k blocks.

Views

Author

Keywords

Examples

References

Crossrefs

Programs

Maple

Mathematica

Formula

A326289 a(0) = 0, a(n) = 2^binomial(n,2) - 2^(n - 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326291 Number of unsortable factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A324325 Number of non-crossing multiset partitions of a multiset whose multiplicities are the prime indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326277 Number of crossing normal multiset partitions of weight n.