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

How can I prove that a function is 1-1 and onto in Combinatorial Proof

I studied the way of combinatorial proof for a=b. That is, 1) Find sets A and B such that |A|=a, |B|=b 2) Construct a bijection between A and B Then |A| = |B|. But I have a difficulty in proving a ...
3
votes
4answers
38 views

Problem involving binomial coefficients where p+q=1

If $p+q=1$, then show that $$\sum_{r=0}^n r^2 \binom {n}{r} p^r q^{n-r}=npq+n^2p^2$$ I was able to solve this by differentiating the expression twice and then relating the given variables. But the ...
1
vote
0answers
26 views

Solvability if two pieces of the fifteen puzzle are identical?

It's known that only half of all the permutations in the fifteen puzzle can be solved (in the sense of recovering the sequential order of numbers, with the empty slot in the lower right corner), for ...
0
votes
1answer
45 views

A combinatorial proof of an identity involving Euler’s $ \phi $-function.

My assignment is to prove this: Problem. For an integer $ n \geq 1 $, show that $ \displaystyle n = \sum_{d|n} \phi \! \left( \frac{n}{d} \right) $. I have a hint: Define an equivalence relation ...
0
votes
0answers
35 views

What is the probability of getting STRAIGHT FLUSH in a $13$-card poker game?

What is the probability of getting STRAIGHT FLUSH in a $13$-card poker game? Here is my attempt: A straight flush is five cards in sequence and of the same suit, but not ace king queen jack ten. ...
2
votes
1answer
39 views

What is the probability of getting FOUR OF A KIND in a $13$-card poker game?

What is the probability of getting FOUR OF A KIND in a $13$-card poker game? Here is my attempt: The setup for the required poker hand would either be: $$AAAABCDEFGHIJ,$$ $$AAAABBBBCDEFG,$$ or ...
0
votes
0answers
27 views

Algebraic or combinatorial proof that $(\sum_{n=0}^\infty {\frac{1}{m} \choose n} z^n )^m = 1+z$ as formal polynomials

I know how to prove this using analytic techniques (just by using derivatives of $(1+z)^{\frac{1}{m}}$, and basic facts about power series), but I was wondering if there's any way to prove this using ...
0
votes
0answers
15 views

Associated vectorial matroid and rank

How can I identify the associated vectorial matroid and determine the rank of this matroid? If I have $E$ a set of columns of ma matrix A over a field $K$. $\mathcal{F}=\{F \subseteq E \mid \text{the ...
3
votes
2answers
108 views

Permutations of numbers $1, 2, 3,\dots,n$

How many permutations do the numbers $1, 2, 3,\dots,n$ have, a) in which there is exactly one occurrence of a number being greater than the adjacent number on the right of it? b) in which there are ...
2
votes
1answer
22 views

A basic combinatorics problem: number of solutions of form $ \pm 1 $ to and additive equationn

In my combinatorics and discrete mathematics class I was asked this question which I cannot seem to be able to solve: Let us define N variables $ \{ s_k \}_{k=1}^{N} $ each having two possible ...
0
votes
5answers
66 views

How to find the number of strings with even and odd number of zeroes? [closed]

Any hints please for this question ? Im stuck.How to find the number of strings with even and odd number of zeroes ?
0
votes
1answer
31 views

Of Balls in Bins in Different Sections with Caps

Problem: There are $19$ bins: $7, 5, 7$ in the left, centre and right sections respectively. There are $8$ balls, some or all of which are to be put into these bins with the following ...
1
vote
0answers
18 views

Ranking players and puzzles from performance in a single player game format

I have a 1000 crossword puzzles and a 1000 solvers - each individual is assigned a 100 arbitrary puzzles to solve (so each solver gets exactly 100 puzzles but each puzzle could have 1-1000 solvers) - ...
1
vote
1answer
29 views

On the multiplicity of the eigenvalue 0 of the adjacency matrix?

Preliminaries: -Laplacian matrix of graph $G$ is defined as follows: $$L=D-A $$ where $D$ is the degree matrix and $A$ is the adjacency matrix of the graph. -The algebraic connectivity of a graph ...
0
votes
1answer
30 views

characteristic cone of polyhedral

Let $$Q=\{x ∶ Ax ≤ b \}≠∅$$ If $Q = P + C$, where $P$ is a polytope and $C$ is a polyhedral cone, prove that $$\{y|Ay ≤ 0\} = \{y|x + y ∈ Q, ∀ x ∈ Q\}$$ The cone $C = \{y|Ay ≤ 0\}$ is ...
0
votes
0answers
53 views

min-max problem

Hello to everybody: I'm trying to prove that : Let $A$ be the incidence matrix of a clutter (simple hypergraph) $C$. Prove that the vertex covering number and the matching number of $C$ satisfy: ...
0
votes
1answer
30 views

Placing k sticks of length d on a space of length L

A total of $k$ identical one-dimensional sticks of length $d$ are placed in a one-dimensional space of length $L$ (where $k\cdot d\leq L$). The values of $d$ and $L$ are integers and the sticks must ...
2
votes
0answers
55 views

