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 (4)

3
votes
0answers
109 views

Binomial Coefficients optimization

Given n and R, I have to find the minimum value of k such that: $${(2^n)-1 \choose k}\bmod(2^n)==R$$ Where $k = \{0, 1, 2, \dots, 2^n-1\}$ Here ${n \choose k}$ is the binomial coefficient ...
1
vote
1answer
82 views

extended linear codes over the field $\mathbb F_q$

Suppose we extend the $[n,k]$ linear code $C$ over the field $\Bbb F_q$ to the code $C'$, where $$ C' = \{(x_1,\ldots ,x_n,x_{n+1})\in \Bbb F_q^{n+1} : (x_1,\ldots,x_n) \in C \text{ and } ...
2
votes
1answer
311 views

Sphere packing bound for binary linear codes of length 15 and minimum distance 3

My question is about bounds and linear codes: a) Use sphere packing bound (Hamming bound) to get an upper bound on $A_2(15,3)$. What linear code meets this bound? Is this code perfect? b)can we do ...
5
votes
1answer
75 views

Show that $\frac{1}{1+x}H(\frac{x}{1+x})=\sum^\infty_{k=0}[\Delta^kh_0]x^k$

For a sequence $\{h_n\}_{\geq 0}$, let $H(x)=\sum_{n\geq0}h_nx^n$. Show that: $$\frac{1}{1+x}H(\frac{x}{1+x})=\sum^\infty_{k=0}[\Delta^kh_0]x^k$$ What I did was that by proving the $$\Delta^k ...
1
vote
2answers
92 views

Proving the formula holds for the $k$-th order differences of a sequence.

Prove that the following formula holds for the $k$-th order differences of a sequence $\{h_n\}_{n\geq0}$: $$\Delta^kh_0=\sum^k_{j=0}(-1)^{k-j}{k \choose j}h_j$$ by using induction on $k$.
1
vote
1answer
27 views

Finding a formula for $\sum^n_{k=0}h_k$

Let the sequence $\{ h_n\}_{n\geq}$ be defined by $h_n=2n^2-n+3$. Determine the difference table, and find a formula for $$\sum^n_{k=0}h_k$$
1
vote
1answer
69 views

Have to prove in a combinatorial and with pascal's pyramid

I have to prove that: $$\sum_{k=0}^{(\lfloor \frac{n}{2} \rfloor)} { n \choose 2k} = 2^{n-1}$$ in two ways: A combinatorial way, and with the help of the Pascal Pyramid. For the combinatorial way I ...
4
votes
2answers
103 views

Probability that a string of $5$ characters from set$\{a,b,c,d,e,f\}$ contains exactly one '$a$', given that it contains at least one vowel

This is a past paper exam question. It doesn't have a mark scheme, so I was hoping somebody could check this answer for me. It's non-calculator, but I don't expect that affects the method used. My ...
4
votes
1answer
214 views

In the marriage problem, if each girl knows at least $m$ boys, then there are at least $m!$ ways to arrange the marriages.

I'm finding problems concerning Hall's theorem very difficult even when they're not. (See here for example. I'm sure I wouldn't have come up with the solution in a million years even though it's ...
1
vote
2answers
341 views

What is the expected size of the largest strongly connected component of a graph?

Given a directed graph with n vertices and the probability of any edge existing being p, what is the size of the largest strongly connected component in the graph? What if its undirected graph? Can we ...
4
votes
2answers
175 views

Asymptotic behavior of sum of squares of combinatorial numbers with a weight.

Consider the following sequence of natural numbers, $$M_n = \sum_{k=0}^n \binom{n}{k}^2 4^k$$ We can interpret $M_n$ as the cardinality of the set $X$ of $(2\times n)$-matrices with entries in ...
3
votes
1answer
109 views

The Mathematics of Shuffling Poker Chips?

First, I must say that I do not have an advanced understanding of mathematics and I don't know what category this question belongs in. This is just a question that I have been thinking about recently. ...
13
votes
3answers
661 views

Exceptional books on real world applications of graph theory.

