Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTwo deformed Pascals triangles and its new properties
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, firstly, by a determinant of deformed Pascals triangle, namely the normalized Hessenberg matrix determinant, to count Dyck paths, we give another combinatorial proof of the theorems which are of Catalan numbers determinant representations and the recurrence formula. Secondly, a determinant of normalized Toeplitz-Hessenberg matrix, whose entries are binomials, arising in power series, we derive new four properties of Pascals triangle.
rate research
Read More
Let $r(n,k)$ (resp. $s(n,k)$) be the number of Schroder paths (resp. little Schroder paths) of length $2n$ with $k$ hills, and set $r(0,0)=s(0,0)=1$. We bijectively establish the following recurrence relations: begin{align*} r(n,0)&=sumlimits_{j=0}^{n-1}2^{j}r(n-1,j), r(n,k)&=r(n-1,k-1)+sumlimits_{j=k}^{n-1}2^{j-k}r(n-1,j),quad 1le kle n, s(n,0) &=sumlimits_{j=1}^{n-1}2cdot3^{j-1}s(n-1,j), s(n,k) &=s(n-1,k-1)+sumlimits_{j=k+1}^{n-1}2cdot3^{j-k-1}s(n-1,j),quad 1le kle n. end{align*} The infinite lower triangular matrices $[r(n,k)]_{n,kge 0}$ and $[s(n,k)]_{n,kge 0}$, whose row sums produce the large and little Schroder numbers respectively, are two Riordan arrays of Bell type. Hence the above recurrences can also be deduced from their $A$- and $Z$-sequences characterizations. On the other hand, it is well-known that the large Schroder numbers also enumerate separable permutations. This propelled us to reveal the connection with a lesser-known permutation statistic, called initial ascending run, whose distribution on separable permutations is shown to be given by $[r(n,k)]_{n,kge 0}$ as well.
Bollobas and Nikiforov [J. Combin. Theory, Ser. B. 97 (2007) 859--865] conjectured the following. If $G$ is a $K_{r+1}$-free graph on at least $r+1$ vertices and $m$ edges, then $lambda^2_1(G)+lambda^2_2(G)leq frac{r-1}{r}cdot2m$, where $lambda_1(G)$ and $lambda_2(G)$ are the largest and the second largest eigenvalues of the adjacency matrix $A(G)$, respectively. In this paper, we confirm the conjecture in the case $r=2$, by using tools from doubly stochastic matrix theory, and also characterize all families of extremal graphs. Motivated by classic theorems due to ErdH{o}s and Nosal respectively, we prove that every non-bipartite graph $G$ of order $n$ and size $m$ contains a triangle, if one of the following is true: (1) $lambda_1(G)geqsqrt{m-1}$ and $G eq C_5cup (n-5)K_1$; and (2) $lambda_1(G)geq lambda_1(S(K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil}))$ and $G eq S(K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil})$, where $S(K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil})$ is obtained from $K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil}$ by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems.
A well-known conjecture of Tuza asserts that if a graph has at most $t$ pairwise edge-disjoint triangles, then it can be made triangle-free by removing at most $2t$ edges. If true, the factor 2 would be best possible. In the directed setting, also asked by Tuza, the analogous statement has recently been proven, however, the factor 2 is not optimal. In this paper, we show that if an $n$-vertex directed graph has at most $t$ pairwise arc-disjoint directed triangles, then there exists a set of at most $1.8t+o(n^2)$ arcs that meets all directed triangles. We complement our result by presenting two constructions of large directed graphs with $tinOmega(n^2)$ whose smallest such set has $1.5t-o(n^2)$ arcs.
Given a family of sets on the plane, we say that the family is intersecting if for any two sets from the family their interiors intersect. In this paper, we study intersecting families of triangles with vertices in a given set of points. In particular, we show that if a set $P$ of $n$ points is in convex position, then the largest intersecting family of triangles with vertices in $P$ contains at most $(frac{1}{4}+o(1))binom{n}{3}$ triangles.
We study a combinatorial problem that recently arose in the context of shape optimization: among all triangles with vertices $(0,0)$, $(x,0)$, and $(0,y)$ and fixed area, which one encloses the most lattice points from $mathbb{Z}_{>0}^2$? Moreover, does its shape necessarily converge to the isosceles triangle $(x=y)$ as the area becomes large? Laugesen and Liu suggested that, in contrast to similar problems, there might not be a limiting shape. We prove that the limiting set is indeed nontrivial and contains infinitely many elements. We also show that there exist `bad areas where no triangle is particularly good at capturing lattice points and show that there exists an infinite set of slopes $y/x$ such that any associated triangle captures more lattice points than any other fixed triangle for infinitely many (and arbitrarily large) areas; this set of slopes is a fractal subset of $[1/3, 3]$ and has Minkowski dimension at most $3/4$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
