This tag is for basic 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
200 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
82 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
199 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
62 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
179 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
306 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
221 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
1k views

Optimal Resolvable Steiner Quintuple System covering with circles and ellipses

Here is a resolvable Steiner quintuple system. Every tuple from 1-25 appears in exactly one of the sets. {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}, ...
4
votes
0answers
178 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
58 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
68 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
212 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
202 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
649 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
92 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
112 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
27 views

Does there exist Latin square critical sets for which deleting any entry results in arbitrarily many completions?

For those familiar with Latin squares terminology, I'll get straight to the point: Q: For all $N \geq 2$, does there exists a critical set $C$ (for a Latin square of any finite order) such that ...
3
votes
0answers
131 views

Derangement bijection

This is a generalization of this question. An $(n,k)$ partial permutation is an injection from $[k]$ to $[n]$. It can be thought of as word of length $k$ in symbols in $[n]$ without duplications. ...
3
votes
0answers
49 views

Conjectured Value of Ramsey Number $R(3,10)$

It is known that the value of the Ramsey number $R(3,10)$ is either 40, 41, or 42. Have any experts in the field offered a conjecture as to which it might be?
3
votes
0answers
71 views

Combinatorical interpretation of $\binom{15}{5} = \binom{14}{6}$

I was reading up on Sigmaster's conjecture on repeated binomial coefficiencts and I read that $$\binom{15}{5} = \binom{14}{6}$$ Sure, it's possible to prove it non-combinatorically: ...
3
votes
0answers
39 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 ...
3
votes
0answers
48 views

What is the number of labeled caterpillars?

A caterpillar is a tree in which all the vertices are within a distance 1 of a central path. (See the Wikipedia article: Caterpillar tree, for an example and some equivalent characterizations). The ...
3
votes
0answers
52 views

number of Lattice paths from origin to diagonal after removing vertices

i am stuck with the following problem: consider the quarter plane $\mathbb{N}_0^2$ with vertices $(i,j)\in\mathbb{N}_0^d$ and edges from each vertex $(i,j)$ to $(i+1,j)$ and $(i,j+1)$, i.e. one ...
3
votes
0answers
58 views

A function on sets which is constant for all permutations

Let $U=\{1, 2,\ldots, 2014\}$. For positive integers $a$, $b$, $c$ we denote by $f(a, b, c)$ the number of ordered 6-tuples of sets $(X_1,X_2,X_3,Y_1,Y_2,Y_3)$ satisfying the following conditions: ...
3
votes
0answers
82 views

Random $0-1$ matrices

I'm working my way through the Oxford notes in Probabilistic Combinatorics and came across this question in one of the question sheets; I'd like to stress that this is not my homework: I'm simply ...
3
votes
0answers
102 views

History of a combinatoric problem: exchanging numbers by throwing stones

Another user recently asked a question on the Puzzling stack: Two spies throwing stones into a river. Suitably generalised, it becomes: Two spies (Alice and Bob) need to exchange a message. Each ...
3
votes
0answers
90 views

Happily Married

Let $B$ be a set of boys (possibly infinite). Each boy $b∈B$ knows a finite set of girls $G_b$. We want to marry each boy with some girl (legally: thus no girl can be married with more than one boy). ...
3
votes
0answers
89 views

Sum of product partitions of divisors

