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
10 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
0answers
6 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
10 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
2answers
11 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
1answer
13 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 ...
2
votes
0answers
46 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
10 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
30 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
24 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
12 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
45 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
24 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
25 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
17 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
16 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
29 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
76 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
56 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
0answers
20 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 ...
0
votes
0answers
10 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
45 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 :( ...
0
votes
0answers
48 views

Combining 2 numbers into a uniqe number

I am stumped on a problem, I have a set of numbers (lets say 2 numbers) A and B and i want to combine them into a unique number C where C is not reproducible by any other set thats not identical ...
1
vote
1answer
44 views

How prove this number of the methods is this $\prod\prod 4\cos^2{\frac{j\pi}{m+1}}+4\cos^2{\frac{k\pi}{n+1}}$

Question: show that an $m$-by-$n$ chessboard can be partitioned some $1$-by-$2$ the numbers of methods is $$\prod_{j=1}^{\lfloor\dfrac{m}{2}\rfloor}\prod_{k=1}^{\lfloor\dfrac{n}{2}\rfloor} ...
13
votes
6answers
536 views

Combinatorial identity with sum of binomial coefficients

How to attack this kinds of problem? I am hoping that there will some kind of shortcuts to calculate this. $$\sum_{k=0}^{38\,204\,629\,939\,869} ...
6
votes
0answers
61 views

Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If ...
0
votes
2answers
29 views

Possible 4 character passwords involving a letter and a digit.

A password consists of 4 characters, each of which is either a digit or a letter of the alphabet. Each password must contain at least ONE digit and AT LEAST ONE letter. How many different such ...
0
votes
2answers
24 views

Probability of an event happening while another doesn't

Say you have a bag with $5$ numbers $(1,2,3,4,5)$. What is the probability that I will draw a $1$ if I draw $3$ times (no replacement)? What is the probability that I will draw a $1$ if I draw 3 ...
0
votes
0answers
19 views

dimension of vector space $\frac{\langle e_{ab_1\ldots b_p}\rangle}{\langle \sum_{1\leq i\leq p}e_{ab_1\ldots \widehat{b_i}\ldots b_pc}\rangle}$

Let $p$ be a prime and $n\!\in\!\mathbb{N}$. What is the dimension of the $\mathbb{Z}_p$-module $$V_{p,n}=\frac{\langle e_{ab_1\ldots b_p};\: 1\leq a<b_1<\ldots<b_p\leq n\rangle}{\langle ...
0
votes
0answers
39 views

Presentation of 2 images in a random but counterbalanced way

Problem: For 18 trials randomly a ‘left’ labeled image or ‘right’ labeled image is shown. The first 9 trials should contain the opposite number of left images as the last 9 (a.k.a. counterbalance). ...
0
votes
1answer
26 views

How many different teams can be created between two groups?

If a company has 8 painters and 12 electricians. How many different teams can be created with 1 painter and 1 electrician? I know that the number of ways a team can be made is: $ {8 \choose 1} * ...
2
votes
3answers
235 views

Probability of no ace in a 6 card hand, given 4 are not aces.

A player is dealt six cards out of a normal deck of cards. He looks at the first four and notices there is no ace among them. What is the probability that he does not have an ace at all. This sounds ...
2
votes
1answer
48 views

Find the chance that $a^3 + b^3 \equiv 0 (\mod 3)$

We are given set of integer numbers $\{1,2, \dots N\}$. $N \ge 3$ Then perform a drawing with replacement of two elements $a$ and $b$. Problem is to find the probability of following statement holding ...