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)

2
votes
1answer
37 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
38 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
64 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
71 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
27 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 ...
18
votes
2answers
282 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
34 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
18 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
19 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
54 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
27 views
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
58 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
44 views

Method of inclusion/exclusion [closed]

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
62 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
59 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? [closed]

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
37 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
111 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 ...
2
votes
0answers
34 views

Sizes of Hamming balls on the discrete torus

Consider the discrete torus $\mathbb Z^2_k $, with $k$ even, i.e. the graph with vertex set $\{0,1,\dots, k-1\} \times \{0,1,\dots, k-1\}$ and edges between any pair of vertices which differ in ...
3
votes
1answer
23 views

How many subgraphs of $K_{m,n}$ are there that contain m + n vertices?

In this problem, a subgraph of $G = (V,E)$ is given by $G' = (V', E')$ where $V' \subset V$ and $E'$ is subset of edges of $E$ that connect two vertices in $V'$. How many subgraphs of $K_{m,n}$ are ...
0
votes
1answer
32 views

Counting permutations of up to k elements

Given a set of $n$ elements, I want to count all permutations with repetition, from $1$ to $k$ elements ($k>2$). In other words, $n^k+n^{k-1}+…+n^1$. What's the term/notation for this operation? ...
3
votes
5answers
77 views

There are $n$ persons sitting around a table…

There are $n$ persons sitting around a circular table. Then, in how many different ways 3 persons can be selected if none of them are neighbours. My approach:- Let us pretend that we have already ...
1
vote
1answer
35 views

Counting the number of unicyclic graphs

Could you help me giving me the number of unicyclic graphs with k vertices and k edges ? I remind that a unicyclic graph with k vertices and k edges is a tree with k vertices and k-1 edges to wich we ...
3
votes
0answers
18 views

Building a 3D matrix of positive integers

I'm trying to build a 3D matrix made up of positive integers that has very specific properties. The matrix dimensions are $N \times N \times (N+1)$ where $N$ is a positive integer. The matrix has two ...
-1
votes
4answers
49 views

Counting candies in boxes

There are $5$ boxes containing $80$ candies. After taking $\frac{1}{5}$ of the candies in the first box and putting them in the seconf one, we take $\frac{1}{5}$ of the candies in the second box and ...
2
votes
2answers
58 views

Find all $a,b,c$ such that $\binom{a}{b} \binom{b}{c}=2\binom{a}{c}$

Find all $a,b,c \in \Bbb N $ such that $$\binom{a}{b} \binom{b}{c}=2\binom{a}{c}$$ $(c\leq b \leq a)$
1
vote
1answer
11 views

Looking for a recurrence relation ot combinatorial way to calculate initial number

