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
1answer
10 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: ...
-1
votes
0answers
22 views

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

Say I have two sets (A and B) containing 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
27 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
29 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
14 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
16 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
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) ...
1
vote
0answers
22 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
46 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
23 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
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
2answers
36 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
18 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
50 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
28 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 [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 ...
1
vote
0answers
53 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
52 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
32 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
49 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 ...
27
votes
8answers
3k 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
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?
1
vote
1answer
47 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
68 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
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 ...
4
votes
1answer
62 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
33 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
20 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 ...
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
54 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
0answers
37 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
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 ...
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
34 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. [on hold]

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
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 ...
1
vote
0answers
50 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
32 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
43 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
3answers
59 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
24 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
35 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, ...
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 $, $$ ...
0
votes
1answer
19 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
18 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 ...
0
votes
1answer
29 views

Some men and women are randomly assigned seats at a round table and no two persons of the same sex are seated next to each other. Probability of this?

Four women and four men are assigned seats at random at a round table. what is the probability that no two persons of the same sex will be sitting next to each other?
7
votes
0answers
54 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 ...