co.combinatorics – What is the inverse Laplace transform of $frac{(1/s)_{n}}{s} $?

Introduction

So far, I have found (p. 5) the following generating functions of the unsigned Stirling numbers of the first kind:

begin{equation} tag{1} label{1} sum_{l=1}^{n} |S_{1}(n,l)|z^{l} = (z)_{n} = prod_{k=0}^{n-1} (z+k) =: g(z) , end{equation} and begin{equation} tag{2} label{2} sum_{n=l}^{infty} frac{|S_{1}(n,l)|}{n!}z^{n} = (-1)^{l} frac{ln^{l}(1-z)}{l!} .end{equation}

Instead of summing the latter expression over $n$, I’m curious whether there is a simpler or different expression of the latter generating sum when summed over the other indices:

begin{equation} tag{3} label{3} f(z) := sum_{k=1}^{n} frac{|S_{1}(n,k)|}{k!}z^{k} . end{equation} (One could also take the sum from $k=1$ to $k=infty$, as $|S_{1}(n,k)| = 0$ when $k>n$.)

Work so far

Approach 1

We see that $(3)$ is the egf version of the ogf in $(1)$. So one of the ways I’ve tried to find $f(cdot)$ is by converting the first equation to the third one by applying the inverse Laplace transform to $g(1/s)/s$.

From $(1)$, we see that $g(1/s)/s = frac{(1/s)_{n}}{s}$. The tricky part of find the inverse Laplace transform lies in the numerator. Therefore, I tried to express it in terms of other functions of which the inverse Laplace transform might be known.

For instance, note that the Chu-Vandermonde identity states: begin{equation} tag{4} label{4} _2F_1left(-n,b;c;1right) = frac{(c-b)_{n}}{(c)_{n}} . end{equation}

Now, set $c=1$ and $b = 1 – 1/s$. Then:

begin{equation} tag{5} label{5} _2F_1left(-n,1-1/s;1;1right) = frac{(1/s)_{n}}{n!} =: h(s) . end{equation}

If the inverse Laplace transform of $h(cdot)$ would be known, then I would only have to multiply by $n!$ and convolve it with $ { mathcal{L}^{-1} (1/s) } (t) = u(t) $, where $u(t)$ is the unit step function.

However, I did not find an expression of the inverse Laplace transform of the hypergeometric function in $(5)$ in the “Tables of Laplace Transforms” by Oberhettinger and Badii (1973).

Approach 2

Another approach I tried is to note that begin{equation} tag{6} label{6} g(1/s) = (1/s)_{n} = frac{Gamma(1/s + n)}{Gamma(1/s)} . end{equation}

Unfortunately, the inverse laplace transform of begin{equation} tag{7} label{7} q(s) := frac{Gamma(s+a)}{Gamma(s+b)} end{equation} is only given by Oberhettinger and Badii (p. 308) in the case when $Re(b-a) >0$, which is not the case here.

Approach 3

Finally, I tried rewriting $g(1/s)/s$ as follows:

begin{align} g(1/s)/s &= frac{1}{s^{2}} cdot frac{1+s}{s} cdot frac{1+2s}{s} dots frac{1+ns}{s} \
&= frac{ prod_{k=1}^{n} (1+ks) }{s^{n+2}} \
&= frac{n! prod_{k=1}^{n}Big{(}s+frac{1}{k} Big{)} }{s^{n+2}}. end{align}

Observe that ${ mathcal{L}^{-1} s^{-(n+2)} }(t) = ( (n+1)! )^{-1} t^{n+1} $, so we are left with finding the inverse Laplace transform of the numerator (and convolve afterwards). However, I have not been able to do so thusfar.

Questions

  1. Is the inverse Laplace transform of $frac{(1/s)_{n}}{s}$ known, or can it be calculated somehow?
  2. Are there already any other expressions known for $f(cdot)$ that can be found by other means than the ones I laid out so far?

N.B. this is a more elaborate version of a question I asked earlier on MSE.

co.combinatorics – What are the coloops of a hypergraphic matroid?

For a hypergraph $H=(V,E)$ call $Fsubseteq E$ a hyperforest in $H$ iff there is a forest graph $G$ and a bijection $smallphi:E(G)to F$ satisfying $smallforall ein E(G)(esubseteq phi(e))$ or equivalently $smallforall Isubseteq F(|I|+1leq |cup_{Sin I}S|)$, further we call the matroid $M(H)=(E,mathcal{I})$ such that $mathcal{I}={Isubseteq E:Itext{ is a hyperforest in }H}$ the hypergraphic matroid of $H$ so in particular if $H$ is an undirected graph then this coincides with the standard definition described here while analogously if $mathcal{E}in E$ then $M(Hsetminusmathcal{E})=M(H)setminusmathcal{E}$.

Now with all of that said, my question is given any hypergraph $H$ what are the coloops of $M(H)$?

I suspect they relate to the line graph $smallmathcal{L}(H)=(E(H),{{X,Y}subseteq E(H):Xneq Ytext{ and }Xcap Yneqemptyset})$.

co.combinatorics – Fastest algorithm to construct a proper edge $(Delta(G)+1)$-coloring of a simple graph

