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

Jacobi Identities

Can anyone guide me how can I prove these two identities? a)$$\prod_{n=1}^{\infty}\frac{1-q^{2n}}{1-q^{2n-1}}=\sum^{\infty}_{n=1}q^{n(n+1)/2}$$ b) ...
0
votes
0answers
19 views

Is the number of different patterns possible permutations or combinations?

I was given the below question. "Linus is taking a true or false test and seems to be guessing every answer. If there are $20$ questions how many different "patterns" are possible?" I solved this ...
2
votes
1answer
20 views

Counting unique states in 3d tic tac toe with 6 moves

I am doing some probability review and came across in interesting question I can't quite figure out how to do. The question is asking for a 3x3x3 tic tac toe board with three players a,b,c with taking ...
6
votes
3answers
271 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.
2
votes
4answers
407 views

How many ways are there for $2$ teams to win a best of $7$ series?

Case $1$: $4$ games: Team A wins first $4$ games, team B wins none = $\binom{4}{4}\binom{4}{0}$ Case $2$: $5$ games: Team A wins $4$ games, team B wins one = $\binom{5}{4}\binom{5}{1}-1$...minus $1$ ...
1
vote
0answers
13 views

Methods of solving nonlinear systems of equations derived from combinatorial problem

I'm trying to find a way to generalize the expression of polynomials of degree $n-1$ such that $$ k_1+k_2x+k_3x^2+k_4x^3+\dots+k_nx^{n-1}=\frac ...
1
vote
3answers
25 views

How many different possible expressions can I have?

I have three numbers $a,b$ and $c$ How many different additions can I have ? $a + a + a = 3a$ $a + a + b = 2a + b$ However, $a + b + a =2a + b$ which is the same addition as above so I neglect it. ...
1
vote
0answers
8 views

Steiner Quadruple System

If a $SQS$ of order $n$ exists, with $n\ge2$ then $n\equiv2$ or $4(\mod6).$ A Steiner quadruple system SQS is a pair $(X,B)$ where $X$ is a set, and $B$ a collection of $4$-element subsets of $X$ ...
1
vote
2answers
31 views

How many words with letters from the word ABRACADABRA if they must end in a consonant and $d$ must be after $r$.

How many words with letters from the word ABRACADABRA if they must end in a consonant and $d$ must be after $r$. What I did: I have $A:5$ $B:2$ $R:2$ $C:1$ $D:1$ If the words must end in a ...
28
votes
9answers
4k 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 ...
-1
votes
0answers
27 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 = ...
3
votes
1answer
52 views

Working with finitely presented groups in GAP

This is more of a question specifically about how GAP handles calculations with finitely presented groups rather than about group theory. I have several finite group presentations that I would like ...
2
votes
2answers
42 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 ...
-1
votes
0answers
14 views

Number of infinite repeated sequences with perod at most k? [on hold]

So say we want to count all infinite length repeated sequences of the form $s_1, s_2, s_3, \dots $ where each $s_i \in \{1, 2,\dots m \}$, which are repeating with period at most $k$. So eg., m=3 and ...
3
votes
3answers
113 views

Find the number of ways to form 15 teams out of 15 men and 15 women.

In how many ways can 15 teams be formed, each consisting of a man and a woman, from 15 men and 15 women. This looks like the same problem as finding the number of bijective functions from a set $A$ ...
0
votes
0answers
16 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
19 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: ...
4
votes
1answer
74 views

What is this sequence of all permutations with gaps permissible [duplicate]

Let there be a sequence $a_1, a_2, a_3,...,a_n$ that represent some actions that you know are required to solve a problem. However, you do not know what order these actions need to be taken to solve ...
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, ...
1
vote
0answers
55 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
1answer
29 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 ...
1
vote
2answers
373 views

Find recurrence relation for ternary strings that don't have substrings 00, 01 and last symbol is not 0

I am preparing for my finals for discrete mathematics and I came across this exercise in textbook. Let $s_{n}$ denote all ternary strings of length $n$, such that any string in $s_{n}$ does not ...
2
votes
1answer
30 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
98 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
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 ...
3
votes
2answers
61 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
632 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
115 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 ...
0
votes
0answers
39 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
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, ...
0
votes
1answer
51 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
103 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 ...
4
votes
4answers
172 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
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 ...
6
votes
2answers
69 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
35 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
49 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
105 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
33 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
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
48 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 ...
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
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 $$ ...