Groups of 3 from 12 numbers

I need groups of $3$ numbers from $12$ without any repetition and I need $4$ sets of these groups of $3$ numbers. e.g. $1,2,3~~~4,5,6~~~7,8,9~~~10,11,12$ is the obvious first set of groups of $3$ ...
0
votes
2answers
36 views

What is the probability of getting NO PAIRS in a $13$-card poker game?

What is the probability of getting NO PAIRS in a $13$-card poker game? Here is my attempt: The setup for the required poker hand would be: $$ABCDEFGHIJKLM$$ where $A, B, \ldots, M$ are distinct ...
0
votes
1answer
27 views

Filling k positions with objects from $n$ different types

There are $n$ different types of objects and $k$ positions where an object can be placed. How can I determine the number of ways in which these $k$ positions can be filled by using objects of these ...
0
votes
1answer
27 views

Combinatorial Geometry explanation

I do not understand what is going on in $(4)$: for every flat $E \in \mathcal F$, $E \ne X$, the flats that cover $E$ in $\mathcal F$ partition the remaining parts. What is meant by "the flats ...
2
votes
0answers
38 views

How to find the largest possible value when moving values between N nodes

I stumbled upon an interasting combinatorial question while playing a game of Magic: the Gathering. Take N nodes, each one with an assigned value. Each node's value begins at 1, and may increase as ...
8
votes
2answers
154 views

What is the subword complexity function of this infinite word?

Let $w_{0}$ denote the finite word $01$ in the free monoid $\{ 0, 1 \}^{\ast}$, and for $i \in \mathbb{N}$ define $w_{i}$ as the word obtained by adjoining the first $\left\lfloor ...
-1
votes
1answer
28 views

How many combinations are possible: English alphabet A-Z and digits 0-9 in a set of 12. [closed]

How many combinations can be made from a 12 set string of letters and number that can be repeated and used more than once in any order. Ie- TD3GD3BK6K7T and would be different than T7K6KB3DG3DT or ...
4
votes
1answer
27 views

Transversals of Latin Squares

According to this thesis, page $28$, the following Latin Square has $3$ $0$-s transversals: $$\begin{bmatrix}1 & 2 & 3 & 4 & 5\\ 2 & 4 & 1 & 5 & 3\\ 3 & 5 & 4 ...
0
votes
1answer
20 views

Let S be a set of k elements, where k is a whole number. Suppose n is not an element of S. Show that S union s has k + 1 elements.

Let S be a set of k elements, where $$k \in \omega$$ Suppose $$n \notin S$$Show that $$S \cup \{n\}$$ has k + 1 elements. I'm honestly last as to where I should start. I was thinking of maybe a ...
1
vote
2answers
31 views

Combinations equation solving with factorial

I was trying to solve the equation using factorial as shown below but now I'm stuck at this level and need help. $$C(n,3) = 2*C(n,2)$$ $$\frac{n!}{3!(n-3)!} = 2\frac{n!}{2!(n-2)!}$$ $$3! (n - 3)! = ...
1
vote
1answer
46 views

How many arrangements of $MATHEMATICAL$ are there in which $ME$ appear together but the $ME$ is not immediately followed by an $A$?

How many arrangements of $MATHEMATICAL$ are there in which $ME$ appear together but the $ME$ is not immediately followed by an $A$? (no MEA) The answer is $(11!)/(3!2!) - (10!)/(2!2!)$ I am confused ...
3
votes
2answers
62 views

How many ways are there to arrange $12$ (distinct) people in a row so that Dr. Tucker is $3$ positions away from Dr. Stanley?

How many ways are there to arrange $12$ (distinct) people in a row so that Dr. Tucker is $3$ positions away from Dr. Stanley (i.e., $2$ people are in between Dr. Tucker and Dr. Stanley), e.g., _ _ _ _ ...
0
votes
0answers
24 views

The weighted sum of all pairwise paths in a tree as a determinant

Let $T$ be a weighted tree, with weights denoted by $w_{ij}$ for all edges $e = (i,j)$ in $T$. Define the weight of a simple path $P$ in $T$ by $w(P) = \prod_{(i,j) \in P} w_{ij}$. Is it possible to ...
0
votes
2answers
47 views

How many arrangements of length $12$ formed by different letters chosen from the $26$-letter alphabet that contain the five vowels $(a,e,i,o,u)$?

How many arrangements of length $12$ formed by different letters (no repetition) chosen from the $26$-letter alphabet are there that contain the five vowels $(a,e,i,o,u)$? I know that there are $12$ ...
-2
votes
0answers
27 views

Finding possible score for tests

V&V team is waiting for a set of blinded (i.e. they don’t know the results) CTNG clinical samples to process and invent a game to pass time by. They decide to guess the results of the ...
1
vote
2answers
43 views

Proving $1 \cdot 2 + 2 \cdot 3 + \cdots + n(n + 1) = 2\binom{n + 2}{3}$by math induction?

