Project: Math 152 - Winter 2017

Path: lectures / 2017-02-22 / 2017-02-22.sagews

Views: ¹⁶⁶⁵⁷

Math 152 - Intro to Mathematical Software

2017-02-23

Kiran Kedlaya; University of California, San Diego

adapted from lectures by William Stein, University of Washington

Lecture 18: Combinatorics (part 1)

%md

Sage has *very* well-developed infrastructure for combinatorics, of which we will only scratch the surface here. For PhD-level research in the subject, it is probably the best software available, open-source or otherwise.

Reference: the Sage combinatorics tutorial http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tutorial.html

Sage has very well-developed infrastructure for combinatorics, of which we will only scratch the surface here. For PhD-level research in the subject, it is probably the best software available, open-source or otherwise.

Reference: the Sage combinatorics tutorial http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tutorial.html

To begin with, recall that the number of ways to make an unordered choice of $k$ distinguishable objects from among $n$ given objects is the binomial coefficient $\binom{n}{k} = \frac{n!}{k! (n-k)!}$ where as usual $n! = 1 \times 2 \times \cdots \times n$ denotes the factorial function.

## Count unordered pairs chosen from a set of 6 objects.
binomial(6, 2)

15

multinomial(2,3,5)

2520

You can use the binomial coefficients to count subsets without generating them. However, if you do actually want to generate the list of $k$ -element subsets of a given set, you can do that easily!

l = ["ERC", "Marshall", "Revelle", "Muir", "Warren", "Sixth"]
S = Subsets(l, 2)
print S.cardinality()

15

<class 'sage.combinat.subset.Subsets_sk_with_category'>

S[0]

{'Marshall', 'ERC'}

S[3:5]

[{'Warren', 'ERC'}, {'Sixth', 'ERC'}]

S[1]

{'Revelle', 'ERC'}

list(S)

[{'Marshall', 'ERC'}, {'Revelle', 'ERC'}, {'Muir', 'ERC'}, {'Warren', 'ERC'}, {'Sixth', 'ERC'}, {'Marshall', 'Revelle'}, {'Marshall', 'Muir'}, {'Marshall', 'Warren'}, {'Sixth', 'Marshall'}, {'Revelle', 'Muir'}, {'Revelle', 'Warren'}, {'Sixth', 'Revelle'}, {'Muir', 'Warren'}, {'Sixth', 'Muir'}, {'Sixth', 'Warren'}]

The Subsets function is an example of a structured set construction. Another important example is the Cartesian product; let's see an example based on playing cards.

suits = ["Clubs", "Diamonds", "Hearts", "Spades"]
ranks = ["Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King"]
deck = cartesian_product([suits, ranks])

type(deck)

<class 'sage.sets.cartesian_product.CartesianProduct_with_category'>

deck[1]

('Clubs', '2')

Another example is the set of permutations of a list.

print list(Permutations([1,2,3]))

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

print list(Permutations([1,2,1,3]))

[[1, 1, 2, 3], [1, 1, 3, 2], [1, 2, 1, 3], [1, 2, 3, 1], [1, 3, 1, 2], [1, 3, 2, 1], [2, 1, 1, 3], [2, 1, 3, 1], [2, 3, 1, 1], [3, 1, 1, 2], [3, 1, 2, 1], [3, 2, 1, 1]]

Exercise for right now: Use the Permutations function to "shuffle" the deck, i.e., pick a random permutation. (Hint: use the random_element method.)

Permutations(deck).random_element()

