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

Combinatorial identity binomial coefficients [duplicate]

How to prove that $$ \binom{m}{p} = \sum_{j=0}^q \binom{q}{j}\binom{m-q}{p-j}\;?$$
0
votes
1answer
25 views

Counting spanning trees in labelled graphs

I have some troubles with counting spanning trees, it seems completely abstract to me. First one is cycle with n vertices - it's just n, because we can move each number n times like so: ...
2
votes
1answer
55 views

How do I express, algebraically, this comparison of two sets of sets?

Say I have two sets ($A$ and $B$) containing three sets of the same integers. For example: $A_1 = \left\{{1,2}\right\}$, $A_2 = \left\{{3}\right\}$, $A_3 = \left\{{4,5,6}\right\}$ $B_1 = ...
0
votes
1answer
30 views

How many poker hands have exactly two pairs?

I found an interesting solution to the combinatorial question of "How many poker hands have exactly two pairs?" and I cannot figure out (or find) the reasoning of the solution. The answer I found in ...
2
votes
1answer
33 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 ...
0
votes
1answer
18 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
17 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 ...
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) ...
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
50 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
26 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 ...
0
votes
2answers
32 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
2answers
45 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
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 ...
2
votes
1answer
66 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, ...
2
votes
1answer
32 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 ...
-1
votes
1answer
15 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 ...
1
vote
0answers
62 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, ...
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
35 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
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 ...
33
votes
7answers
5k views

How many scientists can survive?

Yesterday the aliens took 100 scientists from Earth as prisoners. They want to test how smart the humans are. The aliens made 101 headbands, numbered from 1 to 101. On the contest day, they throw ...
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?
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$. ...
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
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 ...
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
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 ...
0
votes
1answer
21 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 ...
6
votes
3answers
273 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
57 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 ...
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
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 ...
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$ ...
0
votes
2answers
36 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 ...
-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?
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 ...
1
vote
0answers
56 views

Blocks of consecutive natural numbers

Let a < b be natural numbers. Prove that every block of b consecutive natural numbers contains two distinct elements whose product is divisible by ab. Suppose now a < b < c are natural ...
2
votes
1answer
36 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.
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 ...
1
vote
0answers
41 views

Intersecting Family of subsets of size k

Suppose that $k$ divides $n$. Then an intersecting family $F$ of $k$-subsets of an $n$-set $X$ has size at most $n-1\choose k-1$. The prove goes as follows: Let $B$ be the set of all partitions ...
2
votes
3answers
66 views

The number of choices of 3 kinds of crust and up to 6 distinct toppings

David has a pizza shop. There are 3 kinds of crust and 6 different toppings he can chose from. If customers can have as many toppings as they'd like but may not order double of one topping, how ...
0
votes
1answer
28 views

For a solution of linear recurrence relation, $\lim_{n\to\infty}a_n^{1/n}$ is a zero of a related polynomial

On page 134 of J.H. van Lint's book A Course in Combinatorics, it says from $a_n=5a_{n-1}-7a_{n-2}+4a_{n-3}$ $(n\ge5)$, we find that $\lim_{n\to\infty}a_n^{1/n}=\theta$, where $\theta$ is the ...
1
vote
1answer
37 views

2x2 grid game problem

A friend of mine is attempting to make a webpage that has a game for a 2x2 grid that is similar to the old North, South, East, West game. I cannot for the life of me figure this out. Essentially, ...
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 $, $$ ...
0
votes
1answer
22 views

Rewrite the sum of the products by interpretation

By interpreting what the following sum is counting and then counting the same object in a different way, rewrite the following sum as a product of two terms (without any sum): $\sum\limits_{k=m}^n$ ...
0
votes
0answers
19 views

How to find the number of words of length $h$ in a subsets $A$?

Let $L=\{0,1\}^*$ (the set of binary words on $0$ and $1$), Given a tuple of words $(w_1,w_2,\cdots,w_n)\in L^n$ and a function $\sigma:[1,n]\to [1,n]$ define the following set: ...
0
votes
2answers
24 views

Permutations; group of 5 boys, 10 girls. What's the probability the person the 4th position is a boy?

Problem description: A group of 5 boys and 10 girls is lined up in random order -- that is, each of the 15! permutations is assumed to be equally likely. What is the probability that the person in ...