I am working on a problem, but I don't know whether or not to use math induction on it. Here's the problem: Prove that for all integers $n \geq 1$, $$1 \cdot 2 + 2 \cdot 3 + \cdots + n(n + 1) = ...
3
votes
4answers
44 views

Using a combinatorial argument

I am having some difficulty with this problem: Use a combinatorial argument to show that $$\binom{m + n}{r} = \binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r - 1} + \dots + ...
0
votes
0answers
77 views

Given an edge in a planar graph, can we find a function that returns its face neighbors?

I have a planar graph with vertices labeled as in the figure below. The edges are labeled counter clockwise with respect to a square (see the list below). Does there exist a function $F$ such that ...
3
votes
2answers
44 views

Proving $\sum_{i=0}^n \binom{n}{i} = 2^n$ by math induction

I am having some trouble using math induction to prove the following problem: $$\sum_{i=0}^n \binom{n}{i} = 2^n$$ Where n $\geq$ 0 I know the first thing with math induction is substitute the base ...
1
vote
1answer
61 views

$10$ people are standing in a queue when three new checkouts open. In how many ways can the three new queues be formed?

Problem: $10$ people are standing in a queue when three new checkouts open. 8 people rush to the new checkouts and the new queues end up with at least two people in each. In how many ways can ...
3
votes
1answer
78 views

How to prove that $n! = n^n - C_{n,1} (n-1)^n +C_{n,2} (n-2)^n - \cdots $?

How to prove that $n! = n^n - C_{n,1} (n-1)^n +C_{n,2} (n-2)^n - \cdots\,{} $? I faced this problem when trying to find the number of onto functions possible from one set having n elements to ...
1
vote
2answers
24 views

Four six-sided dice are rolled. What is the chance that at least one is a 2? What is the chance that the first is a 1 given that at least one is a 2?

So far I have this: What is the chance that at least one is a 2? There is $\frac{5}{6}$ that you will not get any 2 on the four dices. From this we get $\frac{5^4}{6^4}$ The probability of getting ...
1
vote
1answer
30 views

Conditional probability with “at least”

We split 8 colored (and distinguishable from each other[each ball is unique]) balls to 4 kids, 2 balls for each kid. There are 2 blue balls, 2 red balls, 2 yellow balls, 2 green balls [still each ball ...
0
votes
2answers
28 views

You toss three coins. Is the event that there is at most one tails independent from the event that there is both a heads and tails present?

You toss three coins. Is the event that there is at most one tails independent from the event that there is both a heads and tails present? I am new to probability and I have no idea what I am ...
8
votes
3answers
1k views

Probability of three dice falling in the same quadrant of a box

This is surely really basic for most people here but it's tripping me up. You get a box and draw lines to split it up into 4 parts. I got asked what the probability was that when rolling three ...
0
votes
1answer
24 views

Finding the minimum number of specimens that must be tested

"Jen requests processing of a large set of clinical specimens. In a set of 2000, she would like the following to occur - 1700 specimens tested for CT, 1900 for NG, 1600 for Trichomonas and 1350 for ...
0
votes
1answer
39 views

Maximum matchings in a bipartite graph

How can I show that a bipartite graph $G=G(X,Y),V(G)=X \bigcup Y$ has a perfect matching iff $\mid N_{G}(S)\mid \geq \mid S\mid $ for all $S \subset V(G)$, where $V(G)$ are the vertices of $G,$ $S$ ...
1
vote
0answers
22 views

Finding asymptotycs of partition function

I have been stuck in this problem and have no idea of how to solve it. I have a hint from the book but don't really see how to use it. Any suggestion or hint would be really appreciated. Thanks! ...
1
vote
1answer
38 views

Is there always a way to pick a card from each number?

In a standard deck of cards, there are $n=13$ numbers, each of which appears $k=4$ times. Suppose the cards are distributed to $2k=8$ piles that are laid in an array of $k$ rows, 2 piles in each row. ...
0
votes
1answer
32 views

Recurrence relation for the number of ternary strings of length n that contain either two consecutive 0s or two consecutive 1s.

I'm having trouble with this one...I understand others have posted this it seems. However, I don't understand those answers/others some incorrect. I first tried thinking of the different ways this ...
-2
votes
1answer
32 views

8 teams and X amount of games, Need to play each game and each team [closed]

I'm planning an event with 8 teams and an undecided amount of games. How many games would I need, and what would the set up look like, if each team plays EVERY other team only once, and plays EVERY ...
0
votes
0answers
12 views

Bijection Young Tableau

The problem I have is the following: In part i) we define the sequence $a_k$ for $1 \leq k \leq 2n$ by $a_k:=+1$ if $k$ is in a row 1 of a Young Tableau of shape $(n,n)$ and $a_k:=-1$ if $k$ is in ...
0
votes
1answer
26 views

What is the probability to pick a collection of 12 balls as above with at least 2 red balls and exactly one blue ball?

What is the probability to pick a collection of 12 balls as above with at least 2 red balls and exactly one blue ball? Here is my solution ${{12+3-1}\choose{12-2-1-1}}$ Is this correct?