[('Hearts', '2'), ('Hearts', '8'), ('Clubs', '3'), ('Clubs', '2'), ('Spades', '10'), ('Diamonds', 'Jack'), ('Hearts', 'Ace'), ('Clubs', '8'), ('Diamonds', '9'), ('Diamonds', 'Queen'), ('Diamonds', '5'), ('Clubs', '7'), ('Hearts', '10'), ('Clubs', 'Queen'), ('Hearts', 'Queen'), ('Hearts', '6'), ('Spades', '7'), ('Spades', 'King'), ('Spades', 'Queen'), ('Hearts', 'Jack'), ('Spades', '6'), ('Hearts', '3'), ('Hearts', '9'), ('Spades', '9'), ('Diamonds', 'King'), ('Diamonds', 'Ace'), ('Spades', 'Ace'), ('Diamonds', '7'), ('Diamonds', '6'), ('Diamonds', '10'), ('Spades', '4'), ('Spades', 'Jack'), ('Clubs', '5'), ('Hearts', 'King'), ('Spades', '2'), ('Clubs', 'Jack'), ('Hearts', '7'), ('Clubs', 'Ace'), ('Clubs', '9'), ('Clubs', '4'), ('Diamonds', '8'), ('Spades', '3'), ('Spades', '5'), ('Diamonds', '4'), ('Hearts', '4'), ('Diamonds', '3'), ('Clubs', '6'), ('Clubs', '10'), ('Clubs', 'King'), ('Spades', '8'), ('Diamonds', '2'), ('Hearts', '5')]

Subsets(deck, 13).random_element()

{('Diamonds', '2'), ('Spades', '2'), ('Spades', 'King'), ('Hearts', '9'), ('Clubs', 'Ace'), ('Diamonds', '4'), ('Spades', '8'), ('Hearts', 'King'), ('Clubs', '2'), ('Spades', '5'), ('Diamonds', '9'), ('Spades', 'Queen'), ('Diamonds', '8')}

Another example is the set of partitions of a given nonnegative integer. Let's illustrate with an example:

print list(Partitions(5))

[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]

print list(Partitions(7))

[[7], [6, 1], [5, 2], [5, 1, 1], [4, 3], [4, 2, 1], [4, 1, 1, 1], [3, 3, 1], [3, 2, 2], [3, 2, 1, 1], [3, 1, 1, 1, 1], [2, 2, 2, 1], [2, 2, 1, 1, 1], [2, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1]]

There is a method for counting partitions without enumerating them.

%time n = Partitions(10^12).cardinality()

print N(log(n, 10)) ## This number has over 1 million digits! Let's not print it.

CPU time: 25.63 s, Wall time: 48.81 s
1.11399578738969e6

Partitions(10^6).random_element()

Error in lines 1-1
Traceback (most recent call last):
  File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 982, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/combinat/partition.py", line 5898, in random_element
    return self.random_element_uniform()
  File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/combinat/partition.py", line 5966, in random_element_uniform
    rand -= d * cached_number_of_partitions(r)
  File "sage/misc/cachefunc.pyx", line 1059, in sage.misc.cachefunc.CachedFunction.__call__ (/projects/sage/sage-7.5/src/build/cythonized/sage/misc/cachefunc.c:6077)
    w = self.f(*args, **kwds)
  File "sage/libs/flint/arith.pyx", line 165, in sage.libs.flint.arith.number_of_partitions (/projects/sage/sage-7.5/src/build/cythonized/sage/libs/flint/arith.c:2997)
    sig_on()
  File "src/cysignals/signals.pyx", line 97, in cysignals.signals.sig_raise_exception (build/src/cysignals/signals.c:1303)
KeyboardInterrupt

One can also enumerate partitions where the parts have fixed size, e.g., making change:

WeightedIntegerVectors(37, [1,5,10,25]).list()

[[2, 0, 1, 1], [2, 2, 0, 1], [7, 1, 0, 1], [12, 0, 0, 1], [2, 1, 3, 0], [7, 0, 3, 0], [2, 3, 2, 0], [7, 2, 2, 0], [12, 1, 2, 0], [17, 0, 2, 0], [2, 5, 1, 0], [7, 4, 1, 0], [12, 3, 1, 0], [17, 2, 1, 0], [22, 1, 1, 0], [27, 0, 1, 0], [2, 7, 0, 0], [7, 6, 0, 0], [12, 5, 0, 0], [17, 4, 0, 0], [22, 3, 0, 0], [27, 2, 0, 0], [32, 1, 0, 0], [37, 0, 0, 0]]