What are some exceptional graph theory books geared explicitly towards real-world applications? I would be interested in both general books on the subject (essentially surveys of applied graph ...
2
votes
1answer
194 views

Total possible no. of license plates

I following Susanna Epps book for discrete math & I am not able to solve the following : In another state, all license plates consist of from four to six symbols chosen from the 26 letters ...
5
votes
2answers
607 views

How many 9 letter strings are there that contain at least 3 vowels?

I'm studying for my exams and stuck on this one question. The way I'm thinking of doing this is by: $$26^9 - \binom{26}3-\binom{26}2-\binom{26}1-\binom{26}0= 5,429,503,676,728$$ But that seems ...
0
votes
3answers
465 views

Finding Particular Solutions to Non-Homogeneous Recurrence Relations

Could anyone assist me in solving the following recurrence relations? $a_n = 3a_{n-1} - 2a_{n-2} + 2^n n^2$ $b_n = -nb_{n-1} + n!$ Specifically, I am not sure how to find the particular solutions ...
1
vote
1answer
128 views

Total number of parts in the all partitions of $n$

Let's denote $N_k(n)$ as the number of partitions $n$ into at most $k$ parts. Prove that the total number of parts in the all partitions of $n$ is equal to: $$\sum_{a=1}^n \sum_{b=1}^{\lfloor n/a ...
1
vote
1answer
84 views

The marriage problem with the constraint that a particular boy has to find a wife.

Here I'm considering the version of the marriage problem in which there can be more boys than girls. Suppose there are two sets, one of boys and one of girls, the two satisfying Hall's condition for ...
2
votes
0answers
100 views

Problem involving set systems - combinatorics.

The question is as follows: $A \subset \mathbb{P}(X)$ is called a cross-cut if for every $B \subset X$ there exists $A' \in A$ with $B \subset A'$ or $A' \subset B$. Prove that every cross-cut ...
-2
votes
1answer
200 views

Find a form for $Q(x)$ as an infinite product of polynomials

Let $q(n)$ be the number of partitions of $n$ so that no part appears three or more times. For example, $q(8) = 13$ Let $Q(x) = \sum\limits_{n=0}^\infty q(n) x^n$ be the generating function for ...
-6
votes
1answer
751 views

How to find a Recurrence Relation from a word problem?

Suppose you have 5 kinds of wooden blocks: red blocks which are 2 inches high, blue blocks which are 2 inches high, green blocks which are 2 inches high, yellow blocks which are 3 inches high, and ...
0
votes
2answers
376 views

Probability of One pair hand in Poker 5 cards

I have been working on the problem of probability of poker hands, I have been able to calculate the probability of each hand except one pair and high card hand. Here is what I have P1 P2 X1 X2 ...
3
votes
1answer
109 views

Number of “passing” paths in football

In a football match, $M$ decides to do $N$ passes with $K$ players helping him out, so that $M$ could get the ball back at last to make the goal. In how many ways can $M$ do this? Examples: If ...
2
votes
2answers
189 views

Generating functions. Number of solutions of equation.

Let's consider two equations $x_1+x_2+\cdots+x_{19}=9$, where $x_i \le 1$ and $x_1+x_2+\cdots+x_{10}=10, $ where $ x_i \le 5$ The point is to find whose equation has greater ...
0
votes
3answers
894 views

Arrangements and Selections with Repetitions

How many arrangements of the letters in PEPPERMILL are there with a) The M appearing to the left of all the vowels? b) The first P appearing before the first L? For part a, I have know that the total ...
1
vote
2answers
51 views

Sum of the selected elements of matrix is $255$

A $5\times 10$ matrix is given: $$\begin{pmatrix} 1 & 6 & 11 & 16 & 21 & 26 & 31 & 36 & 41 & 46\\ 2 & 7 & 12 & 17 & 22 & 27 & 32 & 37 ...
4
votes
1answer
60 views

Let's denote $|A|=n, |B|=r$. Calculate the following sum: $\sum_{f:A \rightarrow B} |f(A)|$.

Let's denote $|A|=n, |B|=r$. Calculate the following sum: $$\sum_{f:A \rightarrow B} |f(A)|$$ As I understand, we must calculate cardinality of images of all different functions. I was able ...
1
vote
1answer
203 views

Number of ways of placing $n$ distinguishable balls in $k$ indistiguishable bins where the maximum size of a bin is $m$

I know that the number of ways of placing $n$ distinguishable balls in $k$ indistinguishable bins is given by the Stirling number of the second kind. But I don't know how to modify it to include the ...
2
votes
1answer
198 views

Coin Game, Probability and Fairness

The following game is being played : Player $\mathrm{B}$ pays to Player $\mathrm{A}$ an amount $\mathrm{X}$ and throws a coin at most $20$ times. If at the toss $k\space (k \leq 20)$ tail is thrown, ...
1
vote
3answers
353 views

Number of subsets with at most n elements of a set of 2n+1 elements (updated)

A set contains 2n+1 elements. What is the number of subsets of the set which contain at most n elements? Apart from the answer, please guide how to solve and go through this question? Please note: ...
1
vote
3answers
67 views

Exact number of events to get the expected outcoms

Suppose in a competition 11 matches are to be played, each having one of 3 distinct outcomes as possibilities. How many number of ways one can predict the outcomes of all 11 matches such that exactly ...
2
votes
1answer
105 views

Permutation & Combination

