Wikiversity

Partition related number triangles


Set partitions by number of blocks

edit

All partitions of a set with n elements into k blocks are enumerated by the number triangle called Stirling numbers of the second kind. When some partitions are left out or treated as equivalent the new set of partitions is enumerated by a new number triangle. The number triangles for noncrossing partitions are symmetric.


All Noncrossing
All
Triangle A008277 (Stirling2) with row sums A000110 (Bell)
1 2 3 4 5 6 7 8 9 10 11 12 13 sum
1 1 1
2 1 1 2
3 1 3 1 5
4 1 7 6 1 15
5 1 15 25 10 1 52
6 1 31 90 65 15 1 203
7 1 63 301 350 140 21 1 877
8 1 127 966 1701 1050 266 28 1 4140
9 1 255 3025 7770 6951 2646 462 36 1 21147
10 1 511 9330 34105 42525 22827 5880 750 45 1 115975
11 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 678570
12 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 4213597
13 1 4095 261625 2532530 7508501 9321312 5715424 1899612 359502 39325 2431 78 1 27644437

Diagonal: A129506

 
The 1,7,6,1 partitions of a 4-element set
with 1,2,3,4 blocks
 Triangle A001263 (Narayana) with row sums A000108 (Catalan)
1 2 3 4 5 6 7 8 9 10 11 12 13 sum
1 1 1
2 1 1 2
3 1 3 1 5
4 1 6 6 1 14
5 1 10 20 10 1 42
6 1 15 50 50 15 1 132
7 1 21 105 175 105 21 1 429
8 1 28 196 490 490 196 28 1 1430
9 1 36 336 1176 1764 1176 336 36 1 4862
10 1 45 540 2520 5292 5292 2520 540 45 1 16796
11 1 55 825 4950 13860 19404 13860 4950 825 55 1 58786
12 1 66 1210 9075 32670 60984 60984 32670 9075 1210 66 1 208012
13 1 78 1716 15730 70785 169884 226512 169884 70785 15730 1716 78 1 742900

Diagonal: A000891

 
The 1,6,6,1 n. p. of a 4-element set
with 1,2,3,4 blocks
Up
to
rot
Triangle A152175 with row sums A084423
1 2 3 4 5 6 7 8 9 10 11 sum
1 1 1
2 1 1 2
3 1 1 1 3
4 1 3 2 1 7
5 1 3 5 2 1 12
6 1 7 18 13 3 1 43
7 1 9 43 50 20 3 1 127
8 1 19 126 221 136 36 4 1 544
9 1 29 339 866 773 296 52 4 1 2361
10 1 55 946 3437 4281 2303 596 78 5 1 11703
11 1 93 2591 13250 22430 16317 5817 1080 105 5 1 61690
Triangle A209805 with row sums A054357
1 2 3 4 5 6 7 8 9 10 11 12 13 sum
1 1 1
2 1 1 2
3 1 1 1 3
4 1 2 2 1 6
5 1 2 4 2 1 10
6 1 3 10 10 3 1 28
7 1 3 15 25 15 3 1 63
8 1 4 26 64 64 26 4 1 190
9 1 4 38 132 196 132 38 4 1 546
10 1 5 56 256 536 536 256 56 5 1 1708
11 1 5 75 450 1260 1764 1260 450 75 5 1 5346
12 1 6 104 765 2736 5102 5102 2736 765 104 6 1 17428
13 1 6 132 1210 5445 13068 17424 13068 5445 1210 132 6 1 57148

Diagonal is probably A001246 (square Catalan numbers)
The calculation of T(13,6) is based on the assumption that T(13,7) = C(6)2. Matlab code from the calculation is here.

