Locally restricted compositions II: General restrictions, in preparation (2009)
Edward A. Bender, E. Rodney Canfield
We study compositions ⃗c = (c1,..., ck) of the integer n in which the value ci of the ith part is constrained based on previous parts within a fixed distance of ci. The constraints may depend on i...
Asymptotic enumeration of correlation-immune boolean functions (2009)
Canfield, E. Rodney, Gao, Zhicheng, Greenhill, Catherine, McKay, Brendan D., Robinson, Robert W.
A boolean function of $n$ boolean variables is {correlation-immune} of order $k$ if the function value is uncorrelated with the values of any $k$ of the arguments. Such functions are of considerable...
The Mahonian probability distribution on words is asymptotically normal (2009)
Canfield, E. Rodney, Janson, Svante, Zeilberger, Doron
The Mahonian statistic is the number of inversions in a permutation of a multiset with $a_i$ elements of type $i$, $1\le i\le m$. The counting function for this statistic is the $q$ analog of the...
Coefficients of Functional Compositions Often Grow Smoothly (2009)
Edward A. Bender, E. Rodney Canfield, L. Bruce Richmond
Research supported by the NSA Mathematical Sciences Program. Research support by the NSERC. The coefficients of a power series A(x) are smooth if an−1/an approaches a limit. If A(x) = F (G(x)) and...
General Terms Document Transformation, Design of Algorithm (2008)
Regular Hedge Grammar is a formal method to specify XML schema. XML document can be viewed as an ordered labeled tree. Computing the approximate matching between an XML document with a schema with...
A Discontinuity in the Distribution of Fixed Point Sums (2008)
Edward A. Bender, E. Rodney Canfield, L. Bruce Richmond, Herbert S. Wilf
the electronic journal of combinatorics 10 (2003), #R15 1 The quantity f(n, r), defined as the number of permutations of the set [n] = {1,2,...n} whose fixed points sum to r, shows a sharp...
/res/papers/maps/FDEG.TEX 4/24/2003 The number of degree restricted rooted maps on the sphere (2008)
Edward A. Bender, E. Rodney Canfield
Running head: Counting degree restricted maps
E. Rodney Canfield, Carla D. Savage, Herbert S. Wilf
For integer partitions λ: n = a1 +... + ak, where a1 ≥ a2 ≥... ≥ ak ≥ 1, we study the sum a1 + a3 +... of the parts of odd index. We show that the average of this sum, over all partitions λ...
Edward A. Bender, E. Rodney Canfield
The weight of a vector in the finite vector space GF(q) n is the number of nonzero components it contains. We show that for a certain range of parameters (n; j; k; w) the number of k-dimensional...
Dedicated to the memory of Gian-Carlo Rota (2007)
Neil J. Calkin, Herbert S. Wilf, E. Rodney Canfield
We answer a question posed by Lampert and Slater [7]. Consider a sequence of real numbers qn in the interval [0,1] defined by q0 =0,q1 = 1, and, for n ≥ 1, qn+1 equals an average of preceding terms...
The Fraction of Subspaces of (2007)
Gf With Specified, Edward A. Bender, E. Rodney Canfield
The weight of a vector in the finite vector space GF(q) n is the number of nonzero components it contains. We show that for a certain range of parameters (n; j; k; w) the number of k-dimensional...
The Asymptotic Number of Labeled Graphs With (2007)
Vertices Edges And, Edward A. Bender, Brendan D. Mckay, E. Rodney Canfield, E. Rodney Canfield
Let d(n; q) be the number of labeled graphs with n vertices, q N = \Gamma n 2 \Delta edges, and no isolated vertices. Let x = q=n and k = 2q \Gamma n. We determine functions w k 1, a(x), and...
Submitted: August 3, 1999; Accepted: September 26, 1999 (2007)
Te Mb Er, Edward A. Bender, E. Rodney Canfield
Suppose that t 2 is an integer, and randomly label t graphs with the integers 1 : : : n. We give sufficient conditions for the number of edges common to all t of the labelings to be asymptotically...
Guo-qiang Zhang, E. Rodney Canfield
this article is to introduce a new lemma for regular sets. The new lemma states that if L is a regular language over \Sigma, then
Guo-qiang Zhang, E. Rodney Canfield
this article is to introduce a new lemma for regular sets. The new lemma states that if
Edward A. Bender, E. Rodney Canfield
The weight of a vector in the finite vector space GF(q) n is the number of nonzero components it contains. We show that for a certain range of parameters (n, j, k, w) the number of k-dimensional...
E. Rodney Canfield, Guangming Xing
The role of regular languages and finite automata is becoming more and more important because of the overwhelming use of internet and its applications. Regular expression is an elegant way to specify...
E. Rodney Canfield, Konrad Engel, Prof Konrad Engel
upper bound for the size of the largest antichain
The number of distinct alignments of two strings (2007)
Michael A. Covington, E. Rodney Canfield
An alignment is a way of pairing up elements of two strings, optionally skipping some elements but preserving the order. For example,
E. Rodney Canfield, Carla D. Savage
Let F(n) be a family of partitions of n and let F(n; d) denote the set of partitions in F(n) with Durfee square of size d. We define the Durfee polynomial of F(n) to be the polynomial PF;n = P jF(n;...
Meet and join within the lattice of set partitions (2007)
We build on work of Boris Pittel [5] concerning the number of t-tuples of partitions whose meet (join) is the minimal (maximal) element in the lattice of set partitions. 1
A Discontinuity in the Distribution of Fixed Point Sums (2007)
Edward A. Bender, E. Rodney Canfield, L. Bruce Richmond, Herbert S. Wilf
The quantity f(n, r), defined as the number of permutations of the set [n] = 2, . . . n} whose fixed points sum to r, shows a sharp discontinuity in the neighborhood of r = n. We explain this...
A Discontinuity in the Distribution of Fixed Point Sums (2007)
Edward A. Bender, E. Rodney Canfield, L. Bruce Richmond, Herbert S. Wilf
the electronic journal of combinatorics 10 (2003), #R15 1 The quantity f(n, r), defined as the number of permutations of the set [n] = {1, 2,...n} whose fixed points sum to r, shows a sharp...
A Discontinuity in the Distribution of Fixed Point Sums (2007)
Edward A. Bender, E. Rodney Canfield, L. Bruce Richmond, Herbert S. Wilf
The quantity f(n; r), de ned as the number of permutations of the set [n] = f1; 2; : : : ng whose xed points sum to r, shows a sharp discontinuity in the neighborhood of r = n. We explain this...
Regularly Spaced Subsums of Integer Partitions (2007)
E. Rodney Canfield, Can Eld, Carla D. Savage, Herbert S. Wilf
For integer partitions : n = a 1 + ::: + a k , where a 1 a 2 : : : a k 1, we study the sum a 1 + a 3 + : : : of the parts of odd index. We show that the average of this sum, over all partitions of n,...
The asymptotic volume of the Birkhoff polytope (2007)
Canfield, E. Rodney, McKay, Brendan D.
Let m,n be positive integers. Define T(m,n) to be the transportation polytope consisting of the m x n non-negative real matrices whose rows each sum to 1 and whose columns each sum to m/n. The...
Asymptotic enumeration of contingency tables with constant margins (2007)
Canfield, E. Rodney, McKay, Brendan D.
Let s,t,m,n be positive integers such that sm=tn. Let M(m,s;n,t) be the number of m x n matrices over {0,1,2,...} with each row summing to s and each column summing to t. Equivalently, M(m,s;n,t)...
Counting permutations by their runs up and down (2006)
Canfield, E. Rodney, Wilf, Herbert S.
We find a formula for the number of permutations of $[n]$ that have exactly $s$ runs up and down. The formula is at once terminating, asymptotic, and exact.
Asymptotic enumeration of dense 0-1 matrices with specified line sums (2006)
Canfield, E. Rodney, Greenhill, Catherine, McKay, Brendan D.
Let S=(s_1,s_2,..., s_m) and T = (t_1,t_2,..., t_n) be vectors of non-negative integers with sum_{i=1}^{m} s_i = sum_{j=1}^n t_j. Let B(S,T) be the number of m*n matrices over {0,1} with j-th row sum...
Locally restricted compositions, I. Restricted adjacent differences, Electron (2005)
Edward A. Bender, E. Rodney Canfield
We study compositions of the integer n in which the first part, successive differences, and the last part are constrained to lie in prescribed sets L, D, R, respectively. A simple condition on D...
Regularly spaced subsums of integer partitions (2003)
Canfield, E. Rodney, Savage, Carla D., Wilf, Herbert S.
For integer partitions $\lambda :n=a_1+...+a_k$, where $a_1\ge a_2\ge >...\ge a_k\ge 1$, we study the sum $a_1+a_3+...$ of the parts of odd index. We show that the average of this sum, over all...
A Discontinuity in the Distribution of Fixed Point Sums (2003)
Bender, Edward A., Canfield, E. Rodney, Richmond, L. Bruce, Wilf, Herbert S.
The quantity $f(n,r)$, defined as the number of permutations of the set $[n]=\{1,2,... n\}$ whose fixed points sum to $r$, shows a sharp discontinuity in the neighborhood of $r=n$. We explain this...
E. Rodney Canfield, Carl Pomerance
Say that an integer n is exceptional if the maximum Stirling number of the second kind S(n, k) occurs for two (of necessity consecutive) values of k. We prove that the number of exceptional integers...
Log-Concavity and Related Properties of the Cycle Index Polynomials (1999)
Edward A. Bender, E. Rodney Canfield
Let An denote the n-th cycle index polynomial, in the variables X j , for the symmetric group on n letters. We show that if the variables X j are assigned nonnegative real values which are...
Asymptotic Properties of Labeled Connected Graphs (1999)
Edward A. Bender, E. Rodney Canfield, Brendan D. Mckay
We prove various properties of C(n; q), the set of n-vertex q- edge labeled connected graphs. The domain of validity of the asymptotic formula of Erdos and R'enyi for jC(n; q)j is extended and...
The Number of Degree Restricted Rooted Maps on the Sphere (1999)
Edward A. Bender, E. Rodney Canfield
Let D be a set of positive integers. Let m(n) be the number of n edged rooted maps on the sphere all of whose vertex degrees (or, dually, face degrees) lie in D. Using Brown's technique, we...
Intersections of Randomly Embedded Sparse Graphs are Poisson (1999)
Edward A. Bender, E. Rodney Canfield
Suppose that t # 2 is an integer, and randomly label t graphs with the integers 1 ...n. We give sufficient conditions for the number of edges common to all t of the labelings to be asymptotically...
Intersections of Randomly Embedded Sparse Graphs are Poisson (1999)
Edward A. Bender, E. Rodney Canfield
Suppose that t 2 is an integer, and randomly label t graphs with the integers 1 : : : n. We give sufficient conditions for the number of edges common to all t of the labelings to be asymptotically...
The size of the largest antichain in the partition lattice (1998)
Consider the poset \Pi n of partitions of an n-element set, ordered by refinement. The sizes of the various ranks within this poset are the Stirling numbers of the second kind. Let a = 1 2 \Gamma e...
E. Rodney Canfield, Sylvie Corteel, Carla D. Savage
Let F(n) be a family of partitions of n and let F(n; d) denote the set of partitions in F(n) with Durfee square of size d. We define the Durfee polynomial of F(n) to be the polynomial PF;n = P jF(n;...
E. Rodney Canfield, Sylvie Corteel, Carla D. Savage
Let F(n) be a family of partitions of n and let F(n, d)denotethesetof partitions in F(n) with Durfee square of size d. We define the Durfee polynomial of F(n) to be the polynomial PF,n = # |F(n, d)|y...
Submap Density and Asymmetry Results for Two Parameter Map Families (1997)
Edward A. Bender, E. Rodney Canfield, Zhicheng Gao, L. Bruce Richmond
this paper, all limits are understood to be taken through those values of n
The Asymptotic Number of Labeled Graphs with n Vertices, q Edges, and No Isolated Vertices (1996)
Edward A. Bender, Brendan D. Mckay, E. Rodney Canfield, E. Rodney Canfield
Let d(n; q) be the number of labeled graphs with n vertices, q N = \Gamma n 2 \Delta edges, and no isolated vertices. Let x = q=n and k = 2q \Gamma n. We determine functions w k ¸ 1, a(x), and...
Edward A. Bender, E. Rodney Canfield
The weight of a vector in the finite vector space GF(q) n is the number of nonzero components it contains. We show that for a certain range of parameters (n; j; k; w) the number of k-dimensional...
Log-concavity and related properties of the cycle index polynomials (1996)
Edward A. Bender, E. Rodney Canfield
Log-concavity and cycle index polynomials Let An denote the n-th cycle index polynomial, in the variables Xj, for the symmetric group on n letters. We show that if the variables Xj are assigned...
Asymptotic properties of labeled connected graphs (1992)
Edward A. Bender, E. Rodney Canfield, Brendan D. Mckay
notwithstanding any copyright notation hereon. Properties of Labeled Connected Graphs We prove various properties of C(n, q), the set of n-vertex qedge labeled connected graphs. The domain of...