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
27 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
37 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
87 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
50 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
45 views

Has this subset-sum game been studied?

Consider the following game: two players, Yolanda (who always goes first) and Zachary, take turns selecting (not yet chosen) numbers between $1$ and $9$. The first player who can make three of their ...
4
votes
0answers
69 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
98 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
51 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
75 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
150 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
26 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
82 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
83 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
92 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
53 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
46 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
135 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
397 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
75 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
89 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
108 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
59 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
112 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
88 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
67 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
89 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
365 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
87 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
76 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
101 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
91 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
166 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
130 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
167 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
99 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
97 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
208 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
90 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
86 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
82 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
144 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 : ...