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
147 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, ...
5
votes
0answers
116 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 ...
5
votes
0answers
445 views

Counting simple quadrilaterals in a rectangular lattice.

I've been trying to make an algorithm to find the number of all possible simple quadrilaterals in a N*M lattice. I already have a brute force solution but since this is a Project Euler problem I ...
5
votes
0answers
149 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
140 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
112 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
103 views

Pairwise sums are equal

The distinct positive integers $a_1,a_2,...,a_n,b_1,b_2,...,b_n$ with $n\ge2$ have the property that the $\binom{n}2$ sums $a_i+a_j$ are the same as the $\binom{n}2$ sums $b_i+b_j$ (in some order). ...
5
votes
0answers
333 views

Which unordered partition of $n$ gives rise to the largest number of ordered partitions?

A quick look at the wikipedia article on partitions of $n \in \mathbb{N}$ shows that the number of ordered partitions is $2^{n-1}$, and the number of unordered partitions is asymptotically $ \sim ...
5
votes
0answers
181 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 ...
5
votes
0answers
125 views

On Applications of the Murnaghan-Nakayama rule

The question is located below. In short, I am looking for an accessible explanation of the Murnaghan-Nakayama rule in relation to the following problem. Pardon the long setup. Let $Y$ be a standard ...
5
votes
0answers
116 views

Nice puzzle: Creating a binary word using weights and scales

You are given $N$ weights where for each $i \in \{1,2,...,n\}$, the $i$-th weight weighs $i$ pounds. You are given an $N$-binary-word that's formed by $L$'s and $R$'s and scales. You need to provide ...
5
votes
0answers
205 views

number of potential couples

A potential couple is a pair of a man and a woman that like each other (assume that 'like' is a symmetric relation). Given a group of $M$ men and $W$ women, I want to know how many different ...
5
votes
0answers
227 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
74 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
494 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
259 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
128 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
193 views

Maximum size of a Sperner family containing a set of a given size

Given a set $A$ of $n$ elements and an positive integer $k\le n$, what is the size of the largest Sperner family $\mathcal{F}$ of subsets of $A$ such that $\mathcal{F}$ contains a set $B\subseteq A$ ...
5
votes
0answers
143 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
353 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
243 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
170 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
106 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
65 views

Dealing with a difficult sum of binomial coefficients, $\sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j} $

I am interested in finding an upper bound for the sum $$F(n)= \sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j}.$$ Ideally it should be possible to evaluate it exactly using some ...
4
votes
0answers
54 views

Proof of inequality involving binomial coefficients

Proving things is not my forte. Stumbled upon following identity: $$\binom{n+k+1}{k}>\sum_{i=1}^k \binom{\alpha_i}{i}$$ For $\alpha_i<\alpha_j $ for $i<j$ $0\leq \alpha_i \leq n+k$ Also ...
4
votes
0answers
72 views

Find the number of distinct throws which can be thrown with $n$ six faced normal dice which are indistinguishable among themselves.

Find the number of distinct throws which can be thrown with $n$ six faced normal dice which are indistinguishable among themselves. The total outcomes will be $6^n$. But this this has many cases ...
4
votes
0answers
69 views

Distribution of monochromatic edge counts in 2-colored square lattices

The question is how to compute in general the following: given integers $n$ and $k$, how many 2-colored $n \times n$ lattices have $k$ monochromatic edges. There are no diagonal edges. ...
4
votes
0answers
161 views

Combinatorics and trigonometry identity

Prove the following: $\displaystyle\prod_{n=1}^{180}\left(\cos{\left(\dfrac{n\pi}{180}\right)}+2\right)=\displaystyle\sum_{n=0}^{89}\binom{180}{2n+1}\left(\dfrac{3}{4}\right)^n$. We can state this ...
4
votes
0answers
59 views

Seeking more information regarding the function $\varphi(n) = \sum_{i=1}^n \left[\binom{n}{i} \prod_{j=1}^i(i-j+1)^{2^j}\right].$

Define a function $\varphi : \mathbb{N} \rightarrow \mathbb{N}$ as follows. $$\varphi(n) = \sum_{i=1}^n \left[\binom{n}{i} \prod_{j=1}^i(i-j+1)^{2^j}\right]$$ The motivation is that according to ...
4
votes
0answers
54 views

Room square construction (Howell design)

Using superimposed orthogonal Latin squares to construct a balanced tournament design, I get an n x n array of unique ordered pairs. If I only want unique unordered pairs, I can eliminate half of the ...
4
votes
0answers
85 views

Ramsey number $R(K_4,K_4,K_4)$.

I've done a bit of googling, but I can't seem to locate any bounds for $R(4,4,4)$. Here, $R(n_1,n_2,n_3)$ is the generalized Ramsey number where $n_1,n_2,n_3$ are orders of complete graphs. So, in ...
4
votes
0answers
49 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
127 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
39 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
82 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
147 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
85 views

Coefficients of (generating) function

If I have the generating function \begin{equation*} A(x)= \frac{1}{(1-x^{10})\cdot(1-x^5)\cdot(1-x) }\,, \end{equation*} what is a clean way to find the coefficients of $x^{n}$. This coefficient ...
4
votes
0answers
42 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
449 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
104 views

Multiplying three factorials with three binomials in polynomial identity

I have checked the following identity (1) below for $n\leq 40$ with a computer. Let $(n)_k$ denote the falling factorial $n(n-1)\ldots (n-k+1)$, let $Z_n=\sum_{k=0}^n (n)_k x^{n-k}$, and finally let ...
4
votes
0answers
32 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
41 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
92 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
70 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
68 views

Number of non-negative solutions to an equation - check my work

I tried to solve the following question and would love someone to check my work. Let $\displaystyle x_1,x_2,x_3,x_4$ $100$ digits long numbers where every digit is $1$ or $2$. Find the number ...
4
votes
0answers
85 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
69 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
73 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
95 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
77 views

The number of partitions by distinct positive numbers

Let $N>0$ be a natural number and let $P(N)$ denote the number of ways to write $N$ as a finite sum of $a_i$ such that the $a_i$ are strictly decreasing positive natural numbers. There is a paper ...