A flock of birds migrating south flies above seven lakes. Half of the birds in the flock, plus half a bird(I'm guessing the initial flock contained an odd number of birds, say 5, so in the first lake ...
-4
votes
0answers
27 views

circular derangement related to round table [duplicate]

N people are invited to a dinner party and they are sitting on a round table. Each person is sitting on a chair there are exactly N chairs. So each person has exactly two neighboring chairs, one on ...
3
votes
0answers
51 views

Probability of $m$ out of $n$ rolls of a die being among the numbers $1,2,\ldots,m-1$, for some $m$.

Suppose I have a $k$ sided die with the numbers $1,2,\ldots,k$ on each side, and that I roll it $n$ times ($n<k$). What is the probability that there exists an $m\leq n$, so that $m$ of the $n$ ...
13
votes
9answers
2k views

How many ways can seven people sit around a circular table?

How many ways seven people can sit around a circular table? For first, I thought it was $7!$ (the number of ways of sitting in seven chairs), but the answer is $(7-1)!$. I don't understand how ...
0
votes
1answer
34 views

Finding the total number of members in a club with multiple committees [closed]

In ISI club each member is on two committees and any two committees have exactly one member in common. There are five committees. How many members does ISI club have?
10
votes
1answer
121 views

No sum of three numbers equals another number in set

Consider the set $S=\{1,2,\ldots,1000\}$. What is the maximum size of a subset $S'$ such that for any distinct $a,b,c,d\in S'$, we have $a+b+c\neq d$? We can choose $S'=\{333,334,335,\ldots,1000\}$, ...
0
votes
1answer
59 views

Circular arrangement and inclusion-exclusion principle

$4$ people are invited to a dinner party and they are sitting on a round table. Each person is sitting on a chair there are exactly $4$ chairs. So each person has exactly two neighboring chairs, one ...
-2
votes
1answer
44 views

Show that $x\cdot x(k) = x(k+1) + k\cdot x(k)$ [closed]

Show that $x\cdot x(k) = x(k+1) + k\cdot x(k)$ where $x(n)$ is the falling factorial. $$x(n) = x(x-1)(x-2) \cdots (x-n+1)$$ $$x(k+1)+kx(k) = (x)(x-1)(x-2)\cdots(x-k+2) + ...
2
votes
0answers
45 views

Edges of a permutohedron

Consider a permutohedron $P_n$ (this is a polytope which is a convex hull of $n!$ points, which are obtained from $(1,2,...,n)$ by all possible permutations of coordinates). I have to prove the ...
4
votes
1answer
88 views

The Island in the Miracle Sea. (Christmas edition)

To all of you who love math like me, I have this puzzling riddle that I hope you find interesting : On Christmas Eve just after midnight, Santa was riding his sleigh over the Miracle Sea when ...
0
votes
1answer
30 views

Extension of hypercube

I understand the notion of a hypercube as a graph with vertex set $\{0,1\}^{n}$ and an edge between two vertices if their vertices differ in one co-ordinate is there an extensive body of work on the ...
1
vote
3answers
60 views

Why is this combinatoric solution not correct?

I'm trying to solve the following problem: Balls of the colors red, orange, yellow, green, blue, indigo, violet (7 colors, 1 ball per color) are placed into 4 different boxes A,B,C,D so that no box ...
4
votes
0answers
100 views

A set of 19 numbers that are at most 93, and a set of 93 numbers that are at most 19, have equal sumsets

If $x_1, x_2, ..., x_{19}$ are natural numbers lower or equal than 93 and $y_1, y_2, ..., y_{93}$ are natural numbers lower or equal than 19 then there is a non zero sum of some $x_i$ which is equal ...
0
votes
2answers
40 views

distribution probability question involving binary functions for certain n<2^10

For any positive integer n, let G(n) be the number of pairs of adjacent bits in the binary representation of n which are different. For example, G(10)=3 because the bits of $1010_2$ change at all ...
0
votes
1answer
53 views

Marriage theorem. Proof. [closed]

I am asking for advice: Let G be the bipartite graph $(V_1, E, V_2)$ with each vertex in $V$, of degree at least $d (> 0)$ and each vertex in $V_2$ of degree $d$ or less. Show that if each vertex ...
1
vote
1answer
26 views

Find every possible distribution of the x elements considering a constraint on one of them

Considering a number r of triplets { a, c, i } I'd like to know which procedure / math field should I use to calculate every ...
3
votes
2answers
99 views

Christmas protocol

Since holiday season is coming, here is a little practical-purpose combinatorics question. Lots of group of friends or families practice the random variant of Secret Santa, where each member buys a ...
3
votes
3answers
281 views

Method for Counting the Divisors of a number

I need to find the number of divisors of 600. Is there any other way to solve the problem, apart from writing them down and counting??
1
vote
2answers
66 views

Combinatorics in a Party.

There are 12 persons in a dinner party, they are to be arranged on two sides of a rectangular table. Supposing that the master and the mistress of the house have are always facing each other, and ...
8
votes
2answers
156 views

Solving a circular permutation problem with recursion

N people are invited to a dinner party, and they are sitting at a round table. Each person is sitting on a chair; there are exactly N chairs. So each person has exactly two neighboring chairs, one on ...