There is a game in which there is a point P and k other points on a plane. To win, we must draw directed lines starting from point P and ending at point P with exactly n number of lines to be drawn. P ...
5
votes
4answers
243 views

What is the difference between analytic combinatorics and the theory of combinatorial species?

Yesterday I asked the question Why should a combinatorialist know category theory?, where Chris Taylor suggested me to have a look at combinatorial species. I had heard the term before but I haven't ...
1
vote
0answers
21 views

simple formula to distribute inputs

I need a simple formula to do some math for my inputs to generate max number of fixed values .. Below i wrote a simple logic for the math lets say we have an object that will cost fixed numbers of 4 ...
0
votes
0answers
889 views

2d bin packing problem, with opportunity to optimize the size of the bin

I have been tasked with optimizing a manufacturing process. It is a non-trivial, NP hard problem. The problem is similar to the 2d bin packing problem, but we are trying to optimize the size of the ...
0
votes
1answer
82 views

k-uniform, k-regular set family. Prove there is a coloring that leave no member monochromatic.

Let F be a set family. F is k-uniform: each member of F has k points. F is also k-regular: every point occurs in exactly k members of F. Show that for k $\geq$ 10 there is a way to color all the ...
6
votes
0answers
448 views

Probability, choose a box and then take exactly two white balls

There are $5$ boxes. There are $5$ white and $3$ black balls in two boxes, and $4$ white and $6$ black balls in the other three boxes. One box is randomly chosen. $3$ balls are randomly taken from ...
1
vote
1answer
106 views

Tournament where any k players are beaten by another

In a tournament every player competes against each other. Every match has a winner. A tournament has property $P_k$ if for every set $S$ of $k$ players there exists a player $a\notin S$ who beats ...
1
vote
1answer
56 views

Probability, balls and 2 kinds of boxes

There are 5 boxes. In two of them there are 5 white and 3 black balls, in three of them there are 4 white and 6 black balls. We pick out randomly one box and choose 3 balls. What is the probability ...
1
vote
2answers
209 views

Probability of visiting state $s_1$ of a Markov chain more than $N$ times in $L$ steps.

Assume we have a two-state Markov chain, with $s_1$ and $s_0$ denoting the two states. The initial state of the Markov chain is either $s_1$ or $s_0$ with probability $p_1$ or $p_0$, respectively. The ...
2
votes
1answer
94 views

how to write the process of decomposition of a graph into shortest closed sub graphs

If I want to decompose a graph in to possible shortest closed cycles (as shown in right side). then how can i describe this process with mathematical notations. to understand please refer below ...
5
votes
2answers
424 views

Counting strictly increasing and non-decreasing functions

$f$ is non-decreasing if $x \leq y$ implies $f(x) \leq f(y)$ and increasing if $x < y$ implies $f(x) < f(y)$. How many $f: [a]\to [b]$ are nondecreasing? How many $f: [a] \to [b]$ are ...
1
vote
1answer
75 views

Paths on $\mathbb{Z}^d$

Let's say a path must be non-self-intersecting, and that we have the usual lattice structure. Then if $\sigma(n)$ is the number of paths of length $n$ then why do we have convergence of the sequence ...
1
vote
0answers
35 views

signature of young diagram

In paper of k.c. Misra and T.Miwa on crystal base for basic representation of $U_{q}({{sl_n}}(n))$ they have used signature of a young diagram. Question:what is the meaning of signature of a Young ...
2
votes
2answers
243 views

Exponential generating function for permutations with descent set whose least element is even

Let $E(n)$ be the number of permutations $w\in S_n$ such that the least element of the set $Des(w)\cup \{n\}$ is even, where $Des(w)$ is the descent set of $w$. I need to find the exponential ...
16
votes
1answer
613 views

Why should a combinatorialist know category theory?

I know almost nothing about category theory (I have just skimmed the first chapters of Aluffi's algebra book), reading this question got me thinking... why should someone mostly interested in ...
1
vote
2answers
839 views

The basic of the count

(a) A computer network consists of six computers. Each computer is directly connected to at least one of the other computers. Show that there are at least two computers in the network that are ...
0
votes
2answers
143 views

Choosing countries for a council

How many ways are there to select $12$ countries in the United Nations to serve on a council if $3$ are selected from a block of $45, 4$ are selected from a block of $57$, and the others are selected ...
2
votes
3answers
49 views

Computing $\langle (13746) \rangle$ in $S_7$.

How to list the elements of subgroup $\langle a \rangle$ in $S^7$ where $$a=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 2 & 7 & 6 & 5 & 1 &4 ...
1
vote
3answers
516 views

Negative Binomial Coefficients

Is it true that Pascal's Rule holds for binomial coefficients with a negative upper index? With $n = -1$ and $k = 3$, for example, it appears not to hold.