... or solving the (original) Chicken McNuggets problem: https://en.wikipedia.org/wiki/Coin_problem

WeightedIntegerVectors(92, [6,9,20]).list()

[[2, 0, 4], [0, 8, 1], [3, 6, 1], [6, 4, 1], [9, 2, 1], [12, 0, 1]]

Many combinatorics problems lead naturally to integer sequences. These can be looked up in the On-line Encyclopedia of Integer Sequences (OEIS): http://oeis.org; but better yet, this database is integrated into Sage!

oeis([1,2,3,5,8,13], max_results=4) # requires internet access

A000045: Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
A027926: Triangular array T read by rows: T(n,0) = T(n,2n) = 1 for n >= 0; T(n,1) = 1 for n >= 1; T(n,k) = T(n-1,k-2) + T(n-1,k-1) for k = 2..2n-1, n >= 2.
A001129: Iccanobif numbers: reverse digits of two previous terms and add.
A014260: Iccanobif numbers: add a(n-1) to reversal of a(n-2).

Maybe a less familiar example: let's count set partitions of {1, ..., n}.

list(SetPartitions([1..4]))

[{{1, 2, 3, 4}}, {{1}, {2, 3, 4}}, {{1, 3, 4}, {2}}, {{1, 2, 4}, {3}}, {{1, 2, 3}, {4}}, {{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2, 3}}, {{1}, {2}, {3, 4}}, {{1}, {2, 4}, {3}}, {{1}, {2, 3}, {4}}, {{1, 4}, {2}, {3}}, {{1, 3}, {2}, {4}}, {{1, 2}, {3}, {4}}, {{1}, {2}, {3}, {4}}]

l = [SetPartitions([1..n]).cardinality() for n in [1..10]]
print l

[1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975]

oeis(l, max_results=4)

A000110: Bell or exponential numbers: number of ways to partition a set of n labeled elements.
A164864: Number of ways of placing n labeled balls into 10 indistinguishable boxes; word structures of length n using a 10-ary alphabet.
A276726: Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most ten elements.
A229227: The partition function G(n,10).

%md
Aha, let's read about that first one some more.

Aha, let's read about that first one some more.

t = oeis('A000110')

#What methods?
t.name()

'Bell or exponential numbers: number of ways to partition a set of n labeled elements.'

t.comments()

