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)

5
votes
0answers
224 views

Closed form expression for constants

We have the constants $c_{k,n}$ defined by : $$c_{k,n}=\frac{d^{k}}{ds^{k}}\left(\frac{e^{\frac{1}{n(ns-1)}}e^{\psi\left(\frac{s-1}{s} \right )}}{s} \right )$$ Where $\psi(s)\;$ is the Digamma ...
5
votes
0answers
67 views

Erdos Ko Rado for hypergraphs of bounded degree?

The Erdos-Ko-Rado theorem states that if $H$ is a $k$-uniform hypergraph on $[n]$ which is intersecting, then $|H| \leqslant \binom{n-1}{k-1}$. The easy example which shows this is tight is just take ...
5
votes
0answers
396 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 ...
5
votes
0answers
224 views

There are $n$ horses. At a time only $k$ horse can run in the single race. How many minimum races are required to find the top $m$ fastest horses?

There are $n$ horses. At a time only $k$ horses can run in the single race. How many minimum races are required to find the top $m$ fastest horses? Please explain your answer. PS: There is no timer.
5
votes
0answers
126 views

divisibility by powers of $2$ of diagonal sums of infinite latin square

This array is formed by placing integers such that each is the smallest such that the rectangle with it and the top left hand corner as opposite corners does not contain the same integer twice in any ...
5
votes
0answers
140 views

$k$-covering of the set of all possible n-length words

Give an alphabet $\mathcal{A}=\{a_1,a_2,\ldots,a_m\}$, and let $L_n$ is the set of all possible $n$-length words in form $[a_{i_1}a_{i_2}a_{i_3}\ldots a_{i_n}],\ a_{i_j}\in \mathcal{A}$. We call a ...
5
votes
0answers
335 views

A product puzzle

This is from a math contest. I have solved it, but I'm posting it on here because I think that it would be a good challange problem for precalculus courses. Also, it's kind of fun. Write the ...
5
votes
0answers
236 views

Combinatorics question in the style of Van der Waerden's theorem

I would really appreciate some help with the following problem. It resembles Van der Waerden a lot but I don't know how to proceed. I was told an averaging argument might do the trick but I can't see ...
5
votes
0answers
167 views

Points and lines covering them

Let $n$ be a positive integer. A subset $S$ of points in plane satisfies the following conditions: a) We can't find $n$ lines in plane, such that every element of $S$ belongs to at least one of these ...
5
votes
0answers
102 views

Minimum Universe size in set system with constraints.

Suppose we have a collection on sets $\{S_1, \ldots, S_n\}$ and where each set $S_i \subset \{0, \ldots, u-1\}$ and has $\left| S_i \right| = k$. Also, given a fixed $m \le \frac{n}{2}$, we also ...
4
votes
0answers
45 views

Terminology in graph theory

Let $G$ be a finite graph with the following property: For any vertex $a$ and edge $\{b, c\}$ of $G$, there is an edge connecting them: there is one of $\{a,b\}$ or $\{a, c\}$ in $G$. Is there ...
4
votes
0answers
33 views

How many ways I can put $k$ bishops on $n\times n$ chessboard?

Is there a formula how to count in how many ways I can put $k$ bishops on $n\times n$ chessboard such that no two bishops threaten each other?
4
votes
0answers
28 views

Proving that the intersection of two closed sets is closed in a matroid

I am stuck on a little homework problem I have. Here, $M$ is a matroid with rank function $R$. I am given this definition: In a matroid $M$, a set $A$ is closed if $R(A \cup e) > R(A)$ for all $e ...
4
votes
0answers
68 views

About two combinatorial counting problems.

Here are the problems: Suppose $X$ is a set of $n$ elements, and $S_1,...,S_m$ are $m$ subsets of $X$ of average size at least $n/w$. Show that if $m\geq 2kw^k$, then there are $k$ distinct ...
4
votes
0answers
123 views

Is there a closed-form expression for Shapley value of glove game?

Suppose we have a coalition game with transferable utilities, with $m$ players having a right-handed glove and $n$ players having a left-handed glove. The value of a coalition is equal to the number ...
4
votes
0answers
121 views

How to solve this multiple summation?

How to solve this summation ? $$\sum_{0\le x_1\le x_2...\le x_n \le n}^{}\binom{k+x_1-1}{x_1}\binom{k+x_2-1}{x_2}...\binom{k+x_n-1}{x_n}$$ where $k$ , $n$ are known. Due to hockey-stick identity , ...
4
votes
0answers
68 views

All possible total orderings of a finite set are isomorphic. What are some other examples of this phenomenon?

