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
274 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
96 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
70 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
197 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
76 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
183 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
59 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
166 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
281 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
210 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
174 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
56 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 bgins shows that for each $k$ there is a unique polynomial $P_k(x)$ of degree $k$ whose coefficients are in $\mathbb{Q}(q)$, the field of rational functions, such that ...
4
votes
0answers
67 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
206 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
189 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
633 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
89 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
109 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
29 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
16 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
19 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
36 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
50 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
65 views

derangements and permutations in cryptography

i have a problem that i am having a bit of trouble with; we are given a partial key (missing 11 letters) for a mono-alphabetic substitution cipher and asked to calculate the number of possible keys ...
3
votes
0answers
54 views

Order 5 People of team A, 5 People of team B and 5 People of team C in line

I want to calculate the probability that: each candidate stands next to at least one candidate from their group. At first I thought that subtract from $1$ the probability that each team stands ...
3
votes
0answers
46 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
41 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
69 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
34 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
43 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
36 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
46 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
86 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
29 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
219 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
198 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
43 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 ...
3
votes
0answers
110 views

How many ways can M identical objects be divided into N groups?

We have M indistinguishable objects and will divide them into N indistinguishable groups. How many ways can this be done? Many might believe that this is a Stars and Bars type question, but it is ...
3
votes
0answers
74 views

Recurrence $(n+2)\text{Cat}_{n+1}=(4n+2)\text{Cat}_n$ for non-crossing matchings

The number of non-crossing matchings of sides of $2n$-gon (i.e. the number of ways to connect sides pairwise by non-intersecting paths) is $n$’th Catalan number, $\text{Cat}_n$. How to prove ...
3
votes
0answers
51 views

Deducing that polynomials span

Let us say that we are dealing with a countable family of polynomials with real coefficients in $n$ indeterminates that commute. Are there any known/common nice systematic ways to tell if their span ...
3
votes
0answers
109 views

to find the graphs having vertices with same eccentricity

I was reading a paper http://www.discuss.wmie.uz.zgora.pl/php/discuss3.php?ip=&url=plik&nIdA=11134&sTyp=HTML&nIdSesji=-1 There is a formula to calculate eccentricity in the section ...
3
votes
0answers
50 views

How many elements are there in total?

Suppose that we have a collection of 12 sets, each of which has 8 elements. Every pair of sets shares 6 elements, any collection of 3 sets shares 4 elements, and no collection of 4 sets shares any ...
3
votes
0answers
88 views

Expectation of throws before having $k$ balls in each box

I remember that if there are $n$ boxes, and a ball is being thrown repeatedly into one of the boxes with uniform probability, then the expected number of throws before every box has a ball is ...
3
votes
0answers
129 views

Find specified sets of residues mod an even number

Let $k$ and $l$ be integers greater than $4$. I'm interested in set $S$ of $k$ elements in $\mathbb{Z}/2l\mathbb{Z}$ satisfying the following three conditions: (1) if $a\in S$, then $a+l\not\in S$; ...
3
votes
0answers
78 views

Counting number of distinct systems

This is an enumeration problem in conjonction with some lottery problems. Given an integer $N \ge 5$. Let a ticket be a set of 5 distinct integers between $1$ and $N$. Given an integer $T$ between ...
3
votes
0answers
132 views

Nth term of sequence

I have a sequence: 1,2,3,4,4,4,5,5,5,5,6,6,6,6,6,6,6,6,6,6,.............. I don't know how to use latex so my formatting might not be proper but in words ...
3
votes
0answers
133 views

Teams in tournament problem

I have a practical math problem that I can't solve by myself. The problem is probably already solved by other people but I can't think of any Google search words. If somebody knows a solution or is ...
3
votes
0answers
220 views

Dinner table problem: with multiple tables

Consider a party of $kn$ people and $k$ circular tables of size $n$. If they are seated randomly around the tables for two courses, what is the probability that no two people sit together at both ...