This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

23
votes
0answers
478 views

On the number of complete and gap-free compositions

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
14
votes
0answers
312 views

proving an integer is non-negative by showing there is a vector space with it as its dimension.

The other day i attended a lecture on methods to show whether or not a number is an integer. We were given examples of showing it is the number of ways to count something, and to show there exist ...
12
votes
0answers
113 views

Involutions, RSK and Young Tableaux

Let $S_n$ be the symmetric group on $n$ elements. The Robinson-Schensted-Knuth (RSK) correspondence sends a permutation $\pi\in S_n$ to a pair of Standard Young Tableaux $(P,Q)$ with equal shapes ...
12
votes
0answers
179 views

Combinatorial Interpretation of a Certain Product of Factorials

Let $\mu$ denote the Moebius function. What is a combinatorial interpretation of the following integer, \begin{align} \prod_{d \mid n} d!^{\,\mu(n/d)}, \end{align} where the product is taken over ...
11
votes
0answers
396 views

$f(x)=\sum_{t}{x \choose t}{n-x \choose k-t}$ - even or odd?

The following function popped in my research: $$f(x)=\sum_{\array{0\le t\le k \\ t\equiv_p a}}{x \choose t}{n-x \choose k-t}$$ Where: n,k are natural numbers and $k\le n$. t is taken over all ...
10
votes
0answers
214 views

Multiplying by an irrational number in combinatorial problems

Everybody knows that the number of derangements of a set of size $n$ is the nearest integer to $n!/e$. It is also widely known that the $(n+1)$th Fibonacci number $F_{n+1}$ is the nearest integer to ...
10
votes
0answers
461 views

How to find a total order with constrained comparisons

There are 25 horses with different speeds. My goal is to rank all of them, by using only runs with 5 horses, and taking partial rankings. How many runs do I need, at minumum, to complete my task? As ...
10
votes
0answers
345 views

Prove this determinant identity combinatorially

This is for those of you who understand the Lindstrom-Gessel-Viennot lemma. I am looking for a proof of the following identity using paths and such: Let $A$ be an $n\times n$ matrix, and for ...
9
votes
0answers
173 views

Ruin time for a two-input “risk only” slot machine

Imagine a "risk only" slot machine that takes 'coins' corresponding to some real number fraction of a dollar $p$, returns the coin with probability $p$, and eats the coin with probability $(1-p)$. ...
9
votes
0answers
385 views

How strong is the statement that Thompson F is amenable?

Justin Moore's proof turned out to have an error I just attended Justin Moore's talk on this today. Since I am neither a group theorist nor a combinatorist, and is not familiar with ultrafilters I ...
8
votes
0answers
99 views

How many arrays with crossed cells, order of rows/columns irrelevant

I've been struggling with this simple problem for months though as I am a newbie to… well, maths, there's high chance someone more educated than myself may get it right! Let's consider an array or a ...
8
votes
0answers
201 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
8
votes
0answers
147 views

Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old. Searching relevant ...
7
votes
0answers
221 views

Minimal time gossip problem

The gossip problem (telephone problem) is an information dissemination problem where each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the ...
7
votes
0answers
177 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 ...
7
votes
0answers
151 views

A variation on the Look and Say Sequence and some questions about it.

For information on the sequence mentioned in the title, see http://en.wikipedia.org/wiki/Look-and-say_sequence. This is an original problem. Suppose instead of "describing" the numbers in a string in ...
7
votes
0answers
175 views

Extracting an (almost) independent large subset from a pairwise independent set of Bernoulli variables

Let $n>1$, and let $X_1,X_2, \ldots ,X_n$ be non-constant random variables with values in $\lbrace 0,1 \rbrace$. Let us say that a subset of variables $X_{i_1},X_{i_2}, \ldots,X_{i_d}$ is complete ...
7
votes
0answers
129 views

How to prove that my sum coincides with a sequence on the Online Encyclopedia of Integer Sequences?

I have a topological space $X$ whose reduced $\bmod 2$ Betti numbers (that is to say, the dimension of the $\bmod 2$ reduced homology) I computed to be $$\small \dim \tilde{H}_t(X; {\mathbb{Z}}_2) = ...
7
votes
0answers
158 views

Different notions of q-numbers

It seems that most of the literature dealing with q-analogs defines q-numbers according to $$[n]_q\equiv \frac{q^n-1}{q-1}.$$ Even Mathematica uses this definition: with the built-in function QGamma ...
7
votes
0answers
208 views

A sequence similar to the Catalan numbers