A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing’s theorem states that every simple graph $G$ has a proper edge coloring using at most maximum degree plus one colors. In (1), the authors showed that there is an $O(mn)$-time algorithm to construct a proper edge $(Delta(G)+1)$-coloring of a simple graph whth $m$ edges and $n$ vertices. I wonder whether there is a faster algorithm to construct such an edge coloring.

(1) J. Misra, and D. Gries. A constructive proof of Vizing’s theorem.Inform. Process. Lett.41(3)131–133 (1992)

co.combinatorics – A ratio of two probabilities

Ley $t:=eta$. Then
$$f(t)=frac{P(Gge K)}{P(B ge K)},$$
where $G$ is a random variable with the binomial distribution with parameters $N,q_Gt$ and $B$ is a random variable with the binomial distribution with parameters $N,q_Bt$; here we must assume that $q_B>0$ and $tin(0,1/g_G)$, so that $q_Gt$ and $q_Bt$ are in the interval $(0,1)$.

The random variables $G$ and $B$ have a monotone likelihood ratio (MLR): for each $xin{0,dots,N}$,
$$frac{P(G=x)}{P(B=x)}=CBig(frac{1-q_Gt}{1-q_Bt}Big)^{N-x},$$
which is decreasing in $tin(0,1/g_G)$; here, $C$ is a positive real number which does not depend on $t$.

It is well known that the MLR implies the MTR, the monotone tail ratio. Thus, the desired result follows.

co.combinatorics – Problem concerning cutting of 2n*2n square into 2 equal area connected figures using various cuts without self crossings

We have a square 2n*2n, where n belongs to N. The main problem is to find how many different equal area connected figures could be produced by cuttings without self-crossings. The orientability of the figures is not in the question.
For n=1 it is evidently 1, for n=2 it is 19 (I have written a computer program of brute force cutting), for n=3 the number is more than 6643 (this number I have got from another program based on random cutting). It’s very interesting to find an exact mathematical formula for this number. Another question is the length of the cut. For n=2 all cuts from 4 to 10 except 5 is allowed, for n=3 — all cuts from 6 to 26 except 7 are also allowed. For n>=4 it is possible to use closed cuts, that form a boundary between inner and outer areas of the square. I want to know about maximal lengths of the cuts and banned lengths of the cuts.
Another problem is based on the idea of covering the figures by rectangles (with intersections and without intersections), question is about the max number of the rectangles.

co.combinatorics – Packing equal-size disks in a unit disk

Inspired by the delicious buns and Siu Mai in bamboo steamers I saw tonight in a food show about Cantonese Dim Sum, here is a natural question. It probably has been well studied in the literature, but I cannot find related reference.

Given a real number $r le 1$, let $f(r)$ be the maximum number of radius-$r$ disks that can be packed into a unit disk. For example, $f(1)=1$ for $r in (1/2, 1)$, $f(r)=2$ for $r in (2sqrt{3}-3, 1/2)$, etc.

Question: Is it true that ${f(r): r in (0, 1)}=mathbb{N}$?

co.combinatorics – Hurwitz numbers and $t$-cores

For integers $k geq 0$ and $d geq 1$ let $H(k,d)$
be the Hurwitz number which, for the purposes
of this posting, will be defined by:

begin{equation}
H(k,d)
, := d! , sum_{lambda , vdash d}
, nu_{scriptscriptstyle T}^k(lambda)
text{where} nu_{scriptscriptstyle T}(lambda) := binom{d}{2} cdot
{{chi^lambda_{scriptscriptstyle T}} over {dim(lambda)} }
end{equation}

and where $chi^lambda$ is the
character value of the irreducible representation $V_lambda$ of the symmetric group $S_d$ corresponding to the partition $lambda vdash d$ evaluated at any representative transposition (taken from the conjugacy class $T$ of all transpositions) and where $dim(lambda)$ is the dimension of $V_lambda$. The Hurwitz number $H(k,d)$ can be interpreted, using the Verlinde formula, as counting the
the number of homomorphisms (up to conjugation)

begin{equation}
rho : S_d longrightarrow
pi_1 Big( Bbb{T}^2_k , , mathrm{base , point}Big)
end{equation}

where $Bbb{T}^2_k$ is the 2-torus with $k$ punctures.
We can assemble these Hurwitz numbers into the following
bivariate generating function

begin{equation}
begin{array}{ll}
H(x;q)
&displaystyle =
1 + sum_{d geq 1} , sum_{k geq 0} , H(k,d) , {x^k over {k!}} , q^d \
&displaystyle = 1 + sum_{lambda ne emptyset} , q^{|lambda|} , exp big{ x , nu_{scriptscriptstyle T}(lambda) big}
end{array}
end{equation}

whose logarithm has a “genus” expansion

begin{equation}
log H(x;tau) = F_1(tau) + sum_{g geq 2} , F_g(tau) ,
{x^{2g-2} over {(2g-2)!}}
end{equation}

where we set $q = e^{2pi i tau}$ and each $tau$-series $F_g(tau)$ is known to be a quasi-modular form.

Now let $t geq 2$ be an integer and let us consider the following
$t$-core analogues:

