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)

0
votes
0answers
36 views

$M$ numbered balls (1 to $M$) drawn from urn (without replacement) - probability that at least one ball number matches its pick number

There is an urn with $M$ numbered balls ($1$ to $M$). All balls are drawn without replacement. Find the probability that at least one ball number matches its pick number. I tried to find the ...
2
votes
0answers
19 views

Find ordering of directed weighted graph maximizing sum of edges 'going up'

Consider the following problem. Given a weighted directed graph $G=(V,E)$ with $n = |V|$, find an ordering $\pi: \{1,...n\} \to V$ of the vertices that maximizes $$ \sum_{i<j} w_{\pi(i),\pi(j)}. $$ ...
4
votes
4answers
72 views

Proof of an equation involving Stirling numbers of the second kind

I found this equation involving Stirling numbers of the second kind on Math World: $$\sum\limits_{m=1}^n (-1)^m(m-1)!\,S(n,m)=0 \ .$$ However, I do not know why this is true. I am looking for a proof ...
2
votes
0answers
30 views

Generalization of Cauchy-Davenport inequality to $\mathbb Z_p^d$

Is there some generalization of Cauchy-Davenport inequality to the group $\mathbb Z_p^d$? ($p$ prime number, $d \ge 3$) For example, Kneser Theorem says that if $G$ is any abelian group and ...
3
votes
2answers
80 views

Finding all k-size subgraphs

I have no experience with advanced combinatorics, but I have to solve a problem that I think I will need advanced combinatorial techniques, correct me if I am wrong. Let $G$ be a large directioned ...
1
vote
0answers
57 views

Multinomial Theorem for Negative Exponents

Using an analog to Newton's binomial theorem with negative exponents, is it true that $$ \begin{align} \left(\sum_{k=0}^mx^k\right)^{-n} & = \sum_{0\le ...
9
votes
5answers
871 views

A seemingly easy combinatorics brain teaser

So I have a brain teaser that goes like this: There's a school that awards students that, during a given period, are never late more than once and who don't ever happen to be absent for three ...
5
votes
3answers
450 views

Tricky Rectangle Problem [closed]

How many rectangles are there which do not include any yellow squares?
5
votes
2answers
100 views

Solve the following summation

$S = \dfrac{n \choose 0}{1} + \dfrac{n \choose 1}{2} + \dfrac{n \choose 2}{3}+\dotsb+\dfrac{n \choose n}{n+1}$
1
vote
1answer
47 views

Win $n$ out of $2n+1$ [closed]

Two teams play the best of $2n+1$. Team 1 has cheated and wins when they have won $n$ times and Team 2 wins if they have won $n+1$ times. What is the chance that Team 1 will be the winner of the ...
0
votes
2answers
42 views

Combinatorial sequence [closed]

Say we have $n$ songs, each song is qualified to be a 'rubbish' song ($k$ times) or to be a 'pleasant' song ($n-k$ times). The shuffle modus plays the songs randomly after each other. Determine the ...
4
votes
1answer
46 views

Complement Probability- Choose A Ball

An urn contains $n$ balls, one of which is special. If $k$ of these balls are withdrawn one at a time, with each selection being equally likely to be any of the balls that remain at the time, what ...
1
vote
1answer
47 views

Trouble Understanding a Combinatorics Problem

