Tagged Questions
0
votes
1answer
69 views
What is combinatorics? How is it related to Ramsey theory? What is the background needed to study it? [closed]
What is combinatorics? How is it related to Ramsey theory? What is the background needed to study it?
When I was reading about Ramsey theory in some reviews on some books, many people mentioned this ...
3
votes
0answers
45 views
What's the name for this unimodal sequence?
Let $a_0, a_1, \ldots, a_n$ be an increasing sequence of positive numbers, and consider the sequence $s_1,\ldots,s_n$, where
$$
s_k \;=\; \frac{a_0+\cdots + a_k}{k}.
$$
So
$$
s_1 \;=\; a_0+a_1,\quad ...
6
votes
1answer
69 views
A property of completely separable mad families
A family of sets $\mathcal{A}\subset[\omega]^\omega$ is called almost disjoint (a.d.) iff $\forall a,b\in\mathcal{A}(a\neq b\rightarrow |a\cap b|<\omega)$ and $\mathcal{A}$ is infinite (as such ...
1
vote
1answer
43 views
How to find instances when $d(a,b) = p^2$ for $p$ a prime.
Suppose I have a dimension formula (for a Lie algebra representation) given by
$\mathrm{dim}_{a,b} = {(a+1)(b+1)(a+b+2) \over 2}$. I now would like to find pairs $(a,b)$ where $\dim_{a,b} = p^2$ for ...
-1
votes
3answers
118 views
Good books on combinatorics
I have a math Ph.D. but my knowledge of combinatorics sucks and I simply don't know how to compute anything more complicated, i.e. what happens when we put restrictions on the allowed configurations ...
2
votes
2answers
78 views
Looking for combinatorial identity: $\sum\limits_{j=0}^k{n \choose k-j}{m \choose j}$ [duplicate]
Is there a nicer closed form expression for the following expression? $$\sum_{j=0}^k{n \choose k-j}{m \choose j}$$
2
votes
2answers
61 views
Learning Combinatorial Species.
I have been reading the book conceptual mathematics(first edition) and I'm also about halfway through Diestel's Graph theory(4th edition) I was wondering if I was able to start learning combinatorial ...
13
votes
3answers
307 views
Exceptional books on real world applications of graph theory.
What are some exceptional graph theory books geared explicitly towards real-world applications?
I would be interested in both general books on the subject (essentially surveys of applied graph ...
4
votes
2answers
70 views
The Dinitz problem
I would like to ask if someone knows about good books or online articles about The Dinitz problem or maybe someone can explain the problem a little.
Consider $n^2$ cells arranged in an $( n \times ...
7
votes
0answers
146 views
Citation for subset complement result
Let $S = \{s_1, \ldots, s_n\} \subset \{1, \ldots, 2n\}$. Consider two operations on $S$, unfortunately both called complement in different setting: let $A(S) = \{1, \ldots, 2n\} \setminus S$ (set ...
17
votes
1answer
310 views
A Combinatorial Proof of Dixon's Identity
Dixon's Identity states:
$$ \sum_{k} (-1)^k\binom {a+b}{b+k}\binom{b+c}{c+k}\binom{c+a}{a+k} = \binom{a+b+c}
{a,b,c}$$
A bit of history:
The case $a=b=c$ was proved by Dixon in 1891 using ...
2
votes
0answers
34 views
Combinatorics: Selecting non-adjacent subsets or objects arranged in a circle
Lets say you have a circular table that seats $n$ people and $b\lt n -1$ identitcal boys. If you were to divide the boys into $k$ teams of size $\geq 1$, how many ways are there to seat the boys so ...
0
votes
1answer
49 views
Ways of selecting sets of consecutive numbers arranged in a circle
Assume that you have 24 distinct numbers arranged in a circle. How many ways are there to choose two disjoint sets of adjacent numbers, one of size 2 and one of size 3? How would this change if the 24 ...
0
votes
1answer
33 views
Number of certain (0,1)-matrices, Stanley's Enumerative Combinatorics
Stanley's Enumerative Combinatorics (http://www-math.mit.edu/~rstan/ec/ec1.pdf) contains next fact:
1.1.3 Example. Let f(n) be the number of n × n matrices M of $0$’s and $1$’s such that every
row and ...
1
vote
1answer
37 views
Are there any combinatorial studies of Kirby calculus?
All of the other diagrammatic calculi I know of can be utilised with basically just combinatorial knowledge - for instance calculating knot and link polynomials. Are there similar combinatorial ...
3
votes
2answers
338 views
Proof a graph is bipartite if and only if it contains no odd cycles
How can we prove that a graph is bipartite if and only if all of its cycles have even order? Also, does this theorem have a common name? I found it in a maths Olympiad toolbox.
5
votes
1answer
106 views
Generalization of the Factorial function
Is there any standard generalization of the Factorial function where the "skips" per multiplication is a parameter? For example, one generalization could be: $a(a-b)(a-2b)(a-3b)...1$
I tried to ...
16
votes
3answers
499 views
What's next for me?
I'm in my last year of undergrad, and I would like to do original research for my senior thesis. I am already published in finite group theory and am looking for a new topic to study.
I have taken ...
5
votes
6answers
232 views
Books for combinatorial thinking
I have looked through many discrete mathematics books but they don't put much emphasis on combinatorial thinking.What books could you recommend that are more problem-oriented and emphasize ...
0
votes
0answers
10 views
Qualifying Parameters
you have two parameters, 1) rates of trees per land size, ranging from 30%-100%, and 2) rates of birds per land size, ranging from 5%-30%
goal is that you're trying to find out which is overall ...
4
votes
1answer
74 views
Formula for evaluation of character on a transposition
Let $\lambda\vdash n$ be a partition of $n\in\mathbb N$ and $\chi=\chi_\lambda$ the corresponding irreducible character of the symmetric group $S_n$. Denote by $\lambda^t$ be the transpose of ...
2
votes
0answers
67 views
What is the correct technical term for this generalization of an integer partition?
Given a vector $v$ with non-negative integer coordinates, is there a technical term for an unordered tuple of vectors $(v_1,\dots, v_k)$ with non-negative integer coordinates such that
$v_1+\dots+v_k ...
7
votes
3answers
152 views
Reference for combinatorial game theory.
What is a good reference material for elementary combinatorial game theory?
By combinatorial game theory I mean chiefly the study of zero-sum, deterministic two-player games (perhaps even more ...
1
vote
1answer
52 views
generalization of base-n notation from naturals to fractions
not exactly sure how to best ask this. base-$n$ notation involves a series of digits written where each digit is a natural number less than $n$.
is there some math/theory generalization of ...
8
votes
2answers
174 views
Introduction to Infinitary Combinatorics
What are some good texts for someone interested in becoming acquainted with the "big ideas" of infinitary combinatorics? If you'd like more specificity, assume the reader has respectable mathematical ...
4
votes
0answers
187 views
Number of labelled graphs with $n$ nodes, $k$ edges and $t$ triangles
How many labelled undirected graphs are there with precisely $n$ vertices, $k$ edges, and $t$ triangle subgraphs? (By triangle I mean a graph with three vertices and three edges.)
(Clarification: I ...
4
votes
5answers
273 views
Book recommendation
I have been studying number theory for a little while now, and I would like to learn about integer partitions and q series, but I have never studied anything in the field of combinatorics, so are ...
6
votes
2answers
144 views
Involutions and Abelian Groups, II.
In the thread Involutions and Abelian Groups, I supplied a solution to the following interesting problem (with the help of hints provided by the OP).
Let $ G $ be a finite group and $ I(G) $ the ...
8
votes
8answers
575 views
Books/Resources on generating functions
I'm currently doing a research on generating functions, but I have only found few books on this topic. Can anyone provide references (if possible, trying to assess the level of math competence ...
7
votes
3answers
101 views
Graph on the cover of Bollobás's “Combinatorics”
I was browsing the library and I found Bela Bollobás book "Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics" and, on its cover, it has a graph that I don't ...
1
vote
2answers
149 views
How many $N$ digits binary numbers can be formed where $0$ is not repeated
How many $N$ digits binary numbers can be formed where $0$ is not repeated.
Note - first digit can be $0$.
I am more interested on the thought process to solve such problems, and not just the answer.
...
11
votes
1answer
167 views
On the impossibility of proving certain problems using double counting.
Usually in combinatorics, I love proofs by double counting. It gives me a very happy feeling to know a double counting proof. I feel I understand the problem better. A close younger sibling of this ...
5
votes
1answer
136 views
Extending a partial order to antichains
Let $(S, \leq)$ be a partial order. Let $T$ be the set of antichains of $S$ (i.e., subsets of $S$ whose elements are pairwise incomparable). Define a relation $\leq'$ on $T$ as follows: for all $A$, ...
7
votes
1answer
84 views
Probability of duplicate free sample of iid discrete random sample
Let $\{X_1,\ldots,X_n\}$ be independent identically distributed discrete random variables. I am interested in computing the probability of the event that the sample is duplicate free:
$$
...
3
votes
1answer
75 views
Any forest on 5 or more vertices contains an independent set of size 3.
I am looking for a short proof of this fact. This is clearly true by drawing these trees, but I am having trouble putting it into writing. Somehow I need to select 3 of the 5 vertices and show that ...
3
votes
3answers
135 views
Counting directed acyclic graphs with the same partial ordering
We are given a partially ordered set $P$.
Let $L$ denote the set of all linear extensions of $P$ (or equivalently, the set of all topological sortings of the nodes).
We want to count the number of ...
0
votes
1answer
72 views
Struggling to prove fact about classes of structures
I am having difficulties proving the following:
If $\cal{A}$ is a connected class (i.e $\cal{A_\emptyset} = \emptyset$), then I need to show that the powers of $\mathcal{A}$ form a locally finite ...
0
votes
1answer
55 views
Convergence of series of elementary symmetric functions
Let $x_1,x_2,x_3,\ldots$ be an infinite sequence of real numbers (or assume they're complex numbers if you find that convenient).
Let $e_0,e_1,e_2,e_3,\ldots$ be the elementary symmetric functions of ...
2
votes
3answers
161 views
Graph theory and combinatorics text
I am looking for a graph theory and combinatorics text for someone with limited background in linear algebra(I am not yet into college math;I have only read a bit of group theory and completed single ...
1
vote
1answer
56 views
Triangular numbers
http://en.wikipedia.org/wiki/Triangular_number
I am looking at Triangle numbers and how wikipedia arrived at test for "Triangularity" by checking $(\sqrt{8x + 1} - 1)/2$
The article references item ...
3
votes
1answer
281 views
Longest Odd/Even Sequence in Composite Patterns
NOTE I have completely reworded this because I made a complete hash of it the first time, it got worse as I added to it. I apologize to anyone who might have been confused, and hope that this will be ...
5
votes
1answer
139 views
Is there any good reads for Goodwillie calculus out there?
I have a basic understanding of combinatorial species and category theory and now I am curious about this functor calculus or Goodwillie calculus. Can anyone kindly recommend me a nice place to start. ...
1
vote
0answers
79 views
Shifted Young tableaux & Hook numbers & Bulgarian Solitaire
I would like to find articles or documentation regarding this process:
Starting from what ever integer partition, e.g. 5,2 for the number 7. Construct his Young tableaux and then fill it with Hook ...
1
vote
1answer
56 views
“Cookbook” methods for neighborhood structure design in simulated annealing for combinatorial optimization?
What are some "cookbook" methods for neighborhood structure design in simulated annealing for combinatorial optimization?
Are some reviews or books that contain some "cookbook" methods for ...
11
votes
2answers
396 views
Whats the probability a subset of an $\mathbb F_2$ vector space is a spanning set?
Let $V$ be an $n$-dimensional $\mathbb F_2$ vector space. Note that $V$ has $2^n$ elements and $\mathcal P(V)$ has $2^{2^n}$.
I'm interested in the probability (under a uniform distribution) that an ...
13
votes
7answers
1k views
Where are good resources to study combinatorics?
I am an undergraduate wiht basic knowledge of combinatorics, but I want to obtain sound knowledge of this topic. Where can I find good resources/questions to practice on this topic?
I need more than ...
7
votes
2answers
152 views
Self-avoiding walks
Let $c_n$ be the number of self-avoiding walks in ${\mathbb Z}^2$ of length $n$. Because $c_n$ is a submultiplcative sequence ($c_{n+m} \leq c_nc_m$ for all $n, m \geq 1$), Fekete's lemma tells us ...
4
votes
0answers
72 views
Law of large numbers for Plancherel random Young diagrams
Do you know a reference book on the law of large numbers for random Plancherel Young diagrams ? I know the book of Kerov, but actually, it is only a compilation of his articles, and i need something ...
1
vote
2answers
270 views
Is there a winning strategy for Scrabble?
I am sure many of us are addicted to the popular Facebook app: Words with Friends, which is basically an online version of Scrabble. In Playing Games with Algorithms:Algorithmic Combinatorial Game ...
2
votes
3answers
161 views
Number of positive integer walks from 0 to b.
It is well known that the number of walks of length $m=2k+1$ starting at $0$ and ending at $0$ of step size $\pm 1$ and always nonnegative is the number of Dyck paths from $(0,0)$ to $(k,k)$ i.e. the ...
