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)

4
votes
0answers
64 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
146 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
25 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
75 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
80 views

Generating Function for Associated Stirling Numbers $b(n,k)$

I am trying to identify or find the ordinary generating function (not the exponential generating function) for the Associated Stirling numbers of the Second kind, denoted $$b(1;n,k)=b(n,k)$$ These ...
4
votes
0answers
91 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
45 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
47 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
45 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
129 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
328 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
74 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
88 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
107 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
56 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
110 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
103 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
83 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
65 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
86 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
353 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 ...
4
votes
0answers
85 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
73 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
99 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$. ...
4
votes
0answers
90 views

Sign of some permutation.

I trying to find the sign of this permutation: $\left(\begin{array}{cccccccccc} 1 & 2 & 3 & \cdots & \cdots & \cdots & \cdots & \cdots & n-1 & n\\ 2 & 4 & ...
4
votes
0answers
165 views

What is known about this jigsaw combinatorics problem?

The problem: How many valid reconfigurations, as defined below, are there for a given puzzle? My question is, what, if anything, is known about this problem already? For example, does this ...
4
votes
0answers
125 views

Card game probability

Suppose the following solitaire with a standard deck. I turn four cards visible on the board and on each turn, I remove those suits that appears more than once in the board. Then I fill the board such ...
4
votes
0answers
159 views

The close form expression of a Pfaffian

Recall Schur's Pfaffian identity: $$ \mathrm{Pf}\left(\frac{x_j-x_i}{x_j+x_i}\right)_{1\le i,j\le 2n} = \prod_{1\le i<j \le 2n}\frac{x_j-x_i}{x_j+x_i}. $$ Here $x_1,x_2\cdots x_{2n}$ are $2n$ ...
4
votes
0answers
76 views

Selecting k numbers out of N sorted numbers to a minimize a condition/Formula

A sorted list of $\mathbf N$ numbers is given. $X_1$ $\le$ $X_2$ $\le$ $X_3$ $\le$ .... $\le$ $X_N$ Select $\mathbf K$ Numbers - $Y_1$ , $Y_2$ , $Y_3$ , ..... , $Y_K$ - Such that the following ...
4
votes
0answers
96 views

Simplifying a sum?

Define polynomials $P_{j,s}^{(r)}$ via the generating series $$\left(\frac{d^s}{dz^s}f(z)\right)^r=\sum_{j=0}^{\infty} P_{j,s}^{(r)}z^j,$$ where $r\geq 1$. Here, $f(z)=z+a_2z^2+a_3z^3+\cdots.$ I was ...
4
votes
0answers
89 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). ...
4
votes
0answers
98 views

Extracting Taylor coefficients of a quotient

I was wondering if anybody has come across functions of the form $$\Phi_n(z):=\frac{f(z)^{n+1}}{zf'(z)-f(z)}\quad (n\geq 1).$$ Here, $$f(z)=\sum_{k=0}^{\infty} a_kz^k$$ is holomorphic on the open unit ...
4
votes
0answers
96 views

On Applications of the Murnagham Nakayama rule

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

What's the name for this unimodal sequence?

Let $a_0, a_1, \ldots, a_n$ be an increasing sequence of positive numbers, and consider the sequence $s_1,\ldots,s_n$, where $$ s_k \;=\; \frac{a_0+\cdots + a_k}{k}. $$ So $$ s_1 \;=\; a_0+a_1,\quad ...
4
votes
0answers
206 views

History of Hindman's Theorem

At this blogpost about Hindman's Theorem, I read the following lines: 'I love the odd history so allow me to digress... etc. ' This sentence made me curious to know what this history looks ...
4
votes
0answers
89 views

A combinatorial problem.

Let be $(X, \mathbb{A}, \mu)$ a measure space, a partition of $ X $ is a disjoint family $\xi=\{P_1,\ldots,P_k \}$ of measurable sets such tath $\bigcup P_i=X\pmod0).$ If $\xi=\{P_1,\ldots,P_k ...
4
votes
0answers
74 views

In Pursuit of a Broader Understanding of Complicated Binomial Coefficient Sums

$$\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{(n+k+1)!}$$ The above identity was posted once before by me, however, all results were obtained numerically exploring the identity rather than understanding ...
4
votes
0answers
85 views

Linear Independence Game

Suppose you have a set $X$ of vectors in $\mathbb{F}_2^n$, with $|X| \ge n+1$, and consider the following game. On their turn, each player (2 player game) chooses from $X$ one vector and sets it aside ...
4
votes
0answers
81 views

Sequences of Integers such that no one divides the product of two others.

I'm working on of a problem of Bollobas' Modern Graph Theory, but I can't seem to get the last part of the problem: Let $1<a_1<a_2< \cdots a_k \leq x$ be natural numbers. Suppose no $a_i$ ...
4
votes
0answers
149 views

Using Bernoulli distribution approximate the $q$-th moment

Let $x$ be vector in $R^n$. Let $\pi(⋅)$ be a permutation on the set $\{1,\ldots,n\}$ with a uniform distribution. Let $|m|\leq n, m \in Z$. Using Bernoulli (or maybe some other) distribution ...
4
votes
0answers
142 views

Function composition and Bell polynomials

Suppose that we have the Taylor expansions : $$f(x)=\sum_{n=1}^{\infty}\frac{a_{n}}{n!}x^{n}$$ $$g(x)=\sum_{n=1}^{\infty}\frac{b_{n}}{n!}x^{n}$$ Then we have the standard result : ...
4
votes
0answers
175 views

Efficiently count possible nim-like moves

Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, ...
4
votes
0answers
92 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 ...
4
votes
0answers
363 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 ...
4
votes
0answers
125 views

A general Combinatorics problem (Coefficients of the q factorial)

I was solving a combinatorics problem when I encountered difficulties. The problem was: $x_1 \in \{0,1\}$ $x_2 \in \{0,1,2\}$ . . $x_{n-1}\in\{0,1,2..,n-1\}$ We have to find the number of ways ...
4
votes
0answers
73 views

Expectation of Reciprocals Involving Permutations

Let $a_i$ be $n$ distinct real numbers. What is the expectation: $$\mathbb E_\sigma \left[ \sum_{i=1}^{n} \frac {1} {a_{\sigma(i)} - \sum_{j=1}^{i-1}a_{\sigma(j)}} \right] $$ where the expectation ...
4
votes
0answers
206 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.
4
votes
0answers
90 views

Optimal packing of number sets with limited overlap

When considering something completely different yesterday I came across the following problem: Let $X = \{ 1,2,3,...,n\}$. What is the maximal number of subsets of $X$ of order $m$ one can choose ...
4
votes
0answers
235 views

Generating function for product of binomial coefficients

In general, if $a(n)$ is an integer sequence with generating function $A(t)$ and $b(n)$ is an integer sequence with generating function $B(t)$, it is not easy to find the generating function $C(t)$ ...