This question appeared on my combinatorics exam. I did not even understand the question. Determine the number of functions, $f:\{1,2,3\} \to \{1,2,3\}$, that satisfy $$f(1)+f(3)\equiv0\ (\text{mod ...
0
votes
0answers
29 views

Number of patterns

A pattern consist of three non-empty strings $s_1$ , $s_2$ , $s_3$ such that no string is prefix of another. Strings can have length $\leq n$ and consist of first $k$ english letters of the alphabet. ...
5
votes
1answer
68 views

Combinatorial Proof - choose k out of n+k

I want to prove the following identity combinatorial: \begin{align} {n + k \choose k} = \sum \limits_{i=0}^n {n -i +k -1 \choose k -1}. \end{align} We want to choose k out of $n+k$. I want to use the ...
4
votes
3answers
68 views

Number of different integers between $1,000$ and $10,000$

How many integers are there between $1,000$ and $10,000$ divisible by $60$ and all with distinct digits? I know that there are $8,999$ integers in total, and $\lfloor\frac{8999}{60}\rfloor=149$. So ...
0
votes
1answer
22 views

How many ways can N labelled balls be placed in M unlabelled boxes, provided each box has at least P balls inside?

How many ways can $N$ labelled balls be placed in $M$ unlabelled boxes, provided each box must have at least $P$ balls inside? Naturally $N > M \times P$. Any closed form solutions would be ...
0
votes
1answer
53 views

A square grid path problem proof

Let n be a positive integer. Consider all possible ways of arranging n pairs of parentheses “(” and “)” in a row. We want to arrange them in a way that it is possible to pair up the left parentheses ...
1
vote
2answers
53 views

Number of ways to throw at most 14 with 4 dice - generating functions

Determine the chance to throw at most 14 with 4 normal dice. I will set up the right generating function to determine the number of ways tot thow at most 14 with 4 normal dice and I need some help. I ...
1
vote
2answers
48 views

Calculating all possible sums of the numbers $2^0, 2^1, \ldots, 2^{(n-1)}$

Using the simple equation $2^{n-1}$ you get answers such as: $1,2,4,8,16,32,64,128,256,$ etc. How can I find all possible number combinations within this range? For example, then numbers $1,2,4,8$ ...
1
vote
0answers
35 views

Do combinatorial species have adjoints?

A combinatorial species is a functor $F$ from the category $\mathbb{B}$ of finite sets and bijections to itself. What (if anything) can be said about adjunctions of species?
2
votes
1answer
21 views

Neighboring transpositions for number of length n, Kendall Tau Distance

I have the following question: Given is a string (or number) of length n, n being the number of its digits (or characters) - say for instance given is the number "12345" which has length n = 5. ...
1
vote
0answers
13 views

Do you have to use Latin Squares to solve the Social Golfer's problem?

I'm trying to write a program to solve the social golfers program constrained to a certain number of weeks and so far I've been using the Latin Squares method detailed here: ...
1
vote
3answers
42 views

number of subsets of even and odd

Let $A$ be a finite set. Prove or disprove: the number of subsets of $A$ whose size is even is equal to the number of subsets of $A$ whose size is odd. Example: $A = {1,2}$. The subsets of $A$ are ...
0
votes
2answers
34 views

Counting question proof involving binomial

Let $x,y,z,n$ be positive integers such that $x\leq y\leq z\leq n$. Prove (by counting in two different ways) that: $\binom {n} {x} \binom {n-x} {y-x} \binom {n-y} {z-y} = \binom {n} {z} \binom {z} ...
0
votes
2answers
30 views

Traveling salesman problem (TSP): what is the Relation with number of vertices and length of the found route?

I know that there are many algorithms (exact or approximate) which implement the traveling salesman problem. I would like to know the relation between the number of the vertices (i.e., the places to ...
2
votes
0answers
24 views

Partitioning a set with intersections

Imagine that we want to give an exam consisting of $m$ problems to $n$ students in such a way that every two sets of problems have one or zero problems in common. Is there a closed formula to compute ...
1
vote
2answers
35 views

Move elements in a grid (Combinatorics)

Here's an interesting and fairly simple problem I encountered a couple of weeks ago. There is a grid with 11 rows and 11 columns with a ball in every cell. Move every ball to an adjacent cell (up, ...
2
votes
1answer
71 views

Learning Combinatorics Further

I have completed most of the basic parts in Combinatorics like Generalised Permutation & Combination, Recurrence relations, Pigeonhole Principle, Formal power series, Stirling no, Catalan no, ...
2
votes
1answer
22 views

weak compositions of $n$ with $2m$ parts and extra conditions

A weak composition of $n$ into $k$ parts is a sum $$\displaystyle \sum_{i=0}^k x_i=n$$ such that $x_i\in \mathbb{Z}$ and $x_i\geq 0$ for each $i$. I am trying to figure out the number of weak ...
3
votes
0answers
41 views

Coefficients of (generating) function

If I have the generating function \begin{equation*} A(x)= \frac{1}{(1-x^{10})\cdot(1-x^5)\cdot(1-x) }\,, \end{equation*} what is a clean way to find the coefficients of $x^{n}$. This coefficient ...
0
votes
1answer
41 views

Combinatorics Question about combining rows in a table

I have a table of rows, some rows I want to combine, but not others, for example because the number of cases in adjoining rows is small. If I have separate rows $A,B,C$, I can combine them into $AB,C; ...
3
votes
0answers
42 views

Extremal problem with infinite cardinals

Made up, but somewhat interesting: Let $\lambda\leq\kappa$ be infinite cardinals. Let $X$ be a set of cardinality $\kappa$. Let $F\subseteq [X]^\kappa$ be a family of $2^\kappa$ subsets, which is ...
0
votes
2answers
70 views

Sum of squares of distances between all vertices in tree

Given the adjacency list of unweighted undirected graph without cycles, calculate sum of squares of distances between every two vertices. How to do this fast? (programming task)
0
votes
0answers
24 views

Upper and lower bounds on probability in binomial distribution.

Suppose i have a random variable $X \sim \mathrm{Bin}(n,p)$ and some $1 \leq l \leq n$ can i obtain good upper and lower bounds on the probability that $$\mathbb{P}(X \geq l)?$$ After some research I ...
3
votes
1answer
41 views

How many ways 5 different books be distributed among 5 students

I've seen this question in a book and can't figure it out correctly. Let 5 different books be distributed among 5 students. Suppose the books are returned and distributed to the students again ...
0
votes
1answer
27 views

(combinatorics) 2 problems using signless Stirling number of the first kind

For every subset of [n-1], take the products of all its elements (empty products being taken to be 1) and then,sum of all 2^(n-1) products. What is this value? 2.For every k-element subsets of ...
4
votes
1answer
45 views

Probability of picking at least one of each of $x$ items in $y$ tries from possible $z$ options

As stated in title, there are $z$ things to pick from, and you get $y$ picks, with replacement. What's the probability of picking such that you get at least one of each of $x$ things? Assume $x \leq ...
5
votes
4answers
220 views

(combinatorics) prove that on average, n-permutations have Hn cycles without mathematical induction.

Prove that on average, n-permutations have $H_n$ cycles, where $H_n=1+1/2+1/3+...+1/n$ without mathematical induction. I think that on average, the number of cycles of length i (1≤i≤n) should be ...
2
votes
1answer
22 views

probability of choosing an object at least once in $3$ drawings

So there are $4$ objects in total, and I want to know the probability of choosing object A at least once in $3$ drawings. What I did was add $3C1 + 3C2 + 3C3$ and got $7$ and, as a final answer, I ...
-2
votes
1answer
36 views

Expressing $\frac {x^n}{(1-x)^n}$ as a generating function [closed]

How did they get the following: $$\frac {x^n}{(1-x)^n} = \sum\limits_{m}{m-1 \choose n-1}{x^m}$$
1
vote
1answer
26 views

The fundamental counting principle in reverse

How many natural odd numbers are between $100$ and $999$ that have all different digits? There are two conditions in this question: $(1)$the number must be odd and $(2)$must have all different ...
0
votes
1answer
22 views

number of possible strings of length 4 with exactly 1 digit repeated?

I am trying to find the number of string that have a length of 4 and have 1 digit repeated (ex. 7181). What i did was I found the total number of permutations and got 12, since there is a pair of ...
4
votes
0answers
49 views

What are some other examples of this phenomenon: if $S$ is a finite set, then all possible total orderings of $S$ are isomorphic (as posets).

Finite sets have the amazing property that if $S$ is a finite set, then all possible total orderings of $S$ are isomorphic (as posets). Said another way: finite totally-ordered sets that are ...
1
vote
1answer
39 views

Evaluate $\sum\limits_{k=m}^n (-1)^k {n \choose k} {k \choose m}$

By using generating functions and snake-oil I got to Also what is the implication of $\sum \limits_ {k<={n}}$? I am told that this is equivalent to: But I'm not sure how to do that step, ...
1
vote
1answer
19 views

How many different paths are there on a lattice that pass through a given point?

When Looking at A to C by ${4\choose 2}$ we are ordering, right-r up-u 4 times, so ordering 2 r's or 2 u's determine the other 2 moves? And same with C to B ${3\choose 2}$ ordering the 2 r's ...
0
votes
2answers
74 views

Subset Counting question

How many subsets of [20] consist of 3 odd integers and any number of even integers? This question was asked in an interview today and I wasn't able to solve it. Please help, thanks in advance
2
votes
0answers
29 views

Inviting People To A Party With Limitations

A person has 8 friends, of whom 5 will be invited to a party. (b) How many choices if 2 of the friends will only attend together? Using inclusion-exclusion there are ${8\choose 5}-{2\choose ...
2
votes
2answers
41 views

Counting Problem - Strings

What is the number of strings of four decimal digits that contain exactly one digit repeated twice? (e.g 1198) My intuition was to first place the digits that aren't repeated and then place the ...
1
vote
0answers
19 views

Total probability distribution of multiple random lotteries

My question: Imagine $d$ identical lotteries. Each individual lottery picks a cost $c_{i}$ between $0$ and $1$. Picking a costs occurs with probability distribution $f(c)$. The total cost of these ...