3
votes
1answer
163 views

What is this myth/legend and origin of related ideas?

There is a story I recently heard but the story teller (who read about it someone on the Internet) have forgotten the majority of the story, so there is little I can work on: my search attempts went ...
4
votes
2answers
71 views

Theoretical computer science text for mathematician

I am a high school student, I know some basic programming in java,python and visual basic. I love combinatorics and I have encountered various cases in which I have found some problems are really ...
7
votes
0answers
114 views

Infinite sum involving $q$-adic representations of whole numbers and $q$-factorial numbers

Let $q \in \mathbb{N}_{\geq 2}$. For $n \in \mathbb{N}_0$, let $$\mathrm{fac}_q(n) := \prod_{i=1}^n (1+q+\dots+q^{i-1}) = \prod_{i=1}^n \frac{q^i-1}{q-1}$$ be the $q$-factorial of $n$. In particular, ...
3
votes
0answers
49 views

Conjectured Value of Ramsey Number $R(3,10)$

It is known that the value of the Ramsey number $R(3,10)$ is either 40, 41, or 42. Have any experts in the field offered a conjecture as to which it might be?
1
vote
0answers
20 views

Maximal chain in (strong) Bruhat order

Consider the (strong) Bruhat order, $\leq_{B}$, on the symmetric group $S_n$. Suppose there are permutations $\pi,\sigma \in S_n$ such that $\pi \geq_{B} \sigma$. Suppose further that they satisfy the ...
2
votes
3answers
70 views

Very elementary number theory and combinatorics books.

I know the basics of logic, sets, relations and the like, so studying intros to abstract algebra and real analysis is not that hard. That said, I have a deficiency when it comes to elementary number ...
1
vote
1answer
39 views

Directory for known bound of Ramsey numbers?

I must admit I'm not a google connoisseur, but I have not been able to find a place where I can find known lower bounds for many Ramsey numbers, something ideal would be if I could insert (3,44) and ...
1
vote
0answers
26 views

Number of 3-way contingency tables

Denote by $f(n)$ the number of $2\times 2 \times 2$ contingency tables with all 2-dim marginals equal to $n$. What is $f(n)$? It is easy to see that $f(n)$ is polynomial of degree 4, since it ...
3
votes
3answers
47 views

Recurrence relation for product of binomial coefficients

We all know the standard recurrence relation for binomial coefficients: $$ \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k} $$ Is there any finite-step recurrence relation one can write down for a ...
1
vote
1answer
67 views

Math competitions resource at university level

I want some problems especially in Algebra field for math competitions at undergraduate math students level. Does anybody here know book, website,... that I can use?!
0
votes
4answers
69 views

A basic Combinatorics Book

So, this is my problem...I have completed my boards and among all others, I have a great weakness in combinatorics. So this means I can utilize my free time now to address this problem. I think it is ...
4
votes
2answers
419 views

simple games with cute winning strategies?

Im thinking of games of two players ($A$ goes first and $B$ second) like the following: There are 35 chips in a table, during each turn a player can remove 1,2,3 or 4 chips. Prove player $B$ can ...
8
votes
4answers
208 views

Does $\sum_{k=0}^{k=n} {n \choose k} k!$ have a closed form for integers $k,n$?

While doing research in computer system, I came across the following summation: $$S_n = \sum_{k=0}^{n} {n \choose k} k! = \sum_{k=0}^{n} \frac{n!}{(n-k)!}$$ where both $n$ and $k$ are integers. $S_n$ ...
5
votes
1answer
193 views

Asymmetric roles that are symmetric in every instance

This is similar to something else I posted, but this time we'll pretend we've never heard of infinite sets or infinite series. \begin{align} & \sin(\alpha+\beta+\gamma+\delta+\varepsilon+\zeta) ...
4
votes
2answers
200 views

A conjecture relating Multiple Zeta Values and the Polya Enumeration Theorem

