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)

0
votes
2answers
12 views

Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain at most one element from each $S_i$ is $(a_1 + 1)(a_2 + 1) \dots (a_t + 1)$.

I found this problems on Aigner's: A course in enumeration: 1.1 We are given $t$ disjoint sets $S_i$ with $|Si| = a_i$. Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain ...
0
votes
0answers
6 views

Submodularity in Max-k-Coverage

Why the coverage function $f(S)$ for the Maximum-k-coverage is submodular? The function is defined here (see Coverage Functions) ...
2
votes
3answers
35 views

Probability of winning a rigged coin-flipping game

Betsy and Katie are playing a game with an unfair coin. The coin is rigged to come up heads with probability $\frac35$ and tails with probability $\frac25$. Betsy goes first. The two take turns. The ...
3
votes
1answer
45 views

Number of ways to arrange items

Given a list of $n$ distinct items, where a smaller item behind a larger item is obscured, if you can see $x$ items from one end, and $y$ from the other, how many ways can the items be arranged? ...
2
votes
4answers
62 views

How to find the number of possible outcomes of 10 games between 20 teams?

Hi I am looking for an equation to find possible combinations in a non repeating format with a twist. Here is the example: There are 10 games between 20 teams. I have to chose 5 winners but ...
-1
votes
4answers
45 views

How many ways are there to prepare one of 400 varieties of coffee in one of 7 ways?

I'm hoping someone can check my thinking: I have 400 distinct varieties of coffee. Each can be prepared in 7 ways (black, cream and sugar, etc.). How many possible combinations are there? I'm thinking ...
0
votes
0answers
31 views

How to start a proof ? What kind of mathematical tool I can use here? [on hold]

I have a set of $n$ points $\{A_1,A_2,...,A_n\}$. I draw every triangle formed with $3$ points $A$. What mathematical tool can I use to describe intersections between all these triangles ? I would ...
1
vote
1answer
56 views

How to solve this kind of problem?

I've just found the following problem: $\quad\quad$ $\quad\quad$ $\quad\,$ And I believe that it could be done with something in combinatorics, my feeling is that generating functions would ...
-10
votes
0answers
32 views

Showing $M(n,k,q)=\sum_{i=0}^{q}(-1)^{q+i}\binom{q}{i}\begin{pmatrix}0&n\\k&i\end{pmatrix}$. [on hold]

How do I show $$M(n,k,q)=\sum_{i=0}^{q}(-1)^{q+i}\binom{q}{i}\begin{pmatrix}0&n\\k&i\end{pmatrix}$$ for $q>1?$
3
votes
3answers
51 views

How many different (circular) garlands can be made using $3$ white flowers and $6m$ red flowers?

This is my first question here. I'm given $3$ white flowers and $6m$ red flowers, for some $m \in \mathbb{N}$. I want to make a circular garland using all of the flowers. Two garlands are considered ...
1
vote
0answers
37 views

A combinatorial game theory problem

In details, Let, there are four bishops on a chessboard where every two bishops are in pair ( as there are 4 bishops that means 2 pairs and in each pair they sit in vicinal squares). How many ...
0
votes
1answer
31 views

The number of self-avoiding paths in the plane of length $k$

The number of self-avoiding paths in the plane of length $k$ is at most $4 \cdot 3^{k-1}$ according to this. Why? My immediate thought: four options for the first move and always three choices after ...
0
votes
0answers
78 views

Number of sequences of 0s and 1s of length N such that k consecutive 1s are present [on hold]

How many different sequences of $0$s and $1$s of length $N$ are possible such that at least $k$ consecutive $1$s are present in them where $k\leq N$ exactly $k$ consecutive $1$s are present in ...
-1
votes
1answer
35 views

All variants of stars and bars / balls and bins problem [on hold]

The Stars and Bars problem or Balls and Bins problem are the the very basic in combinatorics but at the same time are quite helpful for beginners. Can we have list of variants of these problems? Add ...
1
vote
1answer
25 views

Union of each family is not the whole set

Let $n\geq k>0$, and consider all $\binom{n}{k}$ subsets of $A=\{1,2,\ldots,n\}$ of size $k$. We want to partition it into families so that the union of each family is not equal to $A$. At least ...
2
votes
0answers
22 views

Concerning the summation of digits to square-free numbers