All possible total orderings of a finite set are isomorphic. I find these kinds of results remarkable. Here's a few more. Assume that $S$ is a finite set. Then: All possible field structures on $S$ ...
4
votes
0answers
34 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has n different elements [A1 .. A2 .... An](random order). We have a comparator C, but it has a probability p to return correct ...
4
votes
0answers
152 views

Probability of turning a 3x3 Rubik's Cube 50 random turns and solving

So I am working with my secondary Algebra II class on permutations, combinations, and probability and had an idea for an interesting problem that I hope can work for their skill level. We have been ...
4
votes
0answers
30 views

Computer realisation of automorphism group of polyhedron

I have a polyhedron (I am especially interested in the case of Platonic solids) and the graph corresponding to its skeleton. I also have some data associated with this graph (e.g. different ...
4
votes
0answers
40 views

Combinatorics and Probability- where am I wrong?

Let there be a cube with $n$ sides denoted $1,...,n$ each. The cube is tossed $n+1$ times. For $1\le k\le n$, what is the probability that exactly $k$ first tosses give different number (i.e, the ...
4
votes
0answers
89 views

What is the name for planar curve that intersect with every line at most $2k$ time

More exactly I want to know is there research in planar (closed) curve (there maybe nodes as singularities) s.t. every line in general position would intersect it at no more than $2k$ times. $k=1$ is ...
4
votes
0answers
51 views

Integrals of orthogonal polynomials and combinatorics

A beautiful result due to Evans and Gillis is that the function $$A(n_1,n_2,\cdots,n_r)=\int_0^\infty L_{n_1}(x)L_{n_2}(x)\cdots L_{n_r}(x)e^{-x}dx$$ counts the number of generalized derangements ...
4
votes
0answers
80 views

The annihilator numbers of $S/I$

Let $S=K[x_{1},x_{2},...,x_{n}]$ and $I$ be a strongly stable ideal of $S$. Compute the annihilator numbers of $S/I$ with respect to the almost regular sequence $x_{n},x_{n-1},...,x_{1}$. ...
4
votes
0answers
56 views

Can the principle of inclusion/exclusion be used to count elements in the intersection of a sequence of sets?

The principle of inclusion-exclusion (PIE) is often used to count the number of elements in a union of $n$ sets in terms of an alternating sum of their various intersections: $$ \left |\bigcup_{i \in ...
4
votes
0answers
100 views

Sum over subsets of a multiset

I have a sum that looks like the following for some multiset $S$ and some function $f$ of $n$ variables which does not depend on the ordering of its arguments: $$\sum_{\{k_1,\dots, k_n\}\subset ...
4
votes
0answers
55 views

Way to compute Stirling numbers of the second kind from a multiset

I was wondering what algorithm would compute S(n, k {occurences of each element}) Where S(6, 3, {1, 2, 3} ) would give ...
4
votes
0answers
79 views

Edges of a permutohedron

Consider a permutohedron $P_n$ (this is a polytope which is a convex hull of $n!$ points, which are obtained from $(1,2,...,n)$ by all possible permutations of coordinates). I have to prove the ...
4
votes
0answers
160 views

6-digit password - a special decoding method

Consider the situation of decoding a 6-digit password that consists of the symbols A to Z and 0 to 9, where all possible combinations are tried randomly and uniformly. Consider the ...
4
votes
0answers
28 views

How to number the natural numbers lexicographically with minimal overhead (and provide a lower bound for the overhead)?

Working in binary, note that the number 100 is lexicographically smaller than the number 11 even though $100 > 11$. How can we devise a function $f$ such that $f(a)$ is lexicographically smaller ...
4
votes
0answers
88 views

How to visualise Bollobas' 1965 theorem?

Theorem $[n]=\{1,\ldots,n\}$. Let $\lbrace (R_i, S_i), i \in I \rbrace, R_i, S_i \subset [n]$ be such that $R_i \cap S_i = \emptyset, R_i \cap S_j \ne \emptyset (i \ne j)$. Then $$\sum_{i \in I} ...
4
votes
0answers
94 views

Can -9 to 9 be placed in 41 lines of zero?

The cubic curve $2x^3-4x^2y+2xy^2-8x+y^3-y$ can be used to get lattice points allowing the placement of the numbers $-8$ to $8$ so that all 32 triplets that sum to 0 will be a straight line of three. ...
4
votes
0answers
49 views

Probabilistic counting inequality

I am reading a proof involving the existence of a property in a tournament (a directed complete graph). To make the proof work, we need to have $n^ke^{-n/2^k}<1$. Here $n$ is the order of the ...
4
votes
0answers
56 views

On a problem of sphere-packing for Reed-Solomon codes

Suppose we have an $[n, k+1, n-k]$ Reed Solomon code $\mathcal C$ over $\mathbb F_q$, where $n-k=d$ is the minimum distance, and suppose that $d=2t+1$. We know that for every $r \in \mathbb F_q^n$ the ...
4
votes
0answers
49 views

placing chess knights in a numbered chessboard.

Suppose you have a square board where the number on the square in column $i$ and row $j$ is $(j-1)8+i$ you have to place knights on the board so no two knights threaten each other and the sum of the ...
4
votes
0answers
152 views

Generating functions to solve number of integer solution problem

If I have $x_1 + x_2 + x_3 =10$ with $1\leq x_1 \leq 5, \; 2 \leq x_2 \leq 6, \;3 \leq x_3 \leq 9$ I know that I compute $(t^1+\dots + t^5)(t^2 +\dots + t^6)(t^3+\dots +t^9)$ and look at the ...
4
votes
0answers
505 views

Clash of Clans Permutations

I'm not an expert mathematician (I'm 16) and I'm Italian, so please try to understand my question and forgive my poor language. Thank you. When I play Clash of Clans, I ask me "How many buildings ...
4
votes
0answers
49 views

an elementary problem on wreath product groups with combinatorial flavor

Embarrassingly, I got stuck in solving the following elementary exercise. Let $G=H\wr \Gamma$ be a wreath product groups, $H,\Gamma$ are countable discrete groups, when $\xi\in\oplus_{\Gamma}H$, then ...
4
votes
0answers
76 views

Combinatorics and symmetric functions

(The actual questions in this posting are at the bottom.) Occasionally someone asks here how to show that every nonempty finite set has just as many subsets of odd cardinality as of even cardinality ...
4
votes
0answers
100 views

${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r},$$ which can be proved combinatorically whether one particular element (among the $n$) ...
4
votes
0answers
109 views

A problem on 0-1 matrices.

Given a 0-1 matrix $A$, is there an efficient way to find all 0-1 vectors $x$ such that $Ax = v$ where the entries of $v$ belong to a set $\{a,b\} \subseteq \mathbb{Z}$ of size $2$? Note that $v$ is ...
4
votes
0answers
64 views

Derangements and the “other” secretary problem

I just found out that the name "Secretary problem" is given to two different problems. The first one talks about a secretary who mixes letters and envelopes, and ask for the probability that no letter ...
4
votes
0answers
113 views

Combinatorial packages of N items [[How many distinct Boolean Expressions can be made using N variables]]

Using just the AND operator, the number of distinct packages that can be built from a set of size $n$, is simply $2^n$. If one adds the operators OR and XOR, how many packages can be built? That is, ...
4
votes
0answers
105 views

Multiplicative subgroup of a finite field with prescribed trace.

Any suggestions/methods/estimates for the following problem would be very appreciated. $l,p$ are primes with $p \equiv 1 \!\! \pmod l$. $r$ is a positive integer with $r \equiv 1 \!\! \pmod p$ and $q ...
4
votes
0answers
101 views

Is there a way to figure out the minimum number of participants or maximum number of rounds in my tournament style?

I just finished hosting a Euchre tournament at work that was meant to get people to meet other people in the company. This is the third time I've hosted this type of tournament. The first two times, ...
4
votes
0answers
68 views

Unique representation of a degenerate simplex

I recently learned about simplicial sets, and now I'm studying some basic properties. I've learned that every degenerate simplex is a degeneracy of a unique non-degenerate (nice) simplex. However, I ...
4
votes
0answers
93 views

About derangement problems

Two derangement problems are really confusing me a lot. Please help me. First Problem There are n people in the room and they are sitting on a round table. All of them went out the room and ...
4
votes
0answers
92 views

What do combinations of non-integers actually represent?

I understand that a combination is a way of selecting a finite number of things out of a larger group, in which the order of elements do not matter. That is all fine. But, in my Mathematical Reasoning ...
4
votes
0answers
83 views

Tao's proof of Szemeredi-Trotter theorem on incidences

In Tao's proof of Szemeredi-Trotter theorem on Point-Line incidences , he uses a lemma which decomposes the real plane into cells. During the proof of this lemma, the final step of getting rid of the ...
4
votes
0answers
102 views

Graph composed of matchings and K_4

Let $G′ = (V, E_1 \cup E_2 \cup E_3)$ be a graph, where $E_1$ and $E_2$ are (nonempty) matchings and $E_3$ is the set of edges of a nonempty collection of pairwise vertex disjoint copies of $K_4$. ...