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
17 views

Set of pairs of options that could be wrong/write

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 ...
0
votes
0answers
8 views

Mobius Funcions of the posets

For a poset, where $n = 2$ we have that two comparable points $1<2$ so $R = \{(1,1),(1,2),(2,2)\}). \ $ For two incomparable points $R=\{(1,1),(2,2)\} \ $. Now, for $n=4$ we have $1<3, ...
0
votes
0answers
12 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
60 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 ...
3
votes
1answer
630 views

Social Golfer Problem - Quintets

I wrote an article on the Social Golfer Problem, which has questions like: Each day, 16 people play Munchkin in foursomes simultaneously. How many days can they play with no two people playing with ...
2
votes
0answers
93 views
+50

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 ...
1
vote
0answers
35 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
48 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
46 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
15 views

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

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) ...
0
votes
4answers
96 views

Number of ways you can form pairs with a group of people when certain people cannot be paired with each other.

Let's say you have a group of eight people and you want to form them into pairs for group projects. There are $\frac{8!}{4!.2!}$ ways to do it. ($8!$ is the total number of ways $8$ people can be ...
3
votes
4answers
168 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
26 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
65 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
32 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
38 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 ...
1
vote
1answer
104 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
2answers
30 views

Combinatorial polynomial identity.

Can someone help me make sense of the following expression: $$f(x) = \sum_{k=0}^n (-1)^k {n \choose k} (x - k)^m$$ Where $m$ is an integer. I ran into a special case of it while solving a ...
2
votes
1answer
31 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.
24
votes
8answers
3k views

How many scientists can survive? [on hold]

Please help with a Maths competition type problem. Yesterday the aliens took 100 scientists from Earth as prisoners. They want to test how smart the humans are. The aliens made 101 headbands, ...
1
vote
0answers
21 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
41 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
21 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
61 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
0answers
47 views

Magic square with not distinct numbers

There's a 4x4 magic square: 4 0 1 0 3 0 2 0 0 3 0 2 0 4 0 1 Where 0s are different numbers, 1=1, 2=2, 3=3, 4=4. Only the rows and the columns have the same sum, ...
0
votes
2answers
30 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
16 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
303 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 ...
7
votes
0answers
53 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 ...
-2
votes
1answer
55 views

Possible Combinations of a Burger Menu [closed]

If I have a build your own burger menu which has $32$ different options on it – how many combinations are possible? To be more precise: there are $32$ yes/no choices and I guess you could have ...
-1
votes
1answer
15 views

Problem related to permutations [on hold]

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
48 views

Binomial Theorem of Differentiation?

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
31 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
33 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
16 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
172 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
110 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 ...
6
votes
3answers
267 views

How many permutations

How many permutations $\pi \in S_{2n} $ for which $\exists a\in [2n] $ such that set $\lbrace a,\pi (a),\pi ^2(a),\pi^3(a),... \rbrace $ has exactly $n$ elements. I need help to solve this.
0
votes
1answer
32 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
22 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
52 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
19 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
45 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\}.$ ...