User:Geoffrey Critzer

== Contact: [email protected]

When I was 60 years old, I earned a masters degree in mathematics at the University of Kansas. It was one of the greatest experiences of my life.

I have about 1900 submissions in the OEIS. Using and contributing to the OEIS has been a joy in my life for the last 25 years.

I view the OEIS as being in its infancy. I often wonder what place the OEIS will hold in the mathematical universe when there are millions of sequences in the data base.

I like to understand integer sequences by considering the correspondence between tasks performed on classes of combinatorial objects and formal algebraic operations (such as sums, products, compositions, derivatives) of their generating functions. As stated by Flajolet and Sedgewick in their seminal work, Analytic Combinatorics, there is a pleasantly "surprising efficiency of generating functions in the solution of combinatorial enumeration problems."

Some decompositions of binary words:

(0 + 1)* A binary word is a sequence of 0's or 1's. $G(x)=1/(1-(x+x))$.

0*(10*)* A binary word is a string of 0's followed by a sequence of one 1 and a string of 0's. $G(x)=1/(1-x)*1/(1-x/(1-x))$.

0*(11*00*)*1* A binary word is a string of 0's followed by a sequence of nonempty strings of 1's and nonempty strings of 0's followed by a string of 1's. $G(x)=1/(1-x)*1/(1-x*1/(1-x)*x*1/(1-x))*1/(1-x).$