The leading diagonal of its difference table is the sequence shifted, see Bernstein and Sloane (1995). - _N. J. A. Sloane_, Jul 04 2015
Also the number of equivalence relations that can be defined on a set of n elements. - Federico Arboleda (federico.arboleda(AT)gmail.com), Mar 09 2005
a(n) = number of nonisomorphic colorings of a map consisting of a row of n+1 adjacent regions. Adjacent regions cannot have the same color. - _David W. Wilson_, Feb 22 2005
If an integer is squarefree and has n distinct prime factors then a(n) is the number of ways of writing it as a product of its divisors. - _Amarnath Murthy_, Apr 23 2001
Consider rooted trees of height at most 2. Letting each tree 'grow' into the next generation of n means we produce a new tree for every node which is either the root or at height 1, which gives the Bell numbers. - _Jon Perry_, Jul 23 2003
Begin with [1,1] and follow the rule that [1,k] -> [1,k+1] and [1,k] k times, e.g., [1,3] is transformed to [1,4], [1,3], [1,3], [1,3]. Then a(n) is the sum of all components. [1,1]=2, [1,2], [1,1]=5, [1,3], [1,2], [1,2],[1,1], [1,2]=15, etc. - _Jon Perry_, Mar 05 2004
Number of distinct rhyme schemes for a poem of n lines: a rhyme scheme is a string of letters (e.g., 'abba') such that the leftmost letter is always 'a' and no letter may be greater than one more than the greatest letter to its left. Thus 'aac' is not valid since 'c' is more than one greater than 'a'. For example, a(3)=5 because there are 5 rhyme schemes: aaa, aab, aba, abb, abc; also see example by Neven Juric. - _Bill Blewett_, Mar 23 2004
In other words, number of length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(0)=0 and s(k)<=1+max(prefix) for k>=1, see example (cf. A080337 and A189845). - _Joerg Arndt_, Apr 30 2011
Number of partitions of {1, ...,n+1} into subsets of nonconsecutive integers, including the partition 1|2|...|n+1. E.g., a(3)=5: there are 5 partitions of {1,2,3,4} into subsets of nonconsecutive integers, namely, 13|24, 13|2|4, 14|2|3, 1|24|3, 1|2|3|4. - _Augustine O. Munagi_, Mar 20 2005
Triangle (addition) scheme to produce terms, derived from the recurrence, from Oscar Arevalo (loarevalo(AT)sbcglobal.net), May 11 2005:
    1
    1  2
    2  3  5
    5  7 10 15
   15 20 27 37 52
   ... [This is Aitken's array A011971]
With P(n) = the number of integer partitions of n, p(i) = the number of parts of the i-th partition of n, d(i) = the number of different parts of the i-th partition of n, p(j,i) = the j-th part of the i-th partition of n, m(i,j) = multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i=1..P(n)} (n!/(Product_{j=1..p(i)}p(i,j)!)) * (1/(Product_{j=1..d(i)} m(i,j)!)) - _Thomas Wieder_, May 18 2005
a(n+1) is the number of binary relations on an n-element set that are both symmetric and transitive. - Justin Witt (justinmwitt(AT)gmail.com), Jul 12 2005
If Jon Perry's rule is used, i.e., "Begin with [1,1] and follow the rule that [1,k] -> [1,k+1] and [1,k] k times, e.g., [1,3] is transformed to [1,4], [1,3], [1,3], [1,3]. Then a(n) is the sum of all components. [1,1]=2, [1,2],[1,1]=5, [1,3],[1,2],[1,2],[1,1],[1,2]=15, etc..." then a(n-1) = [number of components used to form a(n)] / 2. - Daniel Kuan (dkcm(AT)yahoo.com), Feb 19 2006
a(n) is the number of functions f from {1,...,n} to {1,...,n,n+1} that satisfy the following two conditions for all x in the domain: (1) f(x)>x; (2)f(x)=n+1 or f(f(x))=n+1. E.g., a(3)=5 because there are exactly five functions that satisfy the two conditions: f1={(1,4),(2,4),(3,4)}, f2={(1,4),(2,3),(3,4)}, f3={(1,3),(2,4),(3,4)}, f4={(1,2),(2,4),(3,4)} and f5={(1,3),(2,3),(3,4)}. - _Dennis P. Walsh_, Feb 20 2006
Number of asynchronic siteswap patterns of length n which have no zero-throws (i.e., contain no 0's) and whose number of orbits (in the sense given by Allen Knutson) is equal to the number of balls. E.g., for n=4, the condition is satisfied by the following 15 siteswaps: 4444, 4413, 4242, 4134, 4112, 3441, 2424, 1344, 2411, 1313, 1241, 2222, 3131, 1124, 1111. Also number of ways to choose n permutations from identity and cyclic permutations (1 2), (1 2 3), ..., (1 2 3 ... n) so that their composition is identity. For n=3 we get the following five: id o id o id, id o (1 2) o (1 2), (1 2) o id o (1 2), (1 2) o (1 2) o id, (1 2 3) o (1 2 3) o (1 2 3). (To see the bijection, look at Ehrenborg and Readdy paper.) - _Antti Karttunen_, May 01 2006
a(n) is the number of permutations on [n] in which a 3-2-1 (scattered) pattern occurs only as part of a 3-2-4-1 pattern. Example: a(3) = 5 counts all permutations on [3] except 321. See "Eigensequence for Composition" reference a(n) = number of permutation tableaux of size n (A000142) whose first row contains no 0's. Example: a(3)=5 counts {{}, {}, {}}, {{1}, {}}, {{1}, {0}}, {{1}, {1}}, {{1, 1}}. - _David Callan_, Oct 07 2006
Take the series 1^n/1! + 2^n/2! + 3^n/3! + 4^n/4! ... If n=1 then the result will be e, about 2.71828. If n=2, the result will be 2e. If n=3, the result will be 5e. This continues, following the pattern of the Bell numbers: e, 2e, 5e, 15e, 52e, 203e, etc. - Jonathan R. Love (japanada11(AT)yahoo.ca), Feb 22 2007
From _Gottfried Helms_, Mar 30 2007: (Start)
This sequence is also the first column in the matrix-exponential of the (lower triangular) Pascal-matrix, scaled by exp(-1): PE = exp(P) / exp(1) =
     1
     1    1
     2    2    1
     5    6    3    1
    15   20   12    4    1
    52   75   50   20    5    1
   203  312  225  100   30    6   1
   877 1421 1092  525  175   42   7   1
First 4 columns are A000110, A033306, A105479, A105480. The general case is mentioned in the two latter entries. PE is also the Hadamard-product Toeplitz(A000110) (X) P:
     1
     1    1
     2    1    1
     5    2    1    1
    15    5    2    1    1      (X) P
    52   15    5    2    1    1
   203   52   15    5    2    1   1
   877  203   52   15    5    2   1   1
(End)
The terms can also be computed with finite steps and precise integer arithmetic. Instead of exp(P)/exp(1) one can compute A = exp(P - I) where I is the identity-matrix of appropriate dimension since (P-I) is nilpotent to the order of its dimension. Then a(n)=A[n,1] where n is the row-index starting at 1. - _Gottfried Helms_, Apr 10 2007
Define a Bell pseudoprime to be a composite number n such that a(n) == 2 (mod n). W. F. Lunnon recently found the Bell pseudoprimes 21361 = 41*521 and C46 = 3*23*16218646893090134590535390526854205539989357 and conjectured that Bell pseudoprimes are extremely scarce. So the second Bell pseudoprime is unlikely to be known with certainty in the near future. I confirmed that 21361 is the first. - _David W. Wilson_, Aug 04 2007 and Sep 24 2007
This sequence and A000587 form a reciprocal pair under the list partition transform described in A133314. - _Tom Copeland_, Oct 21 2007
Starting (1, 2, 5, 15, 52, ...), equals row sums and right border of triangle A136789. Also row sums of triangle A136790. - _Gary W. Adamson_, Jan 21 2008
This is the exponential transform of A000012. - _Thomas Wieder_, Sep 09 2008
From _Abdullahi Umar_, Oct 12 2008: (Start)
a(n) is also the number of idempotent order-decreasing full transformations (of an n-chain).
a(n) is also the number of nilpotent partial one-one order-decreasing transformations (of an n-chain).
a(n+1) is also the number of partial one-one order-decreasing transformations (of an n-chain). (End)
From _Peter Bala_, Oct 19 2008: (Start)
Bell(n) is the number of n-pattern sequences [Cooper & Kennedy]. An n-pattern sequence is a sequence of integers (a_1,...,a_n) such that a_i = i or a_i = a_j for some j < i. For example, Bell(3) = 5 since the 3-pattern sequences are (1,1,1), (1,1,3), (1,2,1), (1,2,2) and (1,2,3).
Bell(n) is the number of sequences of positive integers (N_1,...,N_n) of length n such that N_1 = 1 and N_(i+1) <= 1 + max{j = 1..i} N_j for i >= 1 (see the comment by B. Blewett above). It is interesting to note that if we strengthen the latter condition to N_(i+1) <= 1 + N_i we get the Catalan numbers A000108 instead of the Bell numbers.
(End)
Equals the eigensequence of Pascal's triangle, A007318; and starting with offset 1, = row sums of triangles A074664 and A152431. - _Gary W. Adamson_, Dec 04 2008
The entries f(i, j) in the exponential of the infinite lower-triangular matrix of binomial coefficients b(i, j) are f(i, j) = b(i, j) e a(i - j). - _David Pasino_, Dec 04 2008
Equals Lim_{k->inf.} A071919^k. - _Gary W. Adamson_, Jan 02 2009
Equals A154107 convolved with A014182, where A014182 = expansion of exp(1-x-exp(-x)), the eigensequence of A007318^(-1). Starting with offset 1 = A154108 convolved with (1,2,3,...) = row sums of triangle A154109. - _Gary W. Adamson_, Jan 04 2009
Repeated iterates of (binomial transform of [1,0,0,0,...]) will converge upon (1, 2, 5, 15, 52,...) when each result is prefaced with a "1"; such that the final result is the fixed limit: (binomial transform of [1,1,2,5,15,...] = (1,2,5,15,52,...). - _Gary W. Adamson_, Jan 14 2009
From _Karol A. Penson_, May 03 2009: (Start)
Relation between the Bell numbers B(n) and the n-th derivative of 1/Gamma(1+x) of such derivatives through seq(subs(x=0, simplify(diff(GAMMA(1+x)^(-1),x$n))), n=1..6);
b) leave them expressed in terms of digamma (Psi(k)) and polygamma (Psi(k,n)) functions and unevaluated;
Examples of such expressions, for n=1..5, are:
n=1: -Psi(1),
n=2: -(-Psi(1)^2+Psi(1,1)),
n=3: -Psi(1)^3+3*Psi(1)*Psi(1,1)-Psi(2,1),
n=4: -(-Psi(1)^4+6*Psi(1)^2*Psi(1,1)-3*Psi(1,1)^2-4*Psi(1)*Psi(2,1)+Psi(3, 1)),
n=5: -Psi(1)^5 +10*Psi(1)^3*Psi(1,1) -15*Psi(1)*Psi(1,1)^2 -10*Psi(1)^2*Psi(2,1) +10*Psi(1,1)*Psi(2,1) +5*Psi(1)*Psi(3,1) -Psi(4,1);
c) for a given n, read off the sum of absolute values of coefficients of every term involving digamma or polygamma functions.
This sum is equal to B(n). Examples: B(1)=1, B(2)=1+1=2, B(3)=1+3+1=5, B(4)=1+6+3+4+1=15, B(5)=1+10+15+10+10+5+1=52;
d) Observe that this decomposition of the Bell number B(n) apparently does not involve the Stirling numbers of the second kind explicitly.
(End)
The numbers given above by Penson lead to the multinomial coefficients A036040. - _Johannes W. Meijer_, Aug 14 2009
Column 1 of A162663. - _Franklin T. Adams-Watters_, Jul 09 2009
Asymptotic expansions (0!+1!+2!+...+(n-1)!)/(n-1)! = a(0) + a(1)/n + a(2)/n^2 + ... and (0!+1!+2!+...+n!)/n! = 1 + a(0)/n + a(1)/n^2 + a(2)/n^3 + .... - _Michael Somos_, Jun 28 2009
Starting with offset 1 = row sums of triangle A165194. - _Gary W. Adamson_, Sep 06 2009
a(n+1) = A165196(2^n); where A165196 begins: (1, 2, 4, 5, 7, 12, 14, 15, ...). such that A165196(2^3) = 15 = A000110(4). - _Gary W. Adamson_, Sep 06 2009
The divergent series g(x=1,m) = 1^m*1! - 2^m*2! + 3^m*3! - 4^m*4! + ..., m >= -1, which for m=-1 dates back to Euler, is related to the Bell numbers. We discovered that g(x=1,m) = (-1)^m * (A040027(m) - A000110(m+1) * A073003). We observe that A073003 is Gompertz's constant and that A040027 was published by Gould, see for more information A163940. - _Johannes W. Meijer_, Oct 16 2009
a(n)= E(X^n), i.e., the n-th moment about the origin of a random variable X that has a Poisson distribution with (rate) parameter, lambda = 1. - _Geoffrey Critzer_, Nov 30 2009
Let A000110 = S(x), then S(x) = A(x)/A(x^2) when A(x) = A173110; or (1, 1, 2, 5, 15, 52, ...) = (1, 1, 3, 6, 20, 60, ...) / (1, 0, 1, 0, 3, 0, 6, 0, 20, ...). - _Gary W. Adamson_, Feb 09 2010
The Bell numbers serve as the upper limit for the number of distinct homomorphic images from any given finite universal algebra. Every algebra homomorphism is determined by its kernel, which must be a congruence relation. As the number of possible congruence relations with respect to a finite universal algebra must be a subset of its possible equivalence classes (given by the Bell numbers), it follows naturally. - _Max Sills_, Jun 01 2010
For a proof of the o.g.f. given in the R. Stephan comment see, e.g., the W. Lang link under A071919. - _Wolfdieter Lang_, Jun 23 2010
Let B(x) = (1 + x + 2x^2 + 5x^3 + ...). Then B(x) is satisfied by A(x)/A(x^2) where A(x) = polcoeff A173110: (1 + x + 3x^2 + 6x^3 + 20x^4 + 60x^5 + ...) = B(x) * B(x^2) * B(x^4) * B(x^8) * .... - _Gary W. Adamson_, Jul 08 2010
Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1) equals the number of ways to choose 0 or more balls of each color without choosing any two colors the same positive number of times. (See related comments for A000108, A008277, A016098.) - _Matthew Vandermast_, Nov 22 2010
A binary counter with faulty bits starts at value 0 and attempts to increment by 1 at each step. Each bit that should toggle may or may not do so. a(n) is the number of ways that the counter can have the value 0 after n steps. E.g., for n=3, the 5 trajectories are 0,0,0,0; 0,1,0,0; 0,1,1,0; 0,0,1,0; 0,1,3,0. - _David Scambler_, Jan 24 2011
No Bell number is divisible by 8, and no Bell number is congruent to 6 modulo 8; see Theorem 6.4 and Table 1.7 in Lunnon, Pleasants and Stephens. - _Jon Perry_, Feb 07 2011, clarified by _Eric Rowland_, Mar 26 2014
a(n+1) is the number of (symmetric) positive semidefinite n X n 0-1 matrices. These correspond to equivalence relations on {1,...,n+1}, where matrix element M[i,j] = 1 if and only if i and j are equivalent to each other but not to n+1. - _Robert Israel_, Mar 16 2011
a(n) is the number of monotonic-labeled forests on n vertices with rooted trees of height less than 2. We note that a labeled rooted tree is monotonic-labeled if the label of any parent vertex is greater than the label of any offspring vertex. See link "Counting forests with Stirling and Bell numbers". - _Dennis P. Walsh_, Nov 11 2011
a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A000772 and A094198. - _Peter Bala_, Nov 25 2011
B(n) counts the length n+1 rhyme schemes without repetitions. E.g., for n=2 there are 5 rhyme schemes of length 3 (aaa, aab, aba, abb, abc), and the 2 without repetitions are aba, abc. This is basically O. Munagi's result that the Bell numbers count partitions into subsets of nonconsecutive integers (see comment above dated Mar 20 2005). - Eric Bach, Jan 13 2012
Number n is prime if mod(a(n)-2,n) = 0. -_Dmitry Kruchinin_, Feb 14 2012
Right and left borders and row sums of A212431 = A000110 or a shifted variant. - _Gary W. Adamson_, Jun 21 2012
Number of maps f: [n] -> [n] where f(x)<=x and f(f(x))=f(x) (projections). - _Joerg Arndt_, Jan 04 2013
Permutations of [n] avoiding any given one of the 8 dashed patterns in the equivalence classes (i) 1-23, 3-21, 12-3, 32-1, and (ii) 1-32, 3-12, 21-3, 23-1. (See Claesson 2001 reference.) - _David Callan_, Oct 03 2013
Conjecture: No a(n) has the form x^m with m > 1 and x > 1. - _Zhi-Wei Sun_, Dec 02 2013
Sum_{n>=0} a(n)/n! = e^(e-1) = 5.57494152476... , see A234473. - _Richard R. Forberg_, Dec 26 2013 (This is the e.g.f. for x=1. - _Wolfdieter Lang_, Feb 02 2015)
Sum_{j=0..n} binomial(n,j)*a(j) = (1/e)*Sum_{k>=0} (k+1)^n/k! = (1/e) Sum_{k=1..infinity} k^(n+1)/k! = a(n+1), n >= 0, using the Dobinski formula. See the comment by _Gary W. Adamson_, Dec 04 2008 on the Pascal eigensequence. - _Wolfdieter Lang_, Feb 02 2015
In fact it is not really an eigensequence of the Pascal matrix; rather the Pascal matrix acts on the sequence as a shift. It is an eigensequence (the unique eigensequence with eigenvalue 1) of the matrix derived from the Pascal matrix by adding at the top the row [1, 0, 0, 0 ...]. The binomial sum formula may be derived from the definition in terms of partitions: label any element X of a set S of N elements, and let X(k) be the number of subsets of S containing X with k elements. Since each subset has a unique coset, the number of partitions p(N) of S is given by p(N) = Sum_{k=1..N} (X(k) p(N-k)); trivially X(k) = N-1 choose k-1. - _Mason Bogue_, Mar 20 2015
a(n) is the number of ways to nest n matryoshkas (Russian nesting dolls): we may identify {1, 2, ..., n} with dolls of ascending sizes and the sets of a set partition with stacks of dolls. - _Carlo Sanna_, Oct 17 2015
Number of permutations of [n] where the initial elements of consecutive runs of increasing elements are in decreasing order. a(4) = 15: `1234, `2`134, `23`14, `234`1, `24`13, `3`124, `3`2`14, `3`24`1, `34`12, `34`2`1, `4`123, `4`2`13, `4`23`1, `4`3`12, `4`3`2`1. - _Alois P. Heinz_, Apr 27 2016
Taking with alternating signs, the Bell numbers are the coefficients in the asymptotic expansion (Ramanujan): (-1)^n*(A000166(n) - n!/exp(1)) ~ 1/n - 2/n^2 + 5/n^3 - 15/n^4 + 52/n^5 - 203/n^6 + O(1/n^7). - _Vladimir Reshetnikov_, Nov 10 2016
Number of treeshelves avoiding pattern T231. See A278677 for definitions and examples. - _Sergey Kirgizov_, Dec 24 2016
Presumably this satisfies Benford's law, although the results in Hürlimann (2009) do not make this clear. - _N. J. A. Sloane_, Feb 09 2017

Note in passing: many of these constructors are examples of Python iterators, which are effectively implicit tuples: the objects are only produced on demand.

The itertools module provides some useful functionality:

https://docs.python.org/2/library/itertools.html

(Reminder: Sage uses Python 2; some syntax is different in Python 3.)

%python
import itertools
list(itertools.permutations([1, 2, 3, 4]))

[(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]

Math 152 - Intro to Mathematical Software

2017-02-23

Kiran Kedlaya; University of California, San Diego

adapted from lectures by William Stein, University of Washington

** Lecture 18: Combinatorics (part 1) **

Lecture 18: Combinatorics (part 1)