Let $M(n)$ be the the set of the multiplicative partitions of $n$, and let $D(n)$ be the set of the sum of the multiplicative partitions of the divisors of $n$. eg $M(30)=\{\{30\},\{2,15\},\{3, ...
3
votes
0answers
107 views

Proving $\sum_{k=1}^{n}\binom{n-1}{k-1}{\binom{n+k}{k}}^{-1}=\frac 12$ combinatorially

Question : How can we prove the following equations combinatorially? $$\begin{eqnarray}\sum_{k=1}^{n}\frac{\binom{n-1}{k-1}}{\binom{n+k}{k}}&=&\frac ...
3
votes
0answers
76 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 ...
3
votes
0answers
34 views

A question on combinations of a set of numbers

I have the set of the first $n$ primes $\{2,3,5,\ldots,p_n\}$. There are $n^n$ ways of selecting $n$ numbers from this set. Each combination has a number ($C_k$) associated with it and it is the ...
3
votes
0answers
21 views

4-net in binary hypercube

Consider a binary hypercube $\mathbb{F}_2^n$. What is the largest size of a subset $S$ such that $d(x,y)\geq 4$ for all $x,y\in S$ ($x\neq y$), where $d(x,y)$ is the Hamming distance between $x$ and ...
3
votes
0answers
24 views

(Counting problem) more challenging Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help - Part II after Part I: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ x_1 y_2 = x_2 y_1 \pmod N \qquad (1) \\ ...
3
votes
0answers
40 views

Division of space by balls in R^n

I would like to know the generalized proof of this result: http://mathworld.wolfram.com/SpaceDivisionbySpheres.html, for $n$ dimensions. What is the maximum number of regions divided by $q$ ...
3
votes
0answers
73 views

Given a number of items, how many sets of three are there where no two sets are two thirds similar?

Sorry if the title isn't proper math-talk. Hopefully I can explain it better here. So let's say we have a set. 1, 2, 3, 4, 5, 6, 7, 8, 9. I want to know how many groups of three can be made where no ...
3
votes
0answers
52 views

Proving the inclusion exclusion principle from the definition of the cardinality

I want to prove the inclusion exclusion principle: $|A\cup B| = |A| + |B| - |A\cap B|$ where $A$ and $B$ are finite sets. I proved the addition rule by contructing a bijection to a subset of ...
3
votes
0answers
56 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 ...
3
votes
0answers
77 views

Combinatorial Proofs of Two Identities

I need a combinatorial proof for these two identites: (a) $\sum_{k=0}^{n} \binom{n}{k}^2 x^k = \sum_{k=0}^{n} \binom{n}{k} \binom{2n-k}{n} (x-1)^k$ (b) $\binom{n}{k} ^2 = \sum_{l=0}^{n-k} (-1)^l ...
3
votes
0answers
37 views

C0mbinatorics: Minimum number of node transitions

For n nodes, labeled 1,2...,n, a total of x nodes can be on at a time. Each node must "visit" each of the other nodes, and a node can only visit another node when both are on. Each time nodes are ...
3
votes
0answers
48 views

How prove this there exsit set $B$ such $card(B)>\dfrac{n}{3}$,

Question: Let $a_{i}\in N^{+}$, and the set $A=\{a_{1},a_{2},\cdots,a_{n}\}$, show that: There exists a set $B\subset A$, such that $card(B)>\dfrac{n}{3}$, and that for any $x,y\in B$, ...
3
votes
0answers
41 views

Verification of a Combinatorial Identity

I have a challenge for you combinatorial mathematicians. Is anyone willing to verify the following combinatorial identity? ...
3
votes
0answers
50 views

News on SG values of Grundy's Game?

Is there any recent research into the Sprague-Grundy values of Grundy's game? It was calculated to $2^{35}$ integers but with no sight of recurrence. Has anyone come up with anything new to compute ...
3
votes
0answers
60 views

How to calculate the number of automorphisms of this set.

Let $N = \{1,2,\dots,n\}$ and define the set of functions $$X = \{ f:N \longrightarrow N : f(i) \leq i\}$$ Similarly let $S_n$ (the usual symmetric group on $n$ elements) act on $N$ by permuting ...
3
votes
0answers
61 views

Number of 'unique' one bit binary functions with N-bit inputs

Consider the set of binary functions that takes an N-bit input -> 1 bit output. There are 2^(2^N) elements in this set. Now potentially reduce this set by restricting to only considering functions ...
3
votes
0answers
108 views

Circular permutations - $n$ sitting at a round table without repeating neighbors

I hope this isn't a duplicate - the problem is to find the number of ways of sitting $n$ people (who initially were sitting in the order $1, 2, \dots,n$, with $1$ and $n$ being neighbors) at a round ...
3
votes
0answers
31 views

On two-colorings of the plane

Suppose that we have colored any point in the plane with two colors and let $n\geq 3$ be given. I want to show that there are $n$ points such that together with their centroid all have the same ...
3
votes
0answers
270 views

Showing equivalency between vertex disjoint and edge disjoint path problems in undirected graphs

First, here are the definitions I am working with: Given an undirected graph $G = (V,E)$ and vertices $s, t \in V$ we wish to either find the number of vertex disjoint paths from $s$ to $t$ or to find ...
3
votes
0answers
199 views

special combinatorial sums

I know several of combinatorial sums, which is equal to 0. For example, $$ \sum_{0 \leq j \leq d} (-1)^j {d \choose j}=0$$ $$ \sum_{0 \leq j \leq \frac{d}{2}} (-1)^j {d \choose j}(d-2j)^\alpha=0, \, ...
3
votes
0answers
60 views

Probability/selection problem

Assume that we have $N$ items of $M$ distinct types in a closed bag. We also have $K$ bowls $(K \leq M)$ that can hold only items of same type. In the beginning bowls are empty. And bowls can hold a ...
3
votes
0answers
55 views

Asymptotics of partitions in at most n parts, bounded by r

For every positive integers $n,r,w$ define $$ p_w(n,r)=\#\{ (i_1,...,i_r) | \, 0\leq i_1 \leq \dots \leq i_r\leq n, \, i_1+\dots+i_r=w\} $$ as the number of partitions of $w$ in at most $r$ piece ...