Up
to
rot
&
ref
Triangle A152176 with row sums A084708
1 2 3 4 5 6 7 8 9 10 11 sum
1 1 1
2 1 1 2
3 1 1 1 3
4 1 3 2 1 7
5 1 3 5 2 1 12
6 1 7 14 11 3 1 37
7 1 8 31 33 16 3 1 93
8 1 17 82 137 85 27 4 1 354
9 1 22 202 478 434 171 37 4 1 1350
10 1 43 538 1851 2271 1249 338 54 5 1 6351
11 1 62 1401 6845 11530 8389 3056 590 70 5 1 31950

 

Triangle A209612 with row sums A111275
1 2 3 4 5 6 7 8 9 10 11 sum
1 1 1
2 1 1 2
3 1 1 1 3
4 1 2 2 1 6
5 1 2 4 2 1 10
6 1 3 8 8 3 1 24
7 1 3 12 17 12 3 1 49
8 1 4 19 41 41 19 4 1 130
9 1 4 27 78 116 78 27 4 1 336
10 1 5 38 148 298 298 148 38 5 1 980
11 1 5 50 250 680 932 680 250 50 5 1 2904

 

In the two illustrations above some set partitions, sharing the same colors, are grouped together.
They always correspond to the same integer partition, shown in the following illustration:

Triangle A008284 with row sums A000041
1 2 3 4 5 6 7 8 9 10 11 12 13 sum
1 1 1
2 1 1 2
3 1 1 1 3
4 1 2 1 1 5
5 1 2 2 1 1 7
6 1 3 3 2 1 1 11
7 1 3 4 3 2 1 1 15
8 1 4 5 5 3 2 1 1 22
9 1 4 7 6 5 3 2 1 1 30
10 1 5 8 9 7 5 3 2 1 1 42
11 1 5 10 11 10 7 5 3 2 1 1 56
12 1 6 12 15 13 11 7 5 3 2 1 1 77
13 1 6 14 18 18 14 11 7 5 3 2 1 1 101
 

Diagonal and second knight moves diagonal: A000041 from 0th entry
A008284 ⚪ A001844     =     A008284 ⚪ A081267     =     A000041

Lah numbers

edit

Counting not only the partitions (which gives the Stirling2 numbers shown above), but also the possible permutations within the blocks gives the triangle of unsigned Lah numbers   A105278 (with the row sums   A000262).

Also here one could define a noncrossing version (where T(4;2) would be 32 instead of 36).

 
The unsigned Lah numbers



Set partitions by type and by number of singletons

edit
tabl triangles,
columns match number of singletons:
A N
A A124323 A091867
Utr A211356 A211357
Utr&r A211358 A211359
tabf triangles,
columns match type:
A N     Rc
A A211350 A211351 A007318
Utr A211352 A211353 A047996
Utr&r A211354 A211355 A052307
Sequences of row sums:
A N
A A000110 A000108
Utr A084423 A054357
Utr&r A084708 A111275
 
Set partitions (up to rotation and reflection) by corresponding integer partition (their type)
 
Counting the displayed partitions in different ways leads to different number triangles.
These are examples for entry(6,3).



All

edit

All, All        (by number of singletons)
Triangle A124323 with row sums A000110 (Bell)

0 1 2 3 4 5 6 7 8 9 10 11 12 sum
0 1 1
1 0 1 1
2 1 0 1 2
3 1 3 0 1 5
4 4 4 6 0 1 15
5 11 20 10 10 0 1 52
6 41 66 60 20 15 0 1 203
7 162 287 231 140 35 21 0 1 877
8 715 1296 1148 616 280 56 28 0 1 4140
9 3425 6435 5832 3444 1386 504 84 36 0 1 21147
10 17722 34250 32175 19440 8610 2772 840 120 45 0 1 115975
11 98253 194942 188375 117975 53460 18942 5082 1320 165 55 0 1 678570
12 580317 1179036 1169652 753500 353925 128304 37884 8712 1980 220 66 0 1 4213597

All, Noncrossing        (by number of singletons)
Triangle A091867 with row sums A000108 (Catalan)

