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
201 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?
5
votes
0answers
232 views

Puzzle - In how many pairings can 25 married couples dance when exactly 7 men dance with their own wives?

Each married couple as well as each dancing pair consists of a man and a woman. How many possible pairings are there? Here is the same question with a different amount of couples. I read the answers ...
5
votes
0answers
289 views

Formula for composition of formal power series with binomial coefficient

Let $f=\sum\limits_{n\geq 0}{f_n x^n}$ and $g=\sum\limits_{n\geq 1}{g_n x^n}$ be formal power series. The $x^n$ coefficient of $f(g)$ is $$ \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {f_k \,g_{i_1}\...
5
votes
0answers
70 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 $[A_1 , A_2, ..., A_n]$ (random order). We have a comparator $C$, but it has a probability $p$ to ...
5
votes
0answers
141 views

Chess Set Latin Square

Here is a very interesting question that my professor and I came up with today. We came up with it while discussing another problem, and I'm very curious to see how this pans out! Question: Suppose ...
5
votes
0answers
69 views

Max possible number of sets that have 1 and only 1 member in common

I have a set of 25 things that I want to group into sets of 6, with the following conditions: Every set shares one, and only one, member in common with every other set No object can appear twice in ...
5
votes
0answers
84 views

Possible squares that a chess piece can move to

Fix four integers $a,b,c,d$ with $\gcd(a,b)=\gcd(c,d)=1$ and with the condition that $abcd<0$ (this ensures that the two moves are of different sign slope). Suppose then we have a chess piece that ...
5
votes
0answers
100 views

number at the circumference

Determine all natural numbers $n$ such that the numbers $1,2,3, . . . ,n$ can be placed on the circumference of a circle, such that for any natural number $s$ with $1 \le s \le \frac{n(n+1)}{2}$ there ...
5
votes
0answers
148 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 S}f(...
5
votes
0answers
61 views

Degree distribution of a graph of integer partitions

Consider a graph whose nodes are the integer partitions of $n$, connected by an edge if you can get from one partition to the other by ‘sliding one square of its Young diagram’ – that is, if one ...
5
votes
0answers
65 views

Number of different rankings of $n$ people

Consider a ranking of $n$ people, possibly with ties. For example, if there are two people, the possibilities are $1>2$, $2>1$, and $1=2$. If there are three people, the possibilities are $1>...
5
votes
0answers
56 views

For the exponential operator $e^{f(x)\frac d{dx}}= \sum_{i=0}^\infty F_i(x) \frac{d^i}{dx^i}$, is there a formula for the $F_i$ in terms of $f$?

Consider the operator $$ e^{ f(x) \frac{d}{dx} } = \sum_{i = 0}^\infty \frac{1}{i!} \left(f \frac{d}{dx} \right)^i $$ If one commutes the derivatives with the powers of $ f $, then there are functions ...
5
votes
0answers
990 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 ...
5
votes
0answers
126 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
174 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
479 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
165 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
161 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
113 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
115 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
356 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 w^{(p_i-p_j)...
5
votes
0answers
136 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
120 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
234 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
228 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
80 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
109 views

Points at Integer Distances in 3-space

With the restriction no three points in a line, no four points on a circle, there is a 7 point configuration of points on the plane such that all pairs of points are at integer distances. [1] For 3-...
5
votes
0answers
524 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
266 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
238 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
368 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
247 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
171 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
107 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
60 views

How many subsets of $n$ linearly independent binary strings of length $n$?

Let's consider binary words of length $n$ with elements {-1,1}. There are $2^n$ binary words of length $n$. Now let's consider a subset of $n$ such binary words. All possible subsets are $\binom{2^n}{...
4
votes
0answers
104 views

Number of ways to arrange $n$ numbers based on their relative values to each other

EDIT I've found a formula to solve this question, but I don't understand the reasoning behind it. Can someone explain this formula? $s(n - 1, x + y - 2) \times C(x + y - 2, x - 1)$ $s$ being ...
4
votes
0answers
45 views

Proof verification: Mantel's theorem

if a graph $G=(V,E)$ on $n$ vertices contains no triangles than it contains at most $n^2/4$ edges. Proof: Let v$\in$V be a vertex of maximum degree k. since G contains no triangles, there are no ...
4
votes
0answers
38 views

Optimal strategy in an idealized dating scenario

The question I have is in some ways a variation on the stable marriage problem adapted to the situation of dating. Suppose there are $n$ boys and $n$ girls, where every boy ranks the girls from $1$ ...
4
votes
0answers
58 views

Minimum number of points chosen from an N by N grid to guarantee a rectangle?

What is the maximum number of points that can be chosen from an $N$ by $N$ grid such that no $4$ of the chosen points form a rectangle with sides parallel to the axes of the grid? Equivalently, what ...
4
votes
0answers
69 views

Expected length of longest arithmetic sequence

Given a natural number $n$, we define the vector valued random variable $\vec Y_n := (X_1, \ldots X_n)$ where all $X_i$ are independently uniformely distributed on $S_n := \{1, \ldots, n\}$. Further ...
4
votes
0answers
49 views

Find the number of 4 digit numbers of the form $abcd$ such that $ab+cd$ is even

Let $n$ denote the number of 4 digit numbers of the form $abcd$ such that $ab+cd$ is even. Find the last digit of $n$. There are two cases. $ab,cd$ is odd. Which means $a,b,c,d \in \text{odd}$. ...
4
votes
0answers
53 views

Birthday problem: why is this solution wrong?

This question is about the birthday problem: the probability that in a group of n people, at least two of them have the same birthday (https://en.wikipedia.org/wiki/Birthday_problem). An easy way to ...
4
votes
0answers
65 views

Central limit theorem for perfect matching counts

Set $N_G$ the number of copies of graph $G$ in the Erdős–Rényi random graph model $G(n,p)$. We have the law of large number for the number of copies of of graph $G$ i.e. $N_G$ is very close to the ...
4
votes
0answers
97 views

Probability of having at least $j$ collisions when tossing $m$ balls into $n$ bins

Suppose that we throw $m$ balls into $n$ bins uniformly and independantly at random. We consider collisions as distinct unordered pairs, e.g., if 3 balls are tossed in one bin, we count 3 collisions. ...
4
votes
0answers
76 views

Can this sum over the q-Pochhammer symbol be simplified?

While considering the problem of the expected value of a dice fixing strategy on a two-sided die that comes up as $1$ with a probability of $\alpha$ and $0$ otherwise. I was studying the strategy ...
4
votes
0answers
58 views

Bijective mapping between face polytopes of permutohedra and partitions of integers

The OEIS entries A019538, A049019, and A133314, relate a refinement of the face polynomials of the permutohedra (A049019) to partition polynomials (A133314) defined by multiplicative inversion of an ...
4
votes
0answers
42 views

Concatenation of strings is not in the set

A set $M$ contains some strings of $0$s and $1$s of length no more than $n$, in a way that if $a,b\in M$ (possibly $a=b$), then their concatenation $ab$ doesn't belong to $M$. What is the maximum size ...