begin{equation}
begin{array}{l}
displaystyle H_t(x;q)
, := 1 + sum_{stackrel{scriptstyle text{$t$-cores}}{lambda ,ne , emptyset}} , q^{|lambda|} , exp
big{ x , nu_{scriptscriptstyle T}(lambda) big} \
displaystyle F_{g; , t}(tau) , := text{
the coefficient of} {x^{2g-2} over {(2g-2)!}} text{in}
log H_t(x;tau)
end{array}
end{equation}

Question 1: Does the generating function $H_t(x;q)$ have
a nice closed expression, e.g. some sort of product formula?

Question 2: Does the $tau$-series $F_{g; , t}(tau)$ have any
kind of modular property?

thanks, ines.

co.combinatorics – Mice, cheese and cycles: configuration change with minimum effort

****Two mice and three cheeses (represented by isosceles triangles) are connected by cotton wires (edges) in such a way that each mouse has a unique (one and only one) cycle, called ‘mouse cycle’, which includes that mouse only, and a set of cheeses.

Such Mice cycles have the following properties:

  1. Uniqueness: for each mouse, there is exactly one ‘mouse cycle’ made by that mouse only, and a set cheeses.

  2. The cheeses within each ‘mouse cycle’ are defined and cannot be changed.

  3. The relative position of mouse and cheeses within each ‘mouse cycle’ does not matter (the order of mice/cheeses may be changed).

  4. The relative orientation of mouse and cheeses within ‘mice cycles’ must be preserved. Mice/cheeses orientation is given by the isosceles triangle representation: the base of the triangle represents mouse’s tail/cheese’s base, whereas the opposite vertex represents mice’s head/cheese’s tip (see top of attached picture).

Using the following notation:
Mice b: light blue mouse B: dark blue mouse. Cheeses Y: yellow cheese, R: red cheese, O: orange cheese Angle bracket: mouse head/cheese tip.

With this notation, mouse cycles can be represented, for example, as:

  • Light blue mouse loop: b>, Y>
  • Dark blue mouse loop: B>, <O, Y>

Which indeed defines cheese content and relative orientation of mice/cheeses for the two mouse cycles (the order of cheeses/mice within each cycle does not matter as already stated).

See one possible visual representation of the above definition in Figure 1 in the attached picture.

Note that:

  • A cheese may be shared between mice, in which case the ‘mice cycles’ intersect.

  • Cheeses may not be part of any of ‘mice cycles’.

——In the visual representation, mice/cheeses connections can be re-arranged in any way as long as properties 1-4 above are preserved.

This means that the following transformations are valid ones:
a) The order of cheeses/mice may be changed. See example in Figure 2a.

b) The two cycles may be drawn such that they share edges. See example in Figure 2b.

c) One end of an isolated cheese (if present) may be connected to mice cycles’s edges. See example in Figure 2c.

—— Problem statement: Given an initial configuration ‘A’ for the two mice cycles, and a final configuration ‘B’ for the two mice cycles, what is the minimum possible number of ‘cuts’ and ‘links’ required to turn the initial configuration ‘A’ into the final one ‘B’, considering all possible equivalent arrangements of mice and cheeses connections obtained using the transformation properties a, b, c above?

See a specific example in Figure 3.

Is it possible to make general conclusions, i.e. conclusions independent from particular mice cycles configurations?

This problem, invented from scratch, has eluded me for a while, I have thought of it long but I’m still not sure how to approach ithow to start.

Any ideas? Has this problem been solved before? Is this problem somehow tractable?

The system won’t let me publish the pictures until I collect 10pts. Will post them ASAP.

co.combinatorics – Can a spherical simplicial complex have more than one “central” inversion?

Let $Delta$ be a (finite) simplicial complex. Call a simplicial map $phi:DeltatoDelta$ an inversion if

  1. $phi$ is an involution, that is $phicircphi=mathrm{id}$, and
  2. $phi$ is not fixing any face of $Delta $ set-wise, except for the empty face and (potentially) $Delta$ itself.

For example, if $Delta$ is the boundary complex of a centrally symmetric polytope then such an inversion is induced by the action of the central inversion $-I$.

I have the following questions:

Qustions:

  1. If $Delta$ has more than one inversion, do they necessarily commute?
  2. If $Delta$ is spherical, can there be more than one inversion?
  3. Are there more general conditions on $Delta$ so that $Delta$ has only a single inversion?

co.combinatorics – Path sequences and isomophy of graphs

Let $G=(V,E)$ be a finite, simple, undirected graph. For each $vin V$ we define the path sequence $text{ps}^G_v: omegato omega$ where $text{ps}_v(n)$ is the number of vertices that can be reached from $v$ via a path of length at most $n$. (So $text{ps}^G_v(0) = 1$ for all $vin V$.) Of course, these path sequences are eventually constant.

What is an example of pairwise non-isomorphic graphs $G_i = (V_i, E_i)$ for $i in {1,2}$ such that there is a bijection $varphi:V_i to V_2$ and $$text{ps}^{G_1}_v = text{ps}^{G_2}_{varphi(v)}$$ for all $vin V$?