0 1 2 3 4 5 6 7 8 9 10 11 12 sum
0 1 1
1 0 1 1
2 1 0 1 2
3 1 3 0 1 5
4 3 4 6 0 1 14
5 6 15 10 10 0 1 42
6 15 36 45 20 15 0 1 132
7 36 105 126 105 35 21 0 1 429
8 91 288 420 336 210 56 28 0 1 1430
9 232 819 1296 1260 756 378 84 36 0 1 4862
10 603 2320 4095 4320 3150 1512 630 120 45 0 1 16796
11 1585 6633 12760 15015 11880 6930 2772 990 165 55 0 1 58786
12 4213 19020 39798 51040 45045 28512 13860 4752 1485 220 66 0 1 208012


Up to rotation

edit

Up to rot, All        (by number of singletons)
Triangle A211356 with row sums A084423

0 1 2 3 4 5 6 7 8 9 10 11 12 sum
0 1 1
1 0 1 1
2 1 0 1 2
3 1 1 0 1 3
4 3 1 2 0 1 7
5 3 4 2 2 0 1 12
6 12 11 12 4 3 0 1 43
7 24 41 33 20 5 3 0 1 127
8 103 162 151 77 39 7 4 0 1 544
9 387 715 648 386 154 56 10 4 0 1 2361
10 1819 3425 3255 1944 876 278 88 12 5 0 1 11703
11 8933 17722 17125 10725 4860 1722 462 120 15 5 0 1 61690
12 48632 98253 97685 62807 29593 10692 3188 726 171 19 6 0 1 351773

Up to rot, Noncrossing        (by number of singletons)
Triangle A211357 with row sums A054357

0 1 2 3 4 5 6 7 8 9 10 11 12 sum
0 1 1
1 0 1 1
2 1 0 1 2
3 1 1 0 1 3
4 2 1 2 0 1 6
5 2 3 2 2 0 1 10
6 5 6 9 4 3 0 1 28
7 6 15 18 15 5 3 0 1 63
8 15 36 56 42 29 7 4 0 1 190
9 28 91 144 142 84 42 10 4 0 1 546
10 67 232 419 432 322 152 66 12 5 0 1 1708
11 145 603 1160 1365 1080 630 252 90 15 5 0 1 5346
12 368 1585 3342 4258 3779 2376 1170 396 128 19 6 0 1 17428


Up to rotation and reflection

edit

Up to rot & ref, All        (by number of singletons)
Triangle A211358 with row sums A084708

0 1 2 3 4 5 6 7 8 9 10 11 12 sum
0 1 1
1 0 1 1
2 1 0 1 2
3 1 1 0 1 3
4 3 1 2 0 1 7
5 3 4 2 2 0 1 12
6 12 7 11 3 3 0 1 37
7 20 28 21 16 4 3 0 1 93
8 81 89 101 43 30 5 4 0 1 354
9 238 395 356 223 86 40 7 4 0 1 1350
10 1079 1757 1783 1004 504 148 62 8 5 0 1 6351
11 4752 9075 8785 5550 2510 936 246 80 10 5 0 1 31950
12 25421 49412 49904 31626 15279 5426 1729 378 113 12 6 0 1 179307

Up to rot & ref, Noncrossing        (by number of singletons)
Triangle A211359 with row sums A111275

0 1 2 3 4 5 6 7 8 9 10 11 12 sum
0 1 1
1 0 1 1
2 1 0 1 2
3 1 1 0 1 3
4 2 1 2 0 1 6
5 2 3 2 2 0 1 10
6 5 4 8 3 3 0 1 24
7 6 11 12 12 4 3 0 1 49
8 14 21 39 24 22 5 4 0 1 130
9 22 55 84 85 48 30 7 4 0 1 336
10 51 124 245 228 190 82 46 8 5 0 1 980
11 95 327 620 730 570 350 136 60 10 5 0 1 2904
12 232 815 1784 2169 2002 1218 645 208 84 12 6 0 1 9176



Subsequences

edit

The by type triangles have some interesting subsequences which are highlighted by colors in the files linked below.

