For 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)

22
votes
0answers
519 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 ...
20
votes
0answers
693 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 ...
14
votes
0answers
190 views

Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
14
votes
0answers
492 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 ...
13
votes
0answers
287 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 ...
12
votes
0answers
82 views

Prove a matrix of binomial coefficients over $\mathbb{F}_p$ satisfies $A^3 = I$.

(This problem is problem $1.16$ in Stanley's Enumerative Combinatorics Vol. 1). Let $p$ be a prime, and let $A$ be the matrix $A = \left[\binom{j+k}{k} \right]_{j,k = 0}^{p-1}$, taken over the ...
12
votes
0answers
552 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 ...
11
votes
0answers
230 views

Probability of two zero inner products

Consider a random $n+1$-dimensional vector $v$. Each $v_1,\dots,v_n$ equals $1$ with probability $1/2$ and $-1$ with probability $1/2$ independently. We also set $v_{n+1} = v_1$. Now consider a ...
11
votes
0answers
254 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
11
votes
0answers
277 views

How many $n$-element subsets $A$ of $\{1,2,3,\cdots,2n\}$ with specified sum are there?

Question: Let $ n$ be an postive integer number.and let $A=\{x_{1},x_{2},\cdots,x_{n}\}$, How many $ n$-element subsets $ A$ of $ \{1,2,\dots,2n\}$ are there,such ...
10
votes
0answers
153 views

On the maximum number of polynomials in a certain subspace

I've already asked this question on mathoverflow, but no one answered. So I put this problem also here. Sorry for that. Let $\mathbb F_q$ be a finite field and let $e, k$ be positive integers with ...
9
votes
0answers
199 views

Distributing groups of objects into boxes

How can I enumerate the number of ways of distributing distinct groups of identical objects (but various cardinality) into $k$ boxes such that at most one box is empty $(1)$ and no combination of ...
9
votes
0answers
457 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 ...
9
votes
0answers
209 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 ...
9
votes
0answers
169 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 ...
8
votes
0answers
92 views

number of factorizations of distinct factors

Let $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ an integer with $p_i$ prime and $e_i \in \mathbb N$. The prime factorization can assumed to be known, i.e. we already know $p_1,\ldots,p_k$ and $e_1 , ...
8
votes
0answers
121 views

Has anyone seen this combinatorial identity involving the Bernoulli and Stirling numbers?

Does anyone know a nice (combinatorial?) proof and/or reference for the following identity? $$\left( \frac{\alpha}{1 - e^{-\alpha}} \right)^{n+1} \equiv \sum_{j=0}^n \frac{(n-j)!}{n!} |s(n+1, ...
8
votes
0answers
124 views

How many different paths to reach $(p,q,r)$ from $(0,0,0)$ without intersection

Problem: In $\mathbb{Z}^3$ starting from $(0,0,0)$ we try to reach $(p,q,r)$ with a sequence of moves. In each step we make a move from a point to another point under following conditions: You can ...
8
votes
0answers
125 views

To what extent is it possible to generalise a natural bijection between trees and $7$-tuples of trees, suggested by divergent series?

In the paper "Seven Trees In One" by Andreas Blass, a "very explicit" bijection is found between trees and 7-tuples of such trees. The idea to construct such a bijection stems from looking at some ...
8
votes
0answers
237 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 ...
8
votes
0answers
490 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
164 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) = ...
8
votes
0answers
365 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 ...
7
votes
0answers
51 views

Dominating a Four Dimensional Chessboard with Rooks

There is a family of chess problems where you try to dominate a board with as few copies of a given piece as possible. The chessboard is dominated if every square either contains a piece, or is ...
7
votes
0answers
81 views

In how many ways can the integers from $1$ to $n$ be divided into two groups with the same sum?

In how many ways can the integers $1,2,\ldots,n$ be divided into two groups with the same sum? I have tried calculating some of these values for small $n$, but cannot seem to find a pattern. Any ...
7
votes
0answers
51 views

Number of paths of a certain type in a triangular array

Consider the $X_n$ set of finite integer sequences $(x_1, \ldots, x_{n})$ of length $n$ for which $x_1 = 0$ and $|x_k - x_{k+1}| = 1$ for each $k \in \{1, \cdots, n-1 \}$. Obviously $|X_n| = 2^{n-1}$. ...
7
votes
0answers
75 views

Showing that poset of set of supports of a vector space is semimodular

Let $W$ be a subspace of the vector space $\mathbb{K}^n$, where $\mathbb{K}$ is a field of characteristic $0$. The support of a vector $v = (v_1,\ldots, v_n) \in \mathbb{K}^n$ is given by ...
7
votes
0answers
183 views

How to maximize the number of operations in process

In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word. If we are given an ordered ...
7
votes
0answers
118 views

Check whether a polynomial ideal is prime in the power series ring

I would like to know whether the ideal $I = \langle y^{2}(y^{2}-x^{2}) + w^{7}, y^{2}(y^{4}-x^{4}) + z^{7}\rangle$ is prime in $\mathbb{C}[[x,y,z,w]]$, the ring of formal power series in the ...
7
votes
0answers
154 views

Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If ...
7
votes
0answers
183 views

Number of ways to express a binary number in a certain way

So I'm working on a problem where I get to a point where I have to count the number of solutions to an equation or at least find a decent upper bound to be used in an estimate I need later. The ...
7
votes
0answers
43 views

Need a feedback on my solution (logic) of the combinatorial problem which involves ordinary deck of cards

So, here is the problem: An ordinary deck of 52 playing cards is randomly divided into 4 piles of 13 cards each. Compute the probability that each pile has exactly 1 ace. My solution: $$\frac { {4 ...
7
votes
0answers
155 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, ...
7
votes
0answers
141 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 ...
7
votes
0answers
109 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. ...
7
votes
0answers
170 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 ...
7
votes
0answers
175 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 ...
7
votes
0answers
194 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
142 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 = ...
7
votes
0answers
207 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 ...
7
votes
0answers
435 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 ...
7
votes
0answers
165 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
163 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)$ ...
7
votes
0answers
257 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
235 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
342 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
69 views

A bound on the nth prime.

Is there any combinatorial argument to show that the nth prime $p_n = \mathcal{O}(n^k)$ for fixed $k$ ? There is a problem in the book by Apostol to find upper bounds on $p_n$, the Prime Number ...
6
votes
0answers
55 views

Arrange Relatively Prime Numbers in a Circle

The question: In how many ways can you arrange the numbers $1$ to $8$ in a circle so that neighboring numbers are relatively prime? Can you generalize for $1$ to $n$? It's fairly easy to list ...
6
votes
0answers
100 views

Partial sums of falling factorials

I want to know if there exists some way, approximate or exact, to do a partial sum of falling factorials of the kind: $$\sum_{k=i}^{n}(a+k)_{h}$$ where all are constants. And I'm interested too in ...
6
votes
0answers
92 views

How many ways are there to fill up a $2n \times 2n$ matrix with $1, -1$?

How many ways are there to fill up a $2n \times 2n$ matrix with $1, -1$ so that each column and each row has exactly $n $ $1$'s and $n$ $-1$'s ? I tried for cases $n=1 , 2$ but the solutions were ...