Exploiting the second decomposition given above we have: A078057(x)=A040000(x)/(1 - x*A040000(x)). A003688(x)=A003945(x)/(1 - x*A003945(x)). A015448(x)= A003946(x)/(1 - x*A003946(x). ... See comments by Joerg Arndt.

(1 + 00*1)*0* A binary word is a sequence of ( 1's OR at least one 0 followed by a 1) followed by a sequence of 0's. $G(x)=1/(1-(x+x*1/(1-x)*x)*1/(1-x)$. We can mark the 1's that are immediately preceded by a 0. Cf. A034867.

A binary word with an even number of 0's is empty or a 1 prepended to such a word or a 01*0 prepended to such a word. $E(x)=1+x*E(x)+x^{2}/(1-x)*E(x).$

A binary word with an odd number of 0's is a 0 or a 011* or a 1 prepended to such a word or a 01*0 prepended to such a word. $O(x)=x+x^{2}/(1-x)+x*O(x)+x^{2}/(1-x)*O(x).$

A binary word with no two consecutive 0's is empty or a single 0 or a 1 prepended to such a word or a 01 prepended to such a word. $F(x)=1+x+xF(x)+x^{2}F(x).$

A binary word with no two consecutive 0's is a sequence of 1 or 10 possibly prepended with a 0. $F(x)=(1+x)*1/(1-x-x^{2}).$

A binary word containing an equal number of 1's and 0's and such that every prefix contains at least as many 1's as 0's is empty or a 1 appended and a 0 prepended to such a word appended to such a word. $D(x)=1+x*D(x)*x*D(x).$

A binary word containing an equal number of 1's and 0's is a sequence of two types of the above words which have been prepended with a 1 and appended with a 0. $B(x)=1/(1-2*x*D(x)*x).$

Every binary word contains a maximal prefix which contains an equal number of 1's and 0's. $B(x)*G(x)=1/(1-2*x)$ where B(x) is defined above and G(x) is the o.g.f. for A063886. The average length of this maximal prefix is n/2 and its distribution is given in A237520.

C(x)=1/(1-x/(1-x)) is the o.g.f. for the number of compositions of n. C(x)*x/(1-x)*C(x) is the number of parts over all compositions of n. C(x)*x^2/*(1-x^2)*C(x) is the number of levels over all compositions of n. C(x)*(x^3 + x^4)/(1-x^2)^2*C(x) is the number of rises over all compositions of n.

A minimal cover of an n-set is a relation from a set of points, A, that are not uniquely covered into a set of blocks, B, of a partition of the points that are uniquely covered such that every element in A is related to at least 2 elements in B. Sum_{n>=0} (exp(x)-1)^n/n! * exp((2^n-n-1)x).

Generating functions are concise and precise.

Often times a generating function is the most concise and precise way to describe a combinatorial class. Consider the excellent comment by Martin J Erickson in A105476:

"a(n) is also the number of compositions of n using 1's and 2's such that each run of like numbers can be grouped arbitrarily". An example is almost essential to understand what is being enumerated.

"For example, a(4) = 15 because 4 = (1)+(1)+(1)+(1) = (1+1)+(1)+(1) = (1)+(1+1)+(1) = (1)+(1)+(1+1) = (1+1)+(1+1) = (1+1+1)+(1) = (1)+(1+1+1) = (1+1+1+1) = (2)+(1)+(1) = (1)+(2)+(1) = (1)+(1)+(2) = (2)+(1+1) = (1+1)+(2) = (2)+(2) = (2+2)".

However, by a quick inspection of the generating function: 1/( 1 - (x/(1-x) + x^2/(1-x^2)) ) we instantly realize exactly what is being counted.

Algebraic simplification of generating functions usually obscures the simplicity of the derivation via the symbolic method. A105476 is also the number of compositions of n when each even part can be of two types. 1/( 1 - (a + (b-c)/2) ) where a = $2*x^{2}/(1-x^{2}).$ b = 1/(1-x). c= 1/(1+x).

A chain in the poset on the powerset of an n-set ordered by set inclusion has a "canonical" correspondence with an ordered set partition. Cf. the Nelson, Schmidt reference given in A007047. ((exp(x)-1)^2 + 2*(exp(x)-1) + 1)*(1/(1 - y*(exp(x)-1))) is the bivariate e.g.f. for A038719.

Some systems of linear Diophantine inequalities

What is the number of solutions to the equation X + Y + Z = n in nonnegative integers such that X >= Y and X >= Z. There are 2 cases: i.) X >= Y + Z. ii.) X < Y + Z. The o.g.f. for case i is $1/(1-x)*1/(1-x)*1/(1-x^{2})$. Case ii. has o.g.f. $x^{3}*1/(1-x^{3})*1/(1-x^{2})*1/(1-x^{2})$. Adding the o.g.f.`s for each case gives A156040.

What is the number of solutions to the equation X + Y + Z = n in nonnegative integers such that X + Y >= Z. There are 3 cases: i.) X and Y are both >= Z. ii.) X or Y exclusively is >= Z. iii.) neither X nor Y is >= Z. Case i. is enumerated by the o.g.f. $1/(1-x)*1/(1-x)*1/(1-x^{3})$. Cf.A001840. Case ii. has ogf: 2 * x^2 * 1/(1-x) * 1/(1-x^3) * 1/(1-x^2) Cf. A001399. Case iii. has o.g.f.: x^4 * 1/(1-x^2) * 1/(1-x^2) * 1/(1-x^3) Cf. A008731. Adding the 3 cases gives A001318.

Alternatively, we can enumerate all solutions with 1/(1-x)*1(1-x)*1/(1-x) and subtract out the bad ones (X + Y < Z) which are counted by 1/(1-x^2)*1/(1-x^2)*x/(1-x). This is A000217 - A008805 = A001318.

Inversions over all n-permutations

What is the total number of inversions in all n-permutations? There is a very elegant combinatorial proof provided in A001809. But more satisfying is to employ the symbolic method in directly translating a combinatorial structure into a generating function. In this case the combinatorial class will be a superset of permutations comprised of permutations with a specially designated pair of elements that are out of order. Let the factor (e.g.f.) x^2/2! select a pair of elements in a permutation and then let three factors (e.g.f.'s) of 1/(1-x) linearly order the elements before, between and after the selected inversion pair. The bold face is to emphasize that generating functions perform tasks (build structures). $G(x)=x^{2}/2!*1/(1-x)^{3}.$

Increasing subsequences over all n-permutations

The number of increasing subsequences in all n-permutations is equal to the number of partial permutations on [n]. (A partial permutation is a bijection from one subset of [n] to another).

The e.g.f. 1/(1-x) linearly orders or permutes a set. The e.g.f. x^i/i! builds an i set. A set is unordered so lets think of it as being in its natural order. Using similar thinking as in the above enumeration of inversions we see that the product x^i/i!*(1/(1-x))^(i+1) is the e.g.f for the number of increasing subsequences of length i in all n-permutations. For i=0,1,...,5 we have A000142 (we must agree that there is exactly one increasing subsequence of length zero for each n-permutation), A001563, A001809, A001810, A001811, A001812. If we sum all such sequences for all i >= 0 we get 1/(1-x)*exp(x/(1-x)) as the e.g.f. for A002720 where Neil Sloane has indicated that the sequence counts the total numbr of increasing subsequences over all permutations of [n]. On page 132 of P. Flajolet and R. Sedgewick, <a href="https://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; there is an equally transparent derivation of the e.g.f. for the number of partial permutations. The two e.g.f.'s are equal and the generatingfunctiontological proof is complete.

Some constructions with generating functions

The function 2x as an e.g.f. performs the task of designating (or not) an atom in a combinatorial structure.

The function $exp(x)$ performs the trivial task of bagging labeled atoms.

Construct the class S comprised of bags of labeled objects where some of the objects have been specially designated. By "The Compositional Formula" (so called by Miklos Bona, Introduction to Enumerative Combinatorics, page 170) we have: $S(x)=exp(2x).$

A 2-colored graph is a bipartite graph in which "some" of the connected components are distinguished. B(x) = exp(2 A(x)) where B(x) is the e.g.f for A047863 and A(x) is the e.g.f. for A001832.

Lets select "some" of the nodes of a simple labeled graph on n-1 nodes and then add an edge between the selected nodes and a node labeled n. We have constructed a simple labeled graph on n nodes and we have the functional equation: G'(x) = G(2x) where G(x) is the e.g.f. for A006125.

The e.g.f. $A(x)=exp(2x)-exp(x)$ enumerates the number of ways to place n labeled objects into a bag and specially designate at least one of them.

Construct a labeled octopus by designating at least one of the nodes in a labeled directed cycle: $C(x)=log(1/(1-x))$. The designated nodes become the body of the octopus and the nodes between them become the tentacles. So $A(x)=C(2x)-C(x)=log(1/(1-2x)-log(1/(1-x))$ where A(x) is the e.g.f. for A029767.

Construct a set partition on {1,2,...,n} and then point to (distinguish) one of the elements. x * B'(x) where B'(x) = exp(exp(x)-1). Accomplish the same task by first selecting a nonempty subset S of {1,2,...,n} and then pointing to one of the elements of S, and then partition the complement of S. x*exp(x)*B(x). So we have: B(x)*exp(x) = B'(x).

Point to (distinguish) an element in a permutation of {1,2,...,n}. x * P'(x) where P(x) = 1/(1 - x). Now "point" to an element in a permutation of {1,2,...,n} by placing a divider bar to the right of the designated element. We have constructed a permutation of a nonempty subset of {1,2,...,n} and a permutation of its complement. x*P(x)*P(x). So we have P'(x) = P(x)^2.

Construct the set of all permutations of A={0,1,2,...,n-1} by performing the following procedure in all possible ways. Label some boxes with a subset S of A containing the element 0, place the elements of A\S into the boxes, make cycles from the elements in each box. x*(x + 1)*(x + 2) *** (x + n-1) = Sum_{k=1,..n} Stirling2(n,k)x^n.

Construct the set of all set partions of {1,2,...,n} into exactly k blocks: Place n + k unlabeled objects into boxes labeled 1 through k with at least one object in each box. Build all functions f_k:[m]->[k] so that f[1]=k where m is the number of objects in each box. x/(1-x)*x/(1-2x)***x/(1-kx) = Sum_{n>=0} Stirling2(n,k)x^n

A preorder is a partial order of some blocks of elements. A( exp(x) - 1) where A(x) is the e.g.f. for A001035. A transitive relation is a partial order of some blocks of elements or some irreflexive points. A(x + exp(x) - 1).

???????????????????? Is there a combinatorial argument to explain the identity: D'(x) = D(x)*x/(1-x) where D(x) is the e.g.f. for A000166 (derangements). Why is the e.g.f. for the number of odd permutations and the number of odd derangements x^2/2!/(1-x) and x^2/2! exp(-x)/(1-x) respectively. Cf. A000166 ????????????????????

Consider the mapping that takes the set of all n-letter words on alphabet {1,2,...,m} into the set of all n-permutations by the following procedure: Scan the word from left to right and note the position of the letters as you come to them in order of least to greatest. For example, the word (2,3,1,2) is mapped to the permutation (3,1,4,2). See A038675. The number of n-words that are mapped to the identity permutation is equal to the number of ways to place at most n-1 indistinguishable balls into n distinguishable boxes. See the first comment in A001700. In terms of ordinary generating functions this is the product of 3 factors (o.g.f's): x * 1/(1-x) * 1/(1-x)^n. By the same reasoning we see that the number of n-words that are mapped to a permutation having k descents is the number of ways to place at most n-1-k balls into n bins. Such a word is a nondecreasing sequence (albeit in a permuted order) with at least k strict increases. Translating into factors of o.g.f.s we have: x^(k+1) * 1/(1-x) * 1/(1-x)^n. So the o.g.f. for the n th powers is x/(1-x)^(n+1) * Sum_{k=0..n-1} E(n,k)x^k where E(n,k) is the number of permutations with k descents. See formula section in A000583.

Inversions over all involutions

The E.G.F. for the total number of inversions over all involutions of length N is:

(1*z^2/2! + 2*z^3/3! + 6*z^4/4! ) * (exp( z + z^2/2) where I have left the first factor in its unsimplified form to make the explanation more transparent.

From Computational Discrete Mathematics, Skiena and Pemmaraju, Cambridge Univ. Press, 2003, page 69 we have the definition: " A pair of elements ( p(i), p(j) ) in a permutation p represents an inversion if i > j and p(i) < p(j)."

Accordingly, I will associate to each inversion an unordered pair whose two members are elements of an involution of length N that are out of order. There are three (mutualy exclusive and exhaustive) ways this can happen: i.) both members are in the same 2-cycle. ii.) one member is a fixed point and the oher is in a 2-cycle. iii.) both members are in distict 2cycles. For case i. it is clear that there is only 1 such unordered pair. For case ii. there are 2 such unordered pairs. I convinced myself of this by writing out the unordered pairs found in the involutions (1)(23),(2)(13) and (3)(12) and counting the number in which one member is a fixed point and the other is in a 2-cycle. For case iii. there are 6 such unordered pairs. Count the appropriate unordered pairs in the involutions (12)(34), (13)(24), and (14)(23).

By the sum and product rule of E.G.F's we have the desired result.

Multivariate generating function for endofunctions

Here is an exponential multivariate generating function that counts the class of all functions f:{1,2,...,n}->{1,2,...,n}.

A(x,v,w,y,z) = (1- z x exp( w T(x,v)))^-y  where T(x,v) = Sum_{n>=1} n^(n-1)(v x)^n/n!

The variable x marks size (the number of elements being mapped = n), y marks the number of cycles, z marks the number of recurrent elements, w marks the number of nonrecurrent elements mapped (directly) to a recurrent element, and v marks the number of nonrecurrent elements.

Let f be a randomly selected (uniform distribution) function from {1,2,...} into {1,2,...}. The probability that f has exactly k cycles of size n is 1/(exp(1/n)*n^k*k!). (This is the same as that of a random permutation of {1,2,...}). Examining the distribution as n gets large (Poisson(1/n)), we expect that there are about H(n) cycles of size n or less (expecially if we disregard the small cycles) where H(n) is the harmonic number.

Multivariate generating function for simple labeled graphs

Here is a generating function in 4 variables that counts simple labeled graphs.

A(x,w,y,z) = exp(z*x)^y * exp(x)^(-y) * (Sum_{n>=0} (1 + w) ^ binomial(n,2) x^n/n! )^y 

The coefficient (after multiplying by n!) of y^k z^j w^m x^n is the number of simple labeled graphs on n nodes that have k connected components, j isolated nodes, and m edges.

Integer partitions

Here are 3 generating functions for the number of integer partitions of n into distinct parts.

G.f.: Product_{m >= 1} (1 + x^m) = 1/Product_{m >= 0} (1-x^(2m+1)) = Sum_{k>=0} Product_{i=1..k} x^i/(1-x^i).

The number of partitions into distinct parts = the number of partitions into odd parts. The number of partitions of n into exactly k distinct parts = the number of partitions with at least one 1, one 2, ... one k.

Some probability problems

Here are two probability questions that can be answered handily employing generating functions and a computer algebra system like Mathematica or Maple.

Three ordinary dice are rolled and the sum of their faces is found to be k. Then k fair coins are tossed and the number of heads is then counted. What is the probability that 10 heads occur? 195973/9437184. The coefficient of x^10 in A(B(x))^3 where A(x) = (x-x^7)/(6(1-x)) and B(x) = (1 + x)/2

In a dice game you win if the sum of the faces of some dice is 25. You are allowed to roll every positive integer number of dice one time. Of course to roll a 25 you need at least 5 dice and rolling more than 25 dice is not going to help you. Acordingly, you begin by rolling 5 dice once, then you roll six dice once, ... finaly (if you haven't won already) you make a desperate attempt to roll 25 aces. What is the probaility that you win? 8119686580790083201/28430288029929701376. This is the coefficient of x^25 in 1/(1-A(x)) where A(x) = (x - x^7)/(6(1 - x)).

Some transformations

If A(x) is the e.g.f. for sequence {a(n)}n>=0 then the e.g.f. for sequence {n^k*a(n)}n>=0 is:

B(x) = Sum_{j=1,..,k} Stirling2(k,j)*x^j*A^j(x) where A^j(x) is the jth derivative of A(x). This is seen by extending the pointing argument given in Analytic Combinatorics to multiple (but not necessarily distinct) elements (atoms) of a combinatorical object. Here we are considering the order in which the atoms are "pointed to" (designated) as important. In other words B(x) is the e.g.f for the number of ways to select a combinatorial object counted by A(x) and then select a k-tuple of its labeled atoms.

If we let A(x) be the e.g.f. for free lableled trees and k = 2, then we have the generating function interpretation of the bijection between "doubly rooted" free labeled trees and functions from {1,2,...,n}->{1,2,...,n}. Cf. "Introduction to Enumerative Combinatorics", Miklos Bona, Page 267.

If A(x) is the e.g.f. for sequence {a(n)}n>=0 then the e.g.f. for sequence {C(n+k-1,k) * a(n)}n>=0 is:

B(x) = Sum_{j=0,..k-1} C(k-1,j)* x^(j+1)/(j+1)! * A^(j+1)(x). Again we are "pointing" at (not necessarily distinct) atoms of a combinatorial object. This time we do not consider the order in which the pointing is done as important. In other words, B(x) is the e.g.f. for the number of ways to select a combinatorial object counted by A(x) and then select a size k multiset of its lableled atoms.

If we let A(x) be the e.g.f. for free labeled trees and k=2, following the map that is laid out in the above bijection except disregarding the order of the roots we see a bijection between "unordered doubly rooted" trees and functions from {1,2,...,n}->{1,2,...,n} such that of all recurrent elements the least is always mapped to the greatest. Cf. A052182.

If A(x) is the e.g.f. for the sequence {a(n)}n>=0 then the e.g.f. for the sequence { C(n,k) * a(n)}n>=0 is:

B(x) = x^k/k! * A^k(x). In other words B(x) is the e.g.f. for the number of ways to select a combinatorial object counted by A(x) and then select a size k subset of its atoms.

If A(x) is the e.g.f. for the sequence {a(n)}n>=0 then the e.g.f. for the sequence { k! * a(n)}n>=0 is:

B(x) = x^k * A^k(x). In other words B(x) is the e.g.f. for the number of ways to select a combinatorial object counted by A(x) and then select a k-permutation of its atoms.

If A(x) is the e.g.f. for the sequence {a(n)}n>=0 then the e.g.f. for the sequence { k^n * a(n)}n>=0 is:

B(x) = A(k*x). For example, Let k=2 and A(x) be the e.g.f. for cyclic permutations: Log(1/(1-x)) then we have A032179.

Cantor's Theorem by analogy

There does not exist a surjective function from any set into its power set.

A photography company (in hopes of selling more photos to the students at a very large school) decides to take a photograph of EVERY possible group of students. They take a photograph of each student individually, of each student paired with every other student, of every possible group of three students and so on. They even take one picture of nobody and one picture with everyone in it. It is not surprising at all to realize that if the number of students at the school is finite then there are more photographs than there are students.

What if there are an infinite number of students? We might think it is possible that the number of photographs is the same as the number of students since both would be infinite. We try to demonstrate this by passing out exactly one photograph to each student in hopes that we are able to distribute every photograph. But this is impossible because no matter how we distribute the photographs there will always be at least one photo that did not get passed out.

Here's why: After distributing the photos (in any possible way), instruct each student to look at the photograph that they received and observe whether or not they are pictured in the photo. Then tell the students " if you are pictured in the photo that you received then line up on the east side of the school. If you are not in the photograph that was given to you then line up on the west side of the school." Now, the photography company certainly took a picture of the subgroup of students on the west side of the school. But no student could possibly have that photo. None of the students on the east side of the school could have the photo because they are pictured in the photo they are holding but they are not in the west side subgroup. No student on the west side of the school could be holding that photo because they are in the west side subgroup but the photo they are holding does not feature them.

Boxed product

Boxed Product of two e.g.f.'s.

If we take the derivative of an e.g.f. A(x), the new e.g.f. A'(x) builds an a structure on {1,2,...,n} but it is given the advantage of having an extra (secret) atom to build with. We can imagine the extra secret atom is the element 1.

Let B(x),C(x) be the e.g.f.'s for the number of ways to build a b-structure, c-structure on a set of labeled objects. Let A(x) be the e.g.f for the number of ways to partition {1,2,...,n} into two disjoint subsets S,T such that S union T = {1,2,...,n} and 1 is an element of S. Then we have: A'(x) = B'(x)*C(x). For example, let B(x)= x*exp(x) and C(x) = exp(x). Integral B'(x)*C(x)*dx is the e.g.f. for the total number of elements over all subsets of {1,2,...,n} that contain the element 1. Cf A001792.

Let B(x)=C(x)=exp(x)-1. Integral(Integral B'(x)*C'(x)*dx)*dx) is the number of set partitions on {1,2,...,n} into exactly two blocks so that the elements 1 and n are not in the same block. Likewise, Integral(Integral(B'(x)*C'(x)*exp(exp(x)-1)*dx)*dx) is the number of set partitions of {1,2,...,n} into any number of blocks so that the element 1 and n are not in the same block. Cf A005493 comment by Andrey Goder.

The fractional part of n*sqrt(2) raised to the nth power diverges

For a real number x let {x} denote the fractional part of x.

I want to show that the sequence a(n) = { n * sqrt(2) }^n diverges. I will examine two subsequences of a(n) and show that one, b(n) converges to 0 while the other, c(n) converges to exp(-1/(2*sqrt(2)).

Index with k for k = {1,2,...} the sequence of rational convergents in the continued fraction representation of sqrt(2). Let p(k) be the numerator in the kth convergent and q(k) be the denominator in the kth convergent.

p(k) = ( (1 - sqrt(2))^k + (1 + sqrt(2))^k )/2 q(k) = ( (1 + sqrt(2)) - (1 - sqrt(2)) )/(2*sqrt(2)) These formulas are given in Sloanes OEIS A001333 and A000129.

Define the sequence b(n) = b(2k-1) = {q(2k-1)*sqrt(2)}^q(2k-1). In other words b(n) is composed of the terms in a(n) where n is a denominator in the 1st, 3rd, 5th,... odd positions... of the sequence of convergents. These are precisely the convergents that are < sqrt(2). The crucial observation is

{q(2k-1)*sqrt(2)} = q(2k-1)*sqrt(2) -p(2k-1).

For example, the first 10 convergents are:

1/1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378

Considering the ninth convergent 1393/985. The fractional part of 985*sqrt(2) is 985*sqrt(2) - 1393.

Using the formulas for p(k),q(k) and the crucial observation we see that

b(n) = b(2k-1) = [ (1 - sqrt(2))^(2k) * (1 + sqrt(2)) ]^q(2k-1) which converges to 0.

Define the sequence c(n) = c(2k) = {q(2k)*sqrt(2)}^q(2k). In other words c(n) is composed of the terms in a(n) where n in a denominator in the 2nd, 4th, 6th,...even positions... of the sequence of convergents. These are precisely the convergents that are > sqrt(2). The crucial observation is

{q(2k)*sqrt(2)} = q(2k)*sqrt(2) - p(2k) + 1.

For example, considering the tenth convergent, 3363/2378.

The fractional part of 2378*sqrt(2) is 2378*sqrt(2) - 3363 +1.

Using the formulas for p(k),q(k) and the crucial observation we see that

c(n) = c(2k) = [ 1 - (1 - sqrt(2))^(2k) ] ^ ( (1 + sqrt(2))^(2k) - (1 - sqrt(2))^(2k) )/(2*sqrt(2))

c(n) converges to exp(-1/(2*sqrt(2))).

If you gave me a rational number p/q that was equal to the sqrt(2), I would make q strides ( my stride length is exactly sqrt(2) units) on a sidewalk whose cracks are exactly 1 unit apart. I would be exactly on the pth crack. If you give me a rational number p/q that is slightly greater than sqrt(2) I will take q strides but I will not quite make it to the pth crack.

Lets say we have a countably infinite set A of real numbers in the interval (0,1) and that 1 is a limit point of A. We make a sequence from the elements in A and raise the nth term to the nth power. We are allowed to arrange the elements of A in any order we want and we get to raise each term to successively higher powers. We are not allowed to make copies of the elements in A, i.e. we must place every element of A into exactly one position of the sequence.

An example is the sequence a(n) = {n*sqrt(2)}^n where {x} denotes the fractional part of x. Another example is the sequence a(n) = (1 - 1/n)^n.

Is it possible to construct such a sequence that would converge to 0?

One possibility might be to arrange the set of proper fractions into their "canonical order": (1/2)^1, (1/3)^2, (2/3)^3, (1/4)^4, (3/4)^5, (1/5)^6, (2/5)^7, (3/5)^8, (4/5)^9, (1/6)^10, ... It looks like the terms are getting smaller but can we demonstrate convergence to 0?

Perhaps an easier question to resolve is: What if we stipulate that 1 is the ONLY limit point of A? Yes! If 1 is the only limit point we consider any sequence of the form a(n) = (1 - 1/n^p)^n where p is in (0,1).

The coefficient of x^2 in Sin(x)Cos(x)/x = Product_{k>=1}(1-x/(k*Pi/2))(1 + x/(k*Pi/2)) gives us Sum_{k>=0} 1/(2k+1)^2 = Pi^2/8.

Cayley's Theorem

The number of distinct degree sequences over all trees (free, unlabeled) having n+2 nodes is equal to the number of functions f:{1,2,...,n}->{1,2,...,n+2}.

A degree sequence of a tree having n+2 nodes is a sequence of positive integers d(1),d(2),...,d(n+2) such that d(1)>= d(2) >= ...>= d(n+2) and d(1) + d(2) + ... + d(n+2) = 2*n + 2.

Let me call an "image" sequence of a function f:{1,2,...,n}->{1,2,...,n+2} a sequence of positive integers j(1),j(2),...,j(k) such that j(1)>= j(2) >= ... >= j(k) and j(1) + j(2) + ... + j(k) = n and each j(i) is the size (cardinality) of the co-image sets under the function f.

(What I mean here by co-image sets is the blocks of the set partition of the domain that the function induces.)

We see the image sequences are the partitions of the integer n.

If we add 1 to each j(i) in the image sequence and then append as many 1's as is necessary to make the image sequence sum to 2*n + 2 then we have the degree sequence of a tree with n + 2 nodes.

Cayley's theorem says that the number of functions f:{1,2,...,n}->f:{1,2,...,n+2} with image sequence j(1),j(2),...,j(n) is equal to the number of LABELED trees with degree sequence d(1),d(2),...,d(n+2) under the above correspondence.

For example: The "star" graph on 6 nodes has degree sequence 5,1,1,1,1,1. There are six labelings of the "star" graph and there are six functions f:{1,2,3,4}->{1,2,3,4,5,6} that have image sequence 4. ( Every element is mapped to a single element in the co-domain.)

Another example (in the other direction): There are 360 functions f:{1,2,3,4}->{1,2,3,4,5,6} with image sequence 1,1,1,1 (the injective functions). There are 360 labelings for the "path" graph with 6 nodes which has degree sequence 2,2,2,2,1,1.

Dirchlet Generating Functions

We can define an equivalence relation ~ on the set of divisors of integer n by d~d' iff the greatest perfect square that divides d is equal to the greatest perfect square that divides d'. Sum_{n>=1} 2^(little omega(n))/n^s * zeta(2s) = zeta(s)^2. C.f. A253196.

More generally we can classify the divisors of n by the greatest kth power that divides them. Sum_{n>=1} theta_k(n)/n^s * zeta(k*s) = zeta(s)^2 where theta_k(n) is the number of kth power free divisors of n.

Every integer can be uniquely factored into the product of a perfect square and a squarefree integer. Sum_{n>=1} |mu(n)|/n^s * zeta(2s) = zeta(s). Generally, every integer can be uniquely factored into the product of a perfect k power and a k-power free integer. Sum_{n>=1} f(n)/n^s * zeta(k*s) = zeta(s), where f(n) is the characteristic function of the k-power free integers.

The number of odd size subsets of an n-element set is equal to the number of even size subsets. The number of squarefree divisors of n with an odd number of primes is equal to the number of squarefree divisors of n with an even number of primes. Sum_{n>=1} mu(n)/n^s * zeta(s) = 1.

If we think of an integer as a multiset M of its prime factors then the number of submultisets of M is the number of divisors (sigma(n)) of n. There is one multisubset that has the same cardinality as M, i.e. M itself. We could arrive at this obvious result in a very tedious manner. Start with all the submultisubsets of M and use the principle of inclusion/exclusion to throw out the "bad" sets. 1 = Sum_{d|n} mu(d)*sigma(n/d).

In terms of multisets the ideas expressed in paragraph two above can be stated as: There is exactly one way to partition a multiset into two subsets A and B so that the multiplicity of every element of A is divisible by k and the multiplicity of every element of B is strictly less than k.

There is only one way to partition a multiset whose elements all have even multiplicity into two submultisubsets A,B such that every element in A has multiplicity two and every element in B has multiplicity divisible by four. Sum_{n>=1} A227291(n)/n^s*zeta(4*s)=zeta(2*s). Generalizing, let d_k(n)=|mu(n^(1/k)| if n is a kth power, otherwise 0. Sum_{n>=1}d_k(n)/n^s*zeta(2*k*s)=zeta(k*s).

The number of even sized multisubsets d(e) of {a^m(1),b^m(2),...,n^m(n)} is equal to the number of odd sized multisubsets d(o) if and only if there is at least one i such that m(i) is odd. Otherwise d(e) = d(o) + 1. Sum_{n>=1}lamda(n)/n^s * zeta(s) = zeta(2*s).

We can define an equivalence relation ~ on {1,2,...,n} by a~b iff gcd(a,n)=gcd(b,n). Sum_{n>=1} phi(n)/n^s * zeta(s) = zeta(s-1).

Let f(n) be a characteristic function, i.e, f(n)=1 if n has some desired property, otherwise f(n)=0. Let F(s) be the Dirichlet g.f. for the sequence f(n). Then the Dirichlet g.f. for the number of integers in row n of A050873 that have the desired property is zeta(s-1)/zeta(s) * F(s). The translation directly above is a particular instance where the desired property is only that n be a positive integer.

More generally, zeta(s-1)/zeta(s)*F(s) is the Dirichlet g.f. for Sum_{j=1..n} f(gcd(n,j)). For example if f(n)=n , then F(s)=zeta(s - 1) and we see that zeta(s-1)/zeta(s)*F(s) is the sum of the entries in row n of A050873 which is given by A018804.

The sum of the k power free divisors of n is the Dirichlet convolution the all 1's sequence and the sequence {a_n}n>=1 defined by a(n) = 0 if n is divisible by a kth power greater than 1 and a(n) = 1 otherwise. The Dirichlet g.f. for the latter is zeta(s - 1)/zeta(k*s - k). Proof: Write down the Dirichlet series for the first few terms of {a_n} and then multiply them by the first few terms of zeta(k*s - k).

The sum of the divisors d such that n/d is k power free is the Dirichlet convolution of a(n) = n and the characteristic function of the k power free numbers. So the Dirichlet g.f. is: zeta(s - 1)*zeta(s)/zeta(k*s)