Let me state my motivation. I believe that the Polya Enumeration Theorem and Multiple Zeta Values (the classic being the Basel problem and the values of the Riemann zeta function at the even ...
1
vote
0answers
22 views

Generalized permutahedron and random polytopes

The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...
7
votes
6answers
411 views

Book on combinatorial identities

Do you know any good book that deals extensively with identities obtained using combinatorial and/or probabilistic arguments (e.g., by solving the same combinatorial or probability problem in two ...
2
votes
1answer
110 views

Characterizing a certain set of matrices arising from binary trees

Suppose I have a binary tree, like v1 v4 \ / -------- / \ v2 v3 I can write a matrix for this tree whose $(i,j)$th ...
1
vote
0answers
23 views

Non-Intersecting up-right lattice paths and standard Young Tableaux

Consider the Lattice $\mathbb{Z}^2$ and an initial set of points with coordinates $(0,u_1)$, $(0,u_2)$, $\cdots$ $(0,u_n)$, final set of points $(m,v_1),(m,v_2),\cdots,(m,v_n)$, where $v_i,u_i$ are ...
0
votes
2answers
39 views

Alternative reference for number of restricted partitions

I am looking for the number of partitions of some number $n$ into $k$ parts. Following the Wikipedia article on partitions, I ended up with Andrew's book [1]. Judging by Google's preview Chapter 3 ...
0
votes
1answer
27 views

Number of non-increasing boolean functions of $n$ booleans, up to permutations.

How many non-increasing boolean functions of $n$ boolean variables are there? I don't want to count functions that ignore some of their inputs. If two or more functions differ only by permuting their ...
6
votes
1answer
72 views

Gowers' proof of Szemerdi's theorem

Are there any good books or other resources (expository notes) which explains Gowers' proof of Szemerdi's theorem in detail?
0
votes
0answers
30 views

A game of repeatedly taking the union of sets

Suppose that I have the set family $\mathcal{A}_1 = \{A_1, \dots, A_k\}$. We play the following game, which consists of a sequence of iterations. In the first iteration, we choose an arbitrary ...
0
votes
0answers
67 views

Describing the sequence A224239.

I've been trying to describe mathematically the $n$th term $a_n$ of the sequence A224239. We get $a_n$ by counting the distinct ways to fill an $n\times n$ grid with squares of smaller integer size, ...
1
vote
0answers
58 views

Monoid on ordered partitions of a natural number

Fix a natural number $n$, and let $O_n$ be the set of ordered partitions of $n$. For example $O_3=\{1+1+1,1+2,2+1,3\}$ which can also be written as $\{1|2|3,1|23,12|3,123\}$. We can define two ...
2
votes
0answers
48 views

References for chromatic symmetric functions of hypergraphs

Define a hypergraph to be a pair $H = (V,E)$ where $V$ is a set of vertices and $E$ is any set of subsets of $V$ called edges. Thus if every edge $U \in E$ has only two elements, then the hypergraph ...
0
votes
1answer
22 views

looking for hypergraph decompositions

there are many thms for/types of graph decompositions. in contrast, am looking for various types of hypergraph decompositions...? also esp interested in graph analogs that translate somehow eg ...
0
votes
1answer
163 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
5
votes
2answers
118 views

What can we say about the kernel of $\phi: F_n \rightarrow S_k$

Let $F_n$ denote the free group on $n$ generators and let $S_k$ denote the symmetric group on the integers $\{1,\dots, k\}$, and the action of homomorphism $\phi$ (as given in the title) on the ...
2
votes
2answers
81 views

Articles on matchstick puzzles

There are many ingenious puzzles involving matchsticks that are arranged as squares, rectangles or triangles, and can be moved under some restrictions (for a lot of examples see ...
2
votes
1answer
73 views

Finding the super-mean (NOT the mean) of a set of numbers.

the super-mean is found by grouping pairs of numbers and finding the average successively until there is just one number. For example, $$(1-2-3-4-5) \to ((1+2)/2,(2+3)/2,(3+4)/2,(4+5)/2) \\ ...
0
votes
0answers
29 views

Variants of sudoku that require very little give aways

Consider the following generalization of sudoku (it might already exist under a different name, any reference is welcome): Let $n$ be a natural number. By a generalized sudoku I understand a ...
9
votes
2answers
180 views

An extrasensory perception strategy :-)

Inspired by classical Joseph Banks Rhine experiments demonstrating an extrasensory perception (see, for instance, the beginning of the respective chapter of Jeffrey Mishlove book “The Roots of ...
4
votes
2answers
140 views

Maximum edges in a square free graph

Square free graph : Graphs with minimum cycle length greater than 4. Question : What is the maximum number of edges possible for a square free graph $G(V,E)$ given that $|V|$ = n. Is it of the order ...
0
votes
0answers
63 views

Ham Sandwich theorem used in combinatorics problem involving beads on a necklace

Ok, so according to a friend of mine you can use the ham sandwich to prove the following theorem: Suppose there is a necklace with $m$ types of beads and $2n_1,2n_2...2n_m$ beads of each colors. So ...
1
vote
0answers
15 views

Online Encyclopedia of Error-Correcting Codes

Is there some kind person on the internet who is making an exhaustive collection of error-correcting codes? I'm looking for something analogous to the OEIS. I want to ask questions like "what is this ...
5
votes
1answer
120 views

Are there mathematical (combinatorial) objects to represent such set systems?

Background: This is a problem arising from my study on computer science. In its appearance, it involves set systems. A set system $\mathcal{S} = \{S_1, S_2, \ldots, S_m \}$ is a collection of ...
5
votes
3answers
205 views

Symmetries of combinatorial structures.

Studying the automorphism groups of graphs/finite geometries/designs has been quite useful and important for both group theory and combinatorics. I know of the following books which cover the ideas ...
0
votes
0answers
42 views

A Survey on Rota's Conjecture

I am looking for a survey on Rota's Conjecture (1970). I am more interested in geometric aspects of the conjecture and any geometric content related to the conjecture. Any reference would be helpful. ...
1
vote
0answers
51 views

How many Hamiltonian loop are there in a big rectangle?

Suppose I have some big rectangle made of $n \times m$ squares, and I want to place tiles on it in a manner that makes a picture of a hamiltonian loop. I can transform this problem into a problem ...
2
votes
0answers
66 views

Maximum bin load for $\alpha n$ balls into $n$ bins

In a paper I am reading the author writes: A standard result concerning balls and bins shows that if we throw at least $\alpha n$ balls into at most $n$ bins, then the maximum bin load is ...
1
vote
1answer
44 views

Counting Self-dual posets

An exercise in Stanley's Enumerative Combinatorics (Chapter 3, ex. 8) asked for an example of a finite self-dual poset, (i.e. there is a bijection $f: P\to P$ such that $s\le t \Longleftrightarrow ...
1
vote
2answers
65 views

Does there exist a branch of mathematics that specifically study the number of lattices enclosed by a region?

I have seen that sometimes, in particular in number theory and combinatorial commutative algebra, our questions are somehow related to finding the number of points with integer components in a ...
2
votes
0answers
46 views

Does the notion of graph with vertex multiplicity exist?

I need to use graphs where each vertex gets a natural number, $b(v)$, its multiplicity. These numbers indicate how many 'replications' of the vertex we have. It is actually a way to write in a ...
1
vote
2answers
94 views

Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
2
votes
3answers
89 views

Books to understand Szemeredi's regularity lemma?

I want to understand the Szemeredi theorem and read on the thoery relating to it. Which books should I pick up to do this? Regards
0
votes
1answer
43 views

Let $G$ be bipartite, what is $\min\{|X_0|:\,X_0\subseteq X\,,N(X_0)=Y\}$

Let $G$ be a bipartite graph. Let $X,Y$ be the two partite sets of $G$. Suppose further that $N(X)=Y$. Consider the problem of finding: $$\min\{|X_0|:\,X_0\subseteq X\,,N(X_0)=Y\}$$ What are some ...
2
votes
2answers
271 views

Books in Combinatorial optimization

I wrote Combinatorial optimization in the title , but I am not sure if this is what I am looking for. Recently, I was getting more interested in Koing's theorem, Hall marriage theorem . I am ...
2
votes
2answers
124 views

Combinatorics, permutations. Books

I want to study about combinatorics, permutations. I don't need for complicated things, I only want to understand this notions very well and only the to try to study more complicated notions. Can ...
1
vote
0answers
38 views

Average number of draws to repeat a random number?

In a random sequence of equiprobable integer numbers between [1,n], how can I find the average number of draws needed for a single integer to repeat? Please recomment a good book.