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)

2
votes
1answer
34 views

Set of pairs of options that could be wrong/right

One has a list of n options out of which 2 are incorrect, and guesses can be made by picking a pair of options. After picking a pair as a guess, it is either valid, in which case both of the pair's ...
2
votes
2answers
107 views

Why General Leibniz rule and Newton's Binomial are so similar?

The binomial expansion: $$(x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$$ The General Leibniz rule (used as a generalization of the product rule for derivatives): $$(fg)^{(n)} = ...
0
votes
0answers
18 views

Determining Counts of Discrete Objects Using Linear Algebra

I'm teaching myself linear algebra and was able to solve the following question using trial and error, but--how would one setup and solve a question like this using Linear Algebra? I have 32 bills ...
3
votes
2answers
66 views

Counting sequences using Catalan Numbers

Count the number of sequences $a_{1},...,a_{2015}$ such that: $a_{i}\in \{-1,1\}$, and $\sum _{i=1} ^ {2015} a_{i}=7$, and $\sum _{i=1} ^{j} a_i >0$ for every $1\leq j\leq 2015$ I assume we have ...
2
votes
0answers
117 views

basic concept about edge graphs (line graphs)

I was learning about the edge graphs or line graphs $L(G)$ of a graph $G$. I read about the relation between degree of any two vertices $u$ and $v$ in $G$ and that of edge $uv$ in $L(G)$. I am just ...
0
votes
0answers
40 views

about complement of a graph

Let $G$ be a $k-$regular graph on $n$ vertices. we know that if $k\geq n/2$, then $G$ is a connected graph. Now, if we take complement of graph $G$ and denote it as $\bar G$ then $\bar G$ will be ...
2
votes
1answer
69 views

What is this type of function called? How can I translate it to a different origin?

A factory produces 1 widget per week. A builder builds 1 factory each week. A construction firm trains 1 new builder each week. Partially-produced things do not produce anything. Starting with 1 firm, ...
0
votes
1answer
53 views

Dilworth's theorem

Show that the truth of Dilworth's theorem for two-level posets can be deduced from Hall's theorem. I am not sure how to prove this. A poset $P$ is a two-level poset if it is the union of two ...
0
votes
0answers
17 views

How to fill number of positions with given operators? [closed]

We have 4 position between 5 numbers ....and 3 operators (+,*,/) to fill this position... for example 1_2_10_15_25 we can have 1+2*10*15/25 or 1+2+10+15+25 (Repetition of any operator is allowed) ...
4
votes
4answers
177 views

The even-numbered coefficients of the Maclaurin series of $ \frac{1}{\cos(x)} $ are odd integers.

Let’s consider $ G(z) \stackrel{\text{df}}{=} \dfrac{1}{\cos(z)} $ as the exponential generating function of the sequence of Euler numbers. How can one prove that in the Maclaurin series of $ G $, $$ ...
2
votes
1answer
35 views

Generating function for recurrence in two variables

Given characteristic polynomial for the recurrence in two variables (say $F(x,y)$) $$ (y^2-1)^x $$ and initial values can generating function for $F(x,y)$ be derived? I know how to do it for a ...
6
votes
2answers
76 views

Exploring $ \sum_{n=0}^\infty \frac{n^p}{n!} = B_pe$, particularly $p = 2$.

I was exploring the fact that $$ \sum_{n=0}^\infty \frac{n^p}{n!} = B_pe,$$ where $B_n$ is the $n$th Bell number. I found this result by exploring the series on wolframalpha and looking up the ...
0
votes
2answers
37 views

Congruence for Stirling Number of first kind $s(n,k)$ when $n$ is prime

Let $s(n,k)$ be the Stirling numbers of first kind: $$\prod_{k=0}^{k=n-1}(x-k) =\sum_{k=0}^{k=n}s(n,k)x^k$$ $p$ is prime $\iff$ for all $k\in\{2,..,p-1\}$, $s(p,k)\equiv0\ mod\ p $ How ...
1
vote
1answer
53 views

How many unique ways can I sum $k$ non-negative numbers to $N$?

I have a similar question but not exactly the same as this. I'm trying to determine the number of unique multisets $S\in \mathbb{N}$ that exist when the members are required to sum to a number $N$. ...
3
votes
1answer
142 views

Arrangement of $100$ points inside $13\times18$ rectangle

Prove that you can't arrange 100 points inside a $13\times18$ rectangle so that the distance between any two points is at least 2. I tried many ways to divide the rectangle, but I can't get the ...
6
votes
5answers
3k views

Show me some pigeonhole problems [closed]

I'm preparing myself to a combinatorics test. A part of it will concentrate on the pigeonhole principle. Thus, I need some hard to very hard problems in the subject to solve. I would be thankful if ...
0
votes
1answer
107 views

Senators full of hatred [closed]

There are 51 senators in a senate. The senate needs to be divided into n committees such that each senator is on exactly one committee. Each senator hates exactly three other senators. (If ...
2
votes
1answer
37 views

$5$ points on a sphere [duplicate]

Diffuse $5$ points on a sphere. Prove there is a closed half-sphere that has at least $4$ points on it.
0
votes
0answers
34 views

Recurrence in two variables

Anyone know how to solve the following recurrence relation in two variables: $$ f(x,y) = b f(x-1,y) + c f(y,x-1), \qquad \begin{cases}f(x,0) = b^{(x-1)} \\ f(0,y) = 0 \end{cases} $$ (Note: repost of ...
0
votes
0answers
49 views

How does Dilworth’s Theorem apply to the set $\{0, 2, 6, 7\}$?

I'm having some serious problems with Dilworth's Theorem. My question is 'how does Dilworth’s Theorem apply to the set $\{0, 2, 6, 7\}$?'. Any help is appreciated.
1
vote
0answers
25 views

question regarding edge space

Given a graph $G=(V,E)$ and it's edges space $\mathcal{E}(G)$ in the book by Diestel it defines given two edges sets $F,F'$ and their coefficients $\lambda_{1},...,\lambda_{m}$ and ...
8
votes
2answers
52 views

Given $n$ points, the difference of $2$ of them is $1/n$ close to an integer

From today's ENS Ulm Math D exam Let $x_1,\ldots,x_n$ be real numbers Prove there exists $i\neq j $ and $h\in \mathbb Z$ such that $|x_i-x_j-h|\leq \frac{1}{n}$ I tried contradiction and ...
0
votes
1answer
27 views

How to show mutually orthogonal latin squares

I have a question concerning mutually orthogonal latin squares (MOLS). Let $ \mathbb F $ be a field of $n\in\mathbb N$ elements. For all $q\in\mathbb F \backslash \{0\}$, define $n\times n $ tables ...
4
votes
1answer
63 views

Finite sequence with no two consecutive terms

$\newcommand{\N}{\mathbb{N}}$ Let $n \in \N$, we define $[n] \doteq \{1 , \ldots, n \}$. Consider the following $$ H_n^k \doteq \{ z \in [n]^k  \mid \forall i \in [k-1]: \ z_{i+1} \neq z_i + 1 \} $$ ...
0
votes
2answers
34 views

Why do we divide to remove elements considered equivalent?

Suppose we have a set of $N$ elements, each of which is considered distintic from all others. If we ask ourselves the number of ways to order those $N$ elements the reasoning is based on this: for the ...
2
votes
0answers
14 views

Optimal Matching Distance

I'm stuck on problem II.5.9 from Bhatia's Matrix Analysis. The problem is as follows: Let $\{\lambda_1,\dots,\lambda_n\},\{\mu_1,\dots,\mu_n\}$ by two $n$-tuples of complex numbers. Let $$ ...
2
votes
0answers
21 views

Max cut problem

I've just looked at the standard proof using the probabilistic method stating that the max cut problem has a lower bound of $|E|/2$ for any graph $G=(V,E)$. More specifically if $X$ is the random ...
0
votes
1answer
304 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
6
votes
0answers
67 views

Riddle: Assigning Students into Groups

Suppose you had a classroom with 25 students. You want to assign 6 homework assignments over the course of the term and for each of these assignments students will work in groups of 5. But you want to ...
-1
votes
1answer
16 views

Problem related to permutations [closed]

I need help with the following question. Can someone please explain as to how such questions should be approached?Thanks ! The number of ways in which six letters can be placed in six directed ...
4
votes
2answers
56 views

Binomial Theorem of Differentiation? [duplicate]

I noticed that $$\frac{d^{n}}{dx^{n}} f(x)g(x)=\sum_{i=0}^n {n \choose i} f^{(i)}(x)g^{(i)}(x)$$ and it's had me scratching for a little bit. It's easy to see how the cross terms add up but can anyone ...
3
votes
1answer
36 views

A result of Erdos: the multiplicative persistence of $n$ is at most $c\ln(\ln n)$

Multiply all the digits of a number $n$ by each other, repeating with the product until a single digit is obtained. The number of steps required is known as the multiplicative persistence of $n$. ...
0
votes
0answers
34 views

Combinations or permutations

I have 3 particles and 5 energy levels (0E,1E,2E,3E,4E). I require all possible ways such that the sum of 3 particles equals 6E. Is there a formula that would enable me to compute the possible ways?
0
votes
0answers
19 views

Can you partition a rectangle into exactly 3 congruent non-rectangular parts?

Recently I came upon the following result: Theorem (*): Let $n$ be a positive integer not equal to $1,3,5,7,9$. Then it is possible to partition a rectangle into exactly $n$ congruent non-rectangular ...
3
votes
1answer
176 views

Number of ways to add multiples of numbers from a set of k numbers while all numbers are never multiplied.

I am trying to come up with a general formula. First let me give a simple example. Let there be 3 numbers: a, b, and c. I multiply any two of them to get: 1. a*b 2. b*c 3. c*a .......[A] Exactly ...
5
votes
1answer
112 views

Evaluate complicated sum

Evaluate following sum: $$\sum_{1\leqslant i< j \leqslant m}\sum_{\substack{1\leqslant k,l \leqslant n\\ k+l\leqslant n}} {n \choose k}{n-k \choose l}(j-i-1)^{n-k-l}.$$ Hint: use combinatorial ...
0
votes
1answer
40 views

Counting and Probability String Length

Consider strings that can be made up from the set $\{a, b, c, d, e, f, \cdots, z, 0, 1, 2, \cdots, 9\}$ 1) How many strings of length 8 contain either the letter '$x$' or '$1$'? 2) What is the ...
2
votes
1answer
24 views

Family of sets without 2 disjunct elements, prove the statement

Suppose, that the $F \subseteq 2^{[n]}$ family of sets doesn't have two disjunct elements. Prove, that there is always an $F' \subseteq 2^{[n]}$ family of sets, which contains $F$, $F'$ has no ...
1
vote
0answers
39 views

Is there an upper limit to the number of times a value can occur in a superset?

Given a set of numbers $S=\{-5,6,9,3,2,-2\}$, is there an upper limit to the number of times a particular value (say $4$) can occur in the sums of all the combinations of these numbers? For example: ...
2
votes
1answer
55 views

Counting 5-point, 4-edge subgraphs of a chess board

I don't know graph theory, but I want to study this specific question for a while. I have no idea if this is a well known and studied question or not. I found it very difficult, and I don't know where ...
0
votes
1answer
22 views

Unimodality of sequence

I have to show the following: a) was pretty easy to show, however, I am not able to get something useful out of the recursive definition in b) and I have no idea how to approach c). What bijection ...
2
votes
1answer
47 views

