This tag is for basic 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 (5)

0
votes
0answers
6 views

Arranging identical blue and red bottles such that there are no 2 red bottles next to each other

There are 10 identical blue bottles and 5 identical red bottles. How many ways are there to arrange the 15 bottles in a row such that no two red bottles are next to each other? My approach: If the 2 ...
2
votes
0answers
15 views

Combinatorial Interpretation of a Binomial Identity

The original post due to David Peterson is here. How to establish the following Binomal identity combinatorially: $$\displaystyle \sum\limits_{k = 0}^{[n/2]}\binom{n-k}{k}2^k = ...
0
votes
0answers
4 views

Plackett-Burman designs for screening experiments

i am looking for a way to investigate the relations between deferent factors in a experiment. basically i have 4 deferent lysis buffers, for each buffer i use deferent variables high/low amount of ...
0
votes
3answers
16 views

Number of positive integers between 1 and 2300 inclusive that are relatively prime to 700.

Find the number of positive integers between 1 and 2300 inclusive that are relatively prime to 700. I have no idea how to approach this question, honestly.
1
vote
0answers
11 views

higher moments of a r.v., combinatorical problem

I'm studying the book of Rick Durrett, I want to understand the proof of the Erdös Kac central limit theorem, so I also need to understand the Lindeberg-Feller theorem: for every $n \in \mathbb{N}$ ...
1
vote
1answer
15 views

Number of different arrangements of the letters A,B,C,D,E,F

How many different arrangements are there of the letters A,B,C,D,E,F in which (a) A and B are next to each other and C and D are also next to each other? (b) E is not the last letter? (c) A is before ...
0
votes
0answers
13 views

Solution of the recurrence relation of factorial.

Well, I have seen the Stirling's approximation for the upper bound of the function f(n)=n! but I want toknow the solving process of the recurrence relation T(n)=n*T(n-1) where T(1)=1
0
votes
0answers
11 views

Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by $$\frac{k}{2n-k}{2n-k \choose n}.$$ The number of Dyck paths from the ...
0
votes
1answer
28 views

Minimum and maximum number of edges graph with 25 vertices and 6 connected components can have

Let G be a simple graph with 25 vertices and 6 connected components. Find (i) the minimum number of edges that G can have. (ii) the maximum number of edges that G can have. What I know: The maximum ...
4
votes
1answer
54 views

Prove $\sum_{k=0}^n k{n\choose k}^2 = {n{2n-1\choose n-1}}$

Give a story proof that $$\sum_{k=0}^n k{n\choose k}^2 = {n{2n-1\choose n-1}}$$ Consider choosing a committee of size n from two groups of size n each , where only one of the two groups has people ...
0
votes
2answers
21 views

Find the number of 17-digit binary sequences with more 0's than 1's.

Find the number of 17-digit binary sequences with more 0's than 1's. What I know: If there are more 0's than 1's, the cases I have to calculate for is 9 0's and 8 1's 10 0's and 7 1's 11 0's and ...
0
votes
1answer
24 views

Number of positive integer solutions

How many positive integer solutions of the equation: $x_1 + x_2 + \cdots + x_p = n$ where $x_1$ and $x_2$ are odd numbers and other $x_i$'s are even numbers ? Is there any theorm about such equation? ...
0
votes
1answer
8 views

prove that every graph with $n\ge7$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6

Question: prove that every graph with $n\ge7$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6. My proof: By induction. For n=7, the number of edges is 21=$2 ...
0
votes
1answer
15 views

Approximating a binomial coefficient using Stirling's formula

I am working on a problem of modelling a rubber molecule as a one-dimensional chain consisting of $N=N_{+}+N_{-}$ links, where $N_{+}$ points in the positive $x$-direction a distance $a$ and $N_{-}$ ...
1
vote
3answers
17 views

Probability of rolling doubles from 5 dice

If I roll five dice, what is the probability that there is a matching pair among them? This is the way I thought about the problem. Let $X$ be the random variable describing the number of occurrences ...
0
votes
2answers
24 views

fibonnaci and lucas series technique

Well i have the following two problems involving fibonnaci sequences and lucas numbers, i know that they share the same technique, but i don't have clear the procedure: $$f_n = f_{n-1} + f_{n-2}: f_0 ...
3
votes
0answers
59 views

