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. Combinatorics is a ...

learn more… | top users | synonyms (4)

4
votes
0answers
46 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
106 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
101 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
73 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
63 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
330 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
82 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
68 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
93 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
85 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
160 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
48 views

The largest regular m-gon that fits inside a regular n-gon

This question just popped into my head while doing some "for fun" math. More precisely: Let $m,n\in\Bbb{Z};m,n>2$. Let $P$ be a regular $n$-gon (let's say $P$ is the convex hull of the $n$ $n$th ...
4
votes
0answers
121 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
145 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
75 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
95 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
85 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
95 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
243 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 ...
4
votes
0answers
69 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
88 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
68 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
82 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
80 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
139 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
167 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
91 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
344 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
120 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
205 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
87 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
216 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)$ ...
4
votes
0answers
65 views

What impedances can be generated from combination of impedances?

There was a problem which asked to connect some resistors in some order(parallel and series) to achieve an equivalent resistor with a specified ohms. I solved that problem but I think we can argue ...
4
votes
0answers
195 views

What is the exponential generating function of the inverse matrix of an integer triangle?

Let ${Z}$ denote an integer triangle (like Pascal's), ${Z}_{n,k}$ for $0\leq k \leq n$ and let $f$ be an exponential generating function for polynomials $p_{n}(x)$ with $[x^k]p_{n}(x)= Z_{n,k}$. ...
4
votes
0answers
329 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 ...
4
votes
0answers
258 views

Combinatorics and graph theory - counting connected graphs

We denote by $C(n,n+k)$ the number of connected graphs on $n$ vertices with $n+k$ edges. I have 2 problems I wish to prove, but after much effort have gotten nowhere with. I would greatly value some ...
4
votes
0answers
190 views

Simplifying an expression involving binomial coefficients

Consider $$ \prod_{j=0}^{i-1}\binom{n-2j}{2}\left[1+\sum_{k=0}^{N-1}{\left( \prod_{l=0}^{k} \dfrac{N-l}{M-l}\right)\left(1 + \sum_{m=k+1}^{N-1} \prod_{p=k+1}^m \dfrac{N-p}{M-p}\right)+1}\right] $$ ...
4
votes
0answers
60 views

Necessary and sufficient condition for $f(q^n)$ to be in $\mathbb{Z}[q,q^{-1}]$ when $f\in\mathbb{Q}(q)[x]$?

In this question, user begins shows that, for each $k\in \mathbb{N}$, there is a unique polynomial $P_k(x)$ of degree $k$ whose coefficients are in $\mathbb{Q}(q)$, the field of rational functions, ...
4
votes
0answers
69 views

About $t$-analogue of the Euler polynomials.

A certain way to define the $t$-analogue of the Euler polynomials $C_n(x)$ is by $$ C_n(x,t)=\sum_{\pi\in S_n}x^{\text{des}(\pi)+1}t^{\text{maj}(\pi)} $$ where $des(\pi)$ is the descents in $\pi$, ...
4
votes
0answers
225 views

How fast does $\binom{n}{k}$ grow when $k \le n/2$?

How fast does $\binom{n}{k}$, $n$ fixed, grow when $k \le n/2$? Especially, I'm interested in the growth of the "inverse" of binomial coefficient $B_n(x) := \min \{k:\binom{n}{k} \ge x\}$. EDIT: ...
4
votes
0answers
234 views

Transversal of a family of sets

What I want to prove is: Let $U=(A_1\ldots,A_n)$ be a family of sets and let $P\subseteq A_1\cup \cdots \cup A_n$. Then $U$ has a transversal which includes the set $P$ if and only if (i) $U$ has ...
4
votes
0answers
693 views

Project Euler Problem 338

I'm stuck on Project Euler problem 338. This is a cross post from StackOverflow where I initially posted, however, it was suggested that I post it here too since the problem mostly relies on math. The ...
4
votes
0answers
95 views

Identify this combinatorial construction

I am no combinateur, but I stumbled across the following construction when studying an operad arising from information theory (actually it's a special algebra of an A$_\infty$-operad). It looked ...
4
votes
0answers
117 views

Are almost all rooted trees asymmetric?

It's well known that almost all graphs are asymmetric (have trivial automorphism group) and that almost all free trees are symmetric. By which argument do I see whether almost all rooted trees are ...
3
votes
0answers
21 views

How many expressions can be formed with two commutative and associative functions?

Suppose we have two binary functions $f,g$ which are commutative and associative, i.e., satisfying $$ f(a,b) = f(b,a) \qquad g(a,b) = g(b,a)$$ $$ f(a,f(b,c)) = f(f(a,b),c) \qquad g(a,g(b,c)) = ...
3
votes
0answers
52 views

Combinatorics project ideas for high school students

It's that time again! Last year I asked for high school project ideas in the area of algebraic geometry, this year it's combinatorics (you can include graph theory and combinatorial game theory if you ...
3
votes
0answers
105 views

Simplification of recursive polynomials

Suppose I have known polynomials $p_i, i=0\ldots k-1$. I have the following horrific looking recursive equation: ...
3
votes
0answers
35 views

Number of Lattice Paths from $(0,0) to (n,n)$ without going over $y=x$

This is a question that was asked at the start of the section on Catalan Numbers in my book. I'm having trouble answering it. My Work All of the legal paths (ones which do not cross over $y=x$) must ...