Transcript A New Connection Between the Triangles of Stirling and Pascal

A New Connection Between the
Triangles of Stirling and Pascal
Craig Bauer
York College of PA
Pascal’s Triangle
Triangular Numbers
Tetrahedral Numbers
Pentatop Numbers
Row Sums – Powers of 2
Fibonacci Numbers
Hockey Stick Patterns
Picture from http://ptri1.tripod.com/
Generating Function
(x+1)n
Shaded Modulo 2
Image from http://wyvern-community.school.hants.gov.uk/sierpinski.htm
Mod 2 with More Rows
Images from http://www.pittstate.edu/math/Cynthia/pascal.html
Mod 3
Mod 4
Mod 5
Mod 6
Mod 7
Investigate for Yourself!
http://binomial.csuhayward.edu/applets
/appletGasket.html
Perfect Numbers
Disclaimer
But the sequence of the number of elements in each
white triangle began with 1 and this isn’t a perfect
number! That’s true, Pascal’s triangle doesn’t always
yield perfect numbers in this manner, but every even
perfect number does appear somewhere in this
sequence. This is because the number of elements in
each white triangle is given by 2n –1(2n – 1). With n = 1,
we get 1. Making n = 2 or 3 gives 6 and 28, respectively.
Every even perfect number is of this form, but not every
number of this form is perfect. What about odd perfect
numbers? Are there any? Nobody knows!
A Simple Pattern
For just one point, we cannot
draw any lines, so have 1
region.
For two points, we may draw
a line to get 2 regions.
A Simple Pattern
For three points, we get
4 regions.
For four points, we get
8 regions.
For five points, we get
16 regions.
Make a Prediction!
We have the sequence 1, 2, 4, 8, 16, …
What will the next term be?
WRONG!
References
*I first saw the problem described above in The (Fabulous)
Fibonacci Numbers by Alfred S. Posamentier and Ingmar
Lehmann, Prometheus Books, June 2007.
*A000127
Partial Row Sums
Some Formulas
Recursive
Non-recursive
George Lilley, Pascal’s Arithmetic Triangle,
American Mathematical Monthly,
Vol. 1, No. 12, Dec., 1894, p.426.
(Well over 200 years after Pascal’s death!)
“This representation comes from China. It dates from a book of 1303 CE written by Chu Shï-kié. The earliest known use
of the pattern was by Yang Hui, whose books date from 1261 & 1275 CE. Chu Shï-kié refers to the triangle as already
being old. Jamshid Al-Kashi, who died around 1436 CE, was an astronomer at the court of Ulugh Beg in Samarkand in
the 15th Century. Al-Kashi was the first known Arabic author to consider 'Pascal's' Triangle.” picture and text from:
http://www.bbc.co.uk/education/asguru/maths/14statistics/03binomialdistribution/8binomialdistribution/index.shtml
Stirling’s Triangle
Where Does it Come From?
• Answer #1 – In how many ways can a set of n
distinct objects be split into k nonempty disjoint
subsets?
• Example: n=4
k=1
k=2
k=3
k=4
Where Does it Come From?
• Answer #2 – How can we express the nth power of
x as a sum of “factorials”?
• Example: x4
x4 = 1x(x – 1)(x – 2)(x – 3)
+6x(x – 1)(x – 2)
+7x(x – 1)
+1x
Coefficients are:
1
6
7
1
Row Sums – Bell Numbers
Exponential Generating Function



k
S (n, k ) x n 1 x
 e 1

n!
k!
n0
Some Formulas
Recursive
Non-recursive
Stirling’s Triangle mod 2
Stirling’s Triangle mod 3
Stirling’s Triangle mod 3
Eighty rows of Stirling Numbers of the second kind mod 3
From http://www.cecm.sfu.ca/~loki/Papers/Numbers/node7.html
Note: This illustration starts with n heap 0 = 0 for each row.
Stirling’s Triangle mod 4
Stirling’s Triangle mod 5
And now for something completely different…
Upper Triangular
Partial Permutation
Matrices
At most a single 1 in any row or
column.
No 1s below the main diagonal.
a

0
0

0

b
e
0
c
f
h
0
0
d

g
i

j 
Examples
1 by 1
0
1
only 2 possibilities
Examples
2 by 2
only 5 possibilities
Examples
3 by 3
only 15 possibilities
Sorted by Dimension & Rank
A New Twist
a

0
0

0

0 c d

e 0 g
0 h 0

0 0 j 
k=1
a

0
0

0

0 0 d

e 0 0
0 h 0

0 0 j 
k=2
a

0
0

0

0 0 0

e 0 0
0 h 0

0 0 j 
k=3
Insist on k extra diagonals of 0s
above the main diagonal.
Counting by Rank (k=1)
A Simple Rule
P(n,k) = P(n – 1,k)
+(n – k)P(n – 1,k – 1)
+P(n – 2,k – 2)
Fibonacci Numbers
Number of n by n matrices of rank n-1 is
Triangular Numbers
Number of n by n matrices of rank 1 is
n + tn–2
More Triangles
We have an infinite sequence of triangles.
They are all distinct.
Comparing terms in a fixed location of the
triangles always gives a decreasing
(convergent) sequence.
The Big Picture
Some Nice General Results
For n ≤ 2k + 2,
Not as General (or Nice)
For n = 2k + 3,
Not Elegant!
For n = 2k + 4,
lim k →∞ ?
Pascal’s Triangle!
k=1 Triangle mod 2
k=1 Triangle mod 3
k=1 Triangle mod 4
k=1 Triangle mod 5
Counting by Rank (k=2)
Molinar’s Conjecture for k = 2
Sullivan’s Result
Pattern?
References
1. Bauer, C., Triangular Monoids and an Analog to
the Derived Sequence of a Solvable Group,
International Journal of Algebra and
Computation, Vol. 10, No. 3 (2000) pp. 309-321.
2. Borwein, D., Rankin, S., and Renner, L.,
Enumeration of Injective Partial Transformations,
Discrete Mathematics, Vol. 73, 1989, p. 291296.
From Wikipedia:
Cereal Box Problem
• The Stirling numbers of the second kind can
represent the total number of ways a person can
collect all prizes after opening a given number of
cereal boxes. For example, if there are 3 prizes,
and one opens three boxes, there is S(3,3), or 1
way to win, {1,2,3}. If 4 boxes are opened, there
are 6 ways to win S(4,3); {1,1,2,3}, {1,2,1,3},
{1,2,3,1}, {1,2,2,3}, {1,2,3,2}, {1,2,3,3}.