How many non prime factors are in the number $N=2^5 \cdot 3^7 \cdot 9^2 \cdot 11^4 \cdot 13^3$.

to find non prime factors in the number $N=2^5 \cdot 3^7 \cdot 9^2 \cdot 11^4 \cdot 13^3$. First I tried finding all the factors by adding 1 to each of the exponents and then multiplying them and ...
0
votes
1answer
44 views

no. of disordered pairs of disjoint subsets

I found this question in a book. The same question has been asked before, but I want a more generalised and rigorous, so to speak, answer. The question reads- " Consider the set $S= \{1,2,3,4\}.$ ...
0
votes
1answer
58 views

What kind of tree it is? How to solve the problem?

I have a tree with following configuration: n is the number of different vertices v ($0 \lt v \le n$). Each vertice ...
1
vote
1answer
44 views

The greatest number of points of intersection of n circles and m straight lines is-

The question is about combinatorics. I have no idea on how to start solving the problem. Please guide me. $(a) 2mn+ {m \choose 2}$ $(b) \frac{1}{2}m(m-1)+n(2m+n-1)$ $(c) {m \choose 2}+2({n \choose ...
2
votes
2answers
33 views

How do you find the the sum of a list of permutations?

If you are given the digits 1, 2, 3 and 4 and then are asked to find the number of different 4-digit numbers you can make (repetition is allowed). We can multiply $4 \times 4 \times 4 \times 4 = 256$ ...
2
votes
1answer
286 views

Count ways to reach last layer

Consider directed graph which has $N + 2$ layers numbered from left to right by integers from $0$ up to $N + 1$. The leftmost ($0$) and the rightmost ($N + 1$) layers both contain only one vertex ...
1
vote
1answer
120 views

Combinatorial Marble Choosing

A bag contains $3$ red marbles, $3$ green ones, $1$ lavender one, $6$ yellows, and $4$ orange marbles. How many sets of five marbles include either the lavender one or exactly one yellow one but not ...
-4
votes
1answer
31 views

A question on basic combinatorics. [closed]

I wonder in how many ways $n$ women and $n$ men can be sat down a circular table such that no man sits beside a man and no woman sits beside a woman?
2
votes
1answer
293 views

How to prove that if n and k are integers with 1 ≤ k ≤ n, then k*(n C k)=n(n−1 C k−1) combinatorally?

I am having with combinatorial proofs. My professor says to come up with a scenario so that we can connect both sides by double counting but I am clueless.