Consider an alphabet of $n+1$ letters: $\{0,...,n \}$. Let $z$ be a number in base $n+1$ such that it has at most $n$ digits (so the initial/first string of digits can be composed of $0$'s). Let ...
0
votes
1answer
50 views

Can this binomial summation be simplified?

I got something like $\displaystyle\sum_{i=0}^K{ \binom{n+i}{i} \cdot \alpha^i} $ where $n,\ K,\ \alpha$ are definite values, $\binom{n+i}{i}$ is the Combinatorial number that choose $i$ from ...
0
votes
3answers
52 views

How many ways to make a connected graph using 4, 5, 6 edges?

How can/how many ways can you make a connected graph that has 5 vertices using 4, 5, 6 edges? I'm not sure how it would look like for 4 edges. Can you draw a diagram?
1
vote
0answers
14 views

Inequality to bound $\sum_i a_i b_i - \sum_i c_i d_i$ (harmonic eigenfunction/graph) type sum with constraints

We have a homogeneous graph $G = (V,E)$ with a function $f:V\rightarrow \mathbb{R}$. We define the following modulus: $\displaystyle \omega(s) = \sup\{f(x)-f(y) \ | \ |x-y|=s \}$ and wish to lower ...
1
vote
1answer
49 views

What is the probability of choosing r objects from c different groups when there are m groups of n objects?

Suppose I have m groups of n objects each for a total of nm objects. I am going to choose r of these nm objects. I want to know what the probability is that my r objects come from c different ...
4
votes
4answers
526 views

Is it possible to permute an unknown binary sequence so that two particular bits are equal?

A blind mathematician is give a $2015$ bit sequence. The mathematician can take any two bits and switch them (so the bit in position $A$ goes to position $B$ and vice-versa). He knows at what position ...
6
votes
0answers
109 views

A curious identity of weighted sums over multi-set permutations.

Suppose we have $n$ balls which are the same except colors, denote $S$ to be the set of all different permutations of the balls.(i.e. the swap of two balls with the same color will be the same ...
1
vote
0answers
79 views

Evaluation of a finite sum

I am having trouble evaluating the following finite sum: $$ \sum_{l=0}^{r}\binom{r}{l}(r-l)^{k},\qquad k\in\mathbb{N}_{0}. $$ Can you shed light on it?
1
vote
1answer
27 views

Questions concerning assumptions to conclude that $\operatorname{P}=\operatorname{NP}$

Suppose you find a reduction from the $k$-vertex-cut problem to the hamiltonian-path problem. In particular, you find an algorithm $A$ that, given the graph $G$ and the number $k$, outputs a ...
0
votes
0answers
18 views

Determine if the following family of hash functions is universal

Let $H = \{h_1,h_2,h_3\}$ be the family of hash functions defined below, each mapping $\{a,b,c,d,e\}$ to $\{0,1,2\}$. Is $H$ universal? A family of hash functions is universal if $\forall ...
0
votes
1answer
32 views

Finding number of relations using counting

Consider $A$ = {$w, x, y, z$}. Determine: (a) the number of possible relations on A, i.e., subsets of A×A (b) the number of relations on A that are reflexive and symmetric. (c) the number of ...
0
votes
2answers
52 views

Stars and bars with minimum number of categories

I've been trying to figure out a closed form solution to this problem, but I haven't been able to find one yet. How many ways are there to pick $n$ items from $k$ categories, such that at least ...
0
votes
1answer
21 views

9-digit ternary sequences with no three consecutive digits that are the same

How many nine-digit sequences with exactly three 0s, three 1s, and three 2s can be created if there are never three consecutive numbers that are the same? Can someone please show a step-by-step ...
2
votes
1answer
35 views

Number of Dyck paths from $(0,0)$ to $(2n,k_1)$ if allowed to go below the $x$ axis

What is the number of (general?) Dyck paths from $(0,0)$ to $(2n,k_1)$, where $k_1\geq0$, allowing the path to go below the $x$ axis and touch the negative horizontal line at $k_2\leq0$ an arbitrary ...
1
vote
0answers
37 views

Distinguishable balls in distinguishable boxes?

Suppose I have $n$ distinguishable balls and $N$ distinguishable boxes. A particular configuration of this 'system' is such that there are $k$ particles in a box, b, where $1\lt b \lt N$ (i.e. the ...
8
votes
1answer
61 views

probability that no two spiders end up at the same vertex?

Eight spiders are located on the eight vertices of a cube. When a bell rings, each spider moves (at random, independent of the others) to an adjacent vertex. What is the probability that no two ...
1
vote
1answer
36 views

Proof of the fact that the set of (p,q) shuffles is a cross section of the subgroup $S_p\times S_q$

Definition Let $G$ be a group and $H$ its subgroup. We name a subset $K$ of $G$ a cross section if it has exactly one element from each left coset of $G/H$. Definition Let $n=p+q$ for some ...
1
vote
1answer
27 views

Combinations - no repetition for mirrors?

My question is, if there is a simple explanation as to why mirrors aren't counted twice with binomials such as it is in the case it's not a mirror? Here is an example: Consider the elements {1, 4}. ...
0
votes
0answers
25 views

Transforming Exponential to Ordinary Generating Functions

I am looking for a particular ordinary generating function, if it exists for the Associated Stirling Numbers of the second kind $$b(1;n,j)=b(n,j)=\sum_{k=0}^j(-1)^k\binom{n}{k}S(n-k,j-k)$$ Where ...
10
votes
0answers
106 views
+50

An example where $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is the number of ways of counting something?

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer. There is a answer given here to this question here. I've seen how it can be proven using recurrence ...
1
vote
1answer
32 views

Distribution problem where |a|, |b|, |c|, and |d| are at most 10. Check my work?

How many ways can a+b+c+d=18, where a,b,c,d are integers such that $|a|,\ |b|,\ |c|,\ |d|$ are each at most 10? This is what I have so far. If all four numbers have the restriction -10 =< a, b, ...
3
votes
1answer
14 views

Interpreting the Möbius function of a poset

I have just learned about incidence algebras and Möbius inversion. I know that the Möbius function is the inverse of the zeta function, and that it appears in the important Möbius inversion formula. ...
0
votes
1answer
17 views

Finding nth permutation in dictionary order with repeats

Given a set of symbols (e.g. $(A, A, B, B, B, C, D, D)$), calculate the nth permutation sorted in alphabetical order. I know how to do this with a set of symbols containing no repeats, but I can't ...
1
vote
1answer
16 views

How does $\mathcal{A}\cup \mathcal{B}$ indicates that there is at least one augmenting path on $\mathcal{A}$?

I had an exam and there was the following question: $\mathcal{A}$ and $\mathcal{B}$ are matchings in a graph $G$, with $|\mathcal{A}|< |\mathcal{B}|$, study the graph formed with the edges of ...
0
votes
1answer
21 views

Combinatorial arrangements notation

I have a program that executes 2 kinds of operation with bytes and bits sets: BYTE OPERATION related to BIT POSITION and BIT OPERATION related to BIT POSITION The first operation provides a kind of ...
4
votes
2answers
53 views

Simplifying $\sum_{j=k}^{n}\binom{j}{k}/(2^{k-1})$

While doing an exercise (computing an expected value), I encountered an expression that looks like this. Is there a simpler formula? $$ \sum_{j=k}^{n}\frac{\binom{j}{k}}{2^{k-1}} $$ If it wasn't ...
1
vote
1answer
25 views

How do i equaly distribute certain weights if i know how many times they appear

So i have those number groups 0, 273073 5, 222768 7, 43000 3, 24000 10, 12000 15, 12000 20, 12000 50, 1000 100, 100 500, 50 1000, 5 5000, 2 15000, 1 40000, 1 The first is the "weight"(which doesnt ...
5
votes
1answer
52 views

Max flow min cut from duality

I have been having some trouble deriving the max flow min cut theorem from duality, which I was told is possible. To begin with, I need to cast the problem into the form "maximize $\langle c, ...
0
votes
2answers
42 views

Method of inclusion/exclusion [on hold]

Having a hard time with this, please help. Given $5$ pairs of gloves, in how many ways can $5$ people chose $2$ gloves with no one getting a matching pair?
0
votes
2answers
60 views

Probability that n people collectively occupy all 365 birthdays

The problem is quite simple to formulate. If you have a large group of people (n > 365), and their birthdays are uniformly distributed over the year (365 days), what's the probability that every day ...
0
votes
3answers
53 views

Let $A=\{0,1\}$. How many strings of length $5$ are in $A^*$ where at least two $1$ are next to each other?

Let $A=\{0,1\}$. How many strings of length $5$ where at least two $1$ next to each other are there in $A^*$?
1
vote
2answers
38 views

8th positive odd integer that is an ODD Catalan number? [on hold]

The $n^{\text{th}}$ Catalan number is given by the formula $C_n = \frac 1{n+1}\binom{2n}n$. It also satisfies the recurence \begin{align*}C_n &=\sum_{k=0}^{n-1}C_kC_{n-1-k}\\ &= ...
2
votes
1answer
35 views

At least 2 girls between every pair of boys distribution question?

Three boys and eight girls are seated randomly in a row of 11 chairs. All orders are equally probable. What is the probability that there are at least 2 girls between every pair of boys? What is ...
5
votes
1answer
100 views

Set with distinct subset sums

The problem is as follows : Given a set A with distinct positive integer elements, prove that there always exists another set B consisting of positive integers, s.t., The size of B is less than or ...