Color Size Integer partition
■ 2n 1 * n    +    n * 1
■ 2n n * 2
□ 2n 2 * n
■ 2n + 1 1 * n    +    (n+1) * 1
■ 2n + 1 n * 1    +    1 * (n+1)
□ 2n + 1 1 * n    +    1 * (n+1)

1 * n + n * 1 stands for the integer partition with one addend n and n addends 1, etc.


All Noncrossing
All

Triangle A211350             

■ 1,6,20,70,252,924...
(2,6,20... are the central binomial coefficients A000984)
■ 1,3,15,105,945,10395...     (double factorial numbers A001147)
□
■
■ □		 1,3,10,35,126,462...     (A001700)
  1,10,35,126,462...
  3,10,35,126,462...     (A001700)

Triangle A211351             

■ 1,6,20,70,252,924...
(2,6,20... are the central binomial coefficients A000984)
■ 1,2,5,14,42,132...     (Catalan numbers A000108)
□ 1,2,3,4,5,6...     (the natural numbers)
■
■		 1,10,35,126,462...
3,10,35,126,462...     (A001700)
□ 3,5,7,9,11     (odd numbers)
Up
to
rot

Triangle A211352             

■ 1,2,4,10,26,80...     (A003239)
■ 1,2,5,18,105,902...     (A007769)
□ 1,2,3,7,15,44...     (A045629)
■ ■ □ 1,2,5,14,42...     (Catalan numbers A000108)

Triangle A211353             

■ 1,2,4,10,26,80...     (A003239)
■ 1,1,2,3,6,14...     (A002995)
□ □ 1,1,1,1,1...
■ ■ 1,2,5,14,42...     (Catalan numbers A000108)
Up
to
rot
&
ref

Triangle A211354             

■ 1,2,3,8,16,50...     (A005648)
■ 1,2,5,17,79,554...     (A054499)
□ 1,2,3,7,13,35...     (A006840?)
■ ■ □ 1,2,4,10,26...     (A003239)

Triangle A211355             

■ 1,2,3,8,16,50...     (A005648)
■ 1,1,2,3,6,12...
□ □ 1,1,1,1,1...
■ ■ 1,2,4,10,26...     (A003239) 


        N   =  0, 1, 2,  3,  4,   5,   6...
A000984(N)  =  1, 2, 6, 20, 70, 252, 924...          (central binomial coefficients)
  • The sequence 1,6,20,70,252,924... appears as All, All ■ and All, Noncrossing ■ :
There is one partition of a 2-set that has a 1-block (i.e. a singleton) and another singleton.
For n>1 there are A000984(n) partitions of a 2n-set that have an n-block and n singletons.


        N   =  0, 1,  2,  3,   4,   5...
A001700(N)  =  1, 3, 10, 35, 126, 462...
  • All, All □ :
There are A001700(n+1) partitions of a 2n-set that have two n-blocks.
  • All, All ■ and All, Noncrossing ■ :
There is one partition of a 3-set that has a 1-block (i.e. a singleton) and two other singletons.
For n>1 there are A001700(n) partitions of a (2n+1)-set that have an n-block and n+1 singletons.
  • All, All ■ and All, Noncrossing ■ :
There are A001700(n) partitions of a (2n+1)-set that have an (n+1)-block and n singletons.
  • All, All □ :
There are A001700(n) partitions of a (2n+1)-set that have an (n+1)-block and an n-block.


        N+   =  1, 2, 3,  4,  5,  6...
A003239(N+)  =  1, 2, 4, 10, 26, 80...
  • Up to rot, All ■ and Up to rot, Noncrossing ■ :
There are A003239(n) necklaces of length 2n with n black and n white beads.
  • Up to rot & ref, All ■ ■ □ and Up to rot & ref, Noncrossing ■ ■ :
There are A003239(n) free necklaces (or bracelets) of length 2n+1 with n black and n+1 white beads.
Retrieved from "https://en.wikiversity.org/w/index.php?title=Partition_related_number_triangles&oldid=2520920"