How to prove that a double sum is always an integer?

I have verified the following double sum is always an integer for $s$ up to $1000$ via Maple. But I can not prove it. Proofs, hints, or references are all welcome. Thanks! ...
2
votes
1answer
14 views

How many sequential partitions (defined inside) are there of numbers 1…n?

So, suppose $[n] = \{1,\cdots,n\}$. A partition of $[n]$ is just any division of $[n]$ into non-overlapping sets. Suppose instead of partition $[n]$ into sets I partitioned it into sequences. So ...
0
votes
2answers
31 views

Subsets of a power set.

How many subsets T of the power set of A contain at most 2 elements if the cardinality of A is n where n is a natural number ? The number of elements in power set A = 2^n. But i dont know how to ...
0
votes
1answer
25 views

Circular permutations problem with putting objects into circle

How many options do I have if I want to put red boxes and black boxes into circle so that no two black boxes are next to each other? I have 12 red boxes and 4 black boxes. Also all two red and black ...
0
votes
1answer
14 views

Why $f^{+}(v)-f^-(v) =val(f)$ if $v$ is the source?

I'm reading Bondy/Murthy's Graph Theory: He defines $x$ as the source and $y$ as the sink, reading a bit later in the chapter, he presents this definitions: $$ f^{+}(v)-f^-(v) = \left\{ ...
0
votes
2answers
49 views

Computing $C_0^2+C_1^2+C_2^2+C_3^2+ \cdots +C_n^2$

If $C_k$ denotes binomial coefficient of choosing $k$ objects from a set of $n$ objects how to calculate this: $$C_0^2+C_1^2+C_2^2+C_3^2+\cdots +C_n^2$$
-1
votes
0answers
27 views

Combinatorics Review; Discrete Math

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
0
votes
1answer
33 views

Problem Solving Involving Permutation

Find the number of 6-digits number with no 3 consecutive number with same digits. Note that 0 might be the first number. I have tried to find the number with no pairs, 1 pairs, 2 pairs and 3 pairs. ...
2
votes
1answer
18 views

Counting Review; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
0
votes
1answer
17 views

Counting Problem; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
0
votes
0answers
17 views

How should i go about proving an expression of this kind?

Lets say i have a complete bell polynomial that is equal to a summation such that $$ B_n(d_1,d_2,\cdots,d_n) = \sum_{k=0}^{n}[g(x)^{-k} h(k)] $$ Where $d_n = \frac{d^n}{dx^n}[f(x)\ln(g(x)]$ and ...
0
votes
1answer
30 views

Counting Question; Discrete Structure

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
1
vote
1answer
21 views

Please explain counting; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
1
vote
1answer
40 views

Combinatorics- monotonic subsequence

For each natural number $n$, find a sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms. I've been stuck on this for a while. Can somebody please point me ...
-3
votes
0answers
11 views

Problem in Kernerl of Digraphs [on hold]

Prove that every digraph that is not kernel perfect contains a critical kernel perfect digraph. Where: A kernel K of a digraph D is a subset of D that satisfies: (1) Every pair of vertex in this ...
1
vote
1answer
17 views

Find the chance that subset $B$ is distributed evenly between $(A_1,A_2,A_3)$

We are given set $A$ which is divided to the 3 parts ($A_1$,$A_2$, $A_3$). $|A| = n = 9k$. For $i,j = 1,2,3;\space \forall i \ne j : A_i \cap A_j = \emptyset; \space\space |A_i| = \frac n 3$. ...
2
votes
1answer
32 views

Combinatorics, dividing objects into groups.

Assuming we have got 5 horses, that are competing in a race, and assuming 2 different horses can arrive at the exact same time. How many possibilities there are for outcomes? for 3 horses for example ...
3
votes
1answer
78 views

Are there non-equivalent cardinal arithmetics?

‎Generalizing a concept in mathematics is always a problematic situation. In most cases there are several ways to generalize a notion and it is not easy to decide if a particular generalization is ...
0
votes
0answers
29 views

Multi-ruled combinatorics problem (need this for my lab)

I need to know this for practical purposes and not homework, learning etc.. Say I have 3 electrodes A,B and C. Say I also have 3 electrolytes A,B and C. If electrode A has to be in electrolyte A, ...
-2
votes
2answers
57 views

Combinatorics homework problem [on hold]

In how many ways can $23$ different books be given to $5$ students so that $2$ of the students will have $4$ books each and the other $3$ will have $5$ books each?
4
votes
2answers
58 views

How many words can be written with $aabbbccdd$ such that no two equal letters are adjacent?

I'm trying to count this using the principle if inclusion-exclusion. I've done the following: Counting the number of permutations of $aabbbccdd$. $9!$ Counting the number of ...
0
votes
1answer
30 views

how to place k rooks on the shaded squares of a m×n grid-like board

I’m given a m×n grid-like board and there are some shaded squares in every row of the board. I have to place one or more rooks on the shaded squares in such a way that no two rooks attack each other. ...
0
votes
1answer
30 views

How many ways can one “fit” $m$ non-overlapping sub-segments of length $k$ into a segment of length $n$?

Given discrete one-dimensional space (a "segment") of length $n$, how many ways can one fit a $m$ non-overlapping sub-segments of length $k$ in this space? This seems like a very simple question, but ...
1
vote
0answers
13 views

Derangement of multiset using recursive relation

Recently,I have read articles on derangement but now I want know about how to derange a multiset. By using inclusion-exclusion one can find out the number of ways to derange a multiset. I'm looking ...
1
vote
2answers
37 views

let $D_n$ be the number of permutations of $\{1,2,3,…n\}$ which leave no element fixed.

Let $n\geq2$ and let $D_n$ be the number of permutations of $\{1,2,3,\dots,n\}$ which leave no element fixed. How to write an expression for $D_n$ in terms of $D_k$? I don't know how to start. Please ...
0
votes
1answer
21 views

Question about some properties of combinatorial structures

Consider $\mathcal A$ as the set of perfect matchings in the complete bipartite graph $K_{n,n}$ and let $i$ be an edge of $K_{n,n}$. Let $$ B_i=\{a\in \mathcal A: \hbox{matching }a\hbox{ has edge ...
1
vote
0answers
14 views

Idempotent generators of the four binary QR codes of length 7

I have a coding theory assignment and I thought it would be a good idea to double check before I hand it in. I'm asked to find the idempotent generators of the four binary QR codes C1, C2, C3, C4, of ...
1
vote
1answer
100 views

A sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms

I'm following a Combinatorics course at the moment, and have recent proved the Erdős–Szekeres Theorem (or, at least, some variation of): A sequence of length $n^2 + 1$ either contains an ...
0
votes
0answers
21 views

Do these statements prove this formula?

$$ \frac{d^n}{dx^n}[g(x)^{f(x)}] = g(x)^{f(x)} B_n(d_1,\cdots,d_n) $$ Calling $$ d_n = \frac{d^n}{dx^n}[ln(g(x))f(x)] $$ Since faa di bruno's formula states $$ \frac{d^n}{dx^n}[f(g(x))] = ...
1
vote
1answer
47 views

Unique permutations from set with repetitions

I am new to combinatorics and might ask a trivial question: There are $69$ different items, each present $4$ times. From this total of $276$ items, $20$ should be picked at random. I need the formula ...
0
votes
1answer
25 views

Is my idea of incoming/outgoing arcs correct?

I'm reading Jungnickel's Graphs, Networks and Algorithms. I've met the following lemma: I know that $e^{-}$ are the incoming vertices and $e^{+}$ are the outgoing vertices. Then I've tried to ...
0
votes
2answers
20 views

There are eight males and 12 females in a certain club. In how many ways can a committee of five be chosen if it is to consist-

There are eight males and 12 females in a certain club. In how many ways can a committee of five be chosen if it is to consist Entirely of Males? Entirely of Females? 2 males and 3 females?
0
votes
1answer
26 views

In how many distinct ways can a group of letters be ordered? [on hold]

In how many distinct ways can the letters aaabbbbb and aaabbbbbcccc be ordered?
0
votes
1answer
51 views

Combinatorics-graph colouring [duplicate]

Show that if $K_9 $is coloured red and blue and contains no red triangle and no blue $K_4$, then every vertex must have red degree $3$ and blue degree $5$. I have absolutely no idea how to proceed :( ...