The $n$-th Catalan number $c_n$ has the closed form $\frac1{n+1}\binom{2n}{n}$ and follows the recursion $c_n = \sum\limits_{i = 0}^{n-1} c_{n-1-i}c_i$ I am interested in the quantity $e_n$ which ...
7
votes
0answers
212 views

Lucky chance or combinatorial cause?

Consider an $n \times 1 - $rectangle where the $n$ squares are numbered $1$ to $n$. Cover this rectangle with white squares $a$, black squares $b$ and dominoes $dd$. To each covering of the rectangle ...
7
votes
0answers
288 views

Number of possible crosswords

I was staring at my crossword this morning when I had this question: How many possible arrangement of grid squares are there in an $N\times N$ crossword, provided we impose certain constraints? I take ...
6
votes
0answers
63 views

Knight's metric: ellipse and parabola.

Knight's metric is a metric on $\mathbb{Z}^2$ as the minimum number of moves a chess knight would take to travel from $x$ to $y\in\mathbb{Z}^2$. What does a parabola (or an ellipse) became with this ...
6
votes
0answers
48 views

How many pairs of nilpotent, commuting matrices are there in $M_n(\mathbb{F}_q)$?

As a follow-up to this question, I've been doing some work counting pairs of commuting, nilpotent, $n\times n$ matrices over $\mathbb{F}_q$. So far, I believe that for $n=2$, there are $q^3+q^2-q$ ...
6
votes
0answers
140 views

Selecting a subset from a set such that a given quantity is minimized

Let $A$ be is a set of some $p$-dimensional points $x \in \mathbb{R}^p$. Let $d_x^A$ denote the mean Euclidean distance from the point $x$ to its $k$ nearest points in $A$ (others than $x$). Let $C ...
6
votes
0answers
83 views

Knuth equivalence of unshuffles

For any permutation $\sigma\in S_k$ and any $i\in\left\lbrace 1,2,...,k\right\rbrace$, I will denote $\sigma\left(i\right)$ by $\sigma_i$. For any word $w$, I will denote by $\mathrm{st}w$ the ...
6
votes
0answers
78 views

Sum-Product Generating Functions

Let $A_n$ be a family of sequences $\{a_i\}_{i=1}^n$ of length $n$. I'll refer to sequence elements of $A_n$ as $a$. Then define $$G(z):=\sum_{a\in A_n}\prod_{i=1}^n(z+a_i).$$ Here's one possible ...
6
votes
0answers
131 views

Rotations of a tetrahedron

Let $P$ be a tetrahedron inside an sphere such that all of its vertices are on the surface of the sphere. Suppose that three quarters of sphere's surface is colored black. Show that there is a ...
6
votes
0answers
157 views

Symmetric polynomials

I've got a seemingly simple question that I've become curious about as a result of supervising some undergraduate research. Let's suppose we have some sequence of polynomials $f_0, f_1, f_2, \cdots ...
6
votes
0answers
227 views

Finding the maximum number of subspaces of a vector space over finite field that satisfy these relations

I have a question and I am stuck. I was wondering if anyone has a thought, before I start a brute-force search. For $q$ a prime number and $n =6$, let $\mathbb {F}_{q}^{n}$ be an $n$-dimensional ...
6
votes
0answers
137 views

Can we rearrange the integers, such that the arithmetic average of any two numbers does not appear between them?

Can we rearrange the integers, such that the arithmetic average of any two numbers does not appear between them? In other words: Can we have a sequence $\{a_n\}_{n\in \mathbb{Z}}$, where all integers ...
6
votes
0answers
118 views

Dimension of the space of algebraic Riemann curvature tensors

Given $n\in \mathbb N$, consider the vector space $\mathbb R^{n^4}$ whose elements I will denote by $(R_{abcd})$ with indices $a,b,c,d \in \{1, \dots, n\}$. This vector space is $n^4$-dimensional. The ...
6
votes
0answers
128 views

The right way to motivate lattice theory in a combinatorics class

I am attending a course on combinatorics. I was asked to present Möbius functions on lattices for this course. I was trying to look for a simple non-trivial problem that illustrates the need for ...
6
votes
0answers
451 views

Probability, choose a box and then take exactly two white balls

There are $5$ boxes. There are $5$ white and $3$ black balls in two boxes, and $4$ white and $6$ black balls in the other three boxes. One box is randomly chosen. $3$ balls are randomly taken from ...
6
votes
0answers
121 views

Characterization of Sequences with Integral Binomial Coefficients

For any sequence of positive integers $\{ a_i \}_{i \ge 1}$ we can define the generalized binomial coefficients $\binom{n}{k}_{a}$ as follows: $$m!_a = a_1 a_2 \cdots a_m, \binom{n}{k}_a = ...
6
votes
0answers
155 views

Combinatorial Proofs of Real Analysis Identity

In this question,a proof using real analysis is given of the following identity: $$ \sum_{n=1}^{\infty} \frac{(n-1)!}{n \prod_{i=1}^{n} (a+i)} = \sum_{k=1}^{\infty} \frac{1}{(a+k)^2}$$ Is there a ...
6
votes
0answers
281 views

Is there a Steiner system S(6,9,45)?

Background: the Belgian Lottery switched its main game this year to a draw of 6 balls out of a pool of 45, plus a bonus number which doesn't matter for the sake of this question. Assuming someone ...
6
votes
0answers
225 views

Young Tableaux as Matrices

These questions are motivated only by curiosity. Take a Young tableau of shape $(\lambda_1,\lambda_2,\ldots,\lambda_n)$, where $\lambda_1\geq\lambda_2\geq\ldots\geq \lambda_n)$. Is there any physical ...
6
votes
0answers
143 views

Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?

Remark: I recently rewrote this post, hoping to get answers! I am analyzing the following experiment: Pick an $x \in \{0,\ldots,2k\}$ uniformly at random Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
6
votes
0answers
88 views

Optimal lower bound of $k$-sums for the integers $\{1,2,\ldots,n\}$ arranged around a circle in arbitrary order.

This question is motivated by the following two questions and is a slightly generalized version of them. Some three consecutive numbers sum to at least $32$ Integers $1, 2, \ldots, 10$ are ...
6
votes
0answers
85 views

Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture states that the graph (i.e. $1$-skeleton) of a $d$-dimensional polytope with $n$ facets has diameter at most $n - d$. It was known for a long time that it sufficed to prove it ...
6
votes
0answers
204 views

Counting ordered tuples with an additional condition

Let $a_1 \le a_2 \le ... \le a_n$ be positive integers. I'm looking for a closed formula of the number $f(a_1,...,a_n)$ of all (ordered) tuples $(x_1,...,x_n)$ of positive integers statisfying $$x_1 ...
6
votes
0answers
194 views

Uses of Chevalley-Warning

In the recent IMC 2011, the last problem of the 1st day (no. 5, the hardest of that day) was as follows: We have $4n-1$ vectors in $F_2^{2n-1}$: $\{v_i\}_{i=1}^{4n-1}$. The problem asks : Prove the ...
6
votes
0answers
106 views

Generalizing Quadratic Reciprocity Law with Dilates

Eisenstein's proof of the Quadratic Reciprocity (QR) (and its Jacobi symbol generalization) both rely on counting lattice points in two congruent triangles. If we take $t$-dilates of these triangles, ...
5
votes
0answers
50 views

Maximal hamming distance

Here is a combinatorial problem : let $\Sigma=\{\alpha_1,\ldots,\alpha_n\}$ be an alphabet and we consider any words over $\Sigma$ of length $n$. We also define over the set of such words the Hamming ...
5
votes
0answers
71 views

Measure minimization for a combination of overlapping sets

This problem may have been worked out before but I don't know where to start looking so I hope one of you can help me. The problem is as follows: There are $N$ variable-sized finite sets ...
5
votes
0answers
68 views

choose at most k from n

The Problem Suppose I have a bit string of length $n$ consisting of all zeros. I want to flip some of the zeros to ones, but I am only able to flip at most $k$ bits (i.e., I can flip any number of ...
5
votes
0answers
66 views

Generalization of Gray codes

A friend of mine asked me if it was possible - physical difficulties aside - to generate all 32 combinations of raised/lowered fingers by changing status of a fixed number of fingers at every step. ...
5
votes
0answers
92 views

A combinatorial problem which should have been studied

I've got a (what I think is) combinatorial problem: assume we have $n$ different elements, and we want to use these elements to construct some sets, each of which contains $m<n$ different elements. ...
5
votes
0answers
163 views

How to partition $S$ in this way?

Assume: $$ P =\{p_1,p_2,\cdots,p_K\}\subset \{1,2,\dots,N\},\quad |P| = K, \qquad x \in \mathbb{R}_+^K , \qquad w = e^{-j\frac{2\pi}N} $$ and, $$ f(l) = \sum_{i=1}^K \sum_{j=1}^K x_i x_j ...