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)

-4
votes
0answers
24 views

help for my test [on hold]

a drawer contains 5 black socks, 6 gray socks, and 4 blue socks. without looking, you draw out a sock and then without returning it you draw another sock. what is the probability that the 2 socks you ...
3
votes
1answer
17 views

Set of positive integers with unique sums

What I'm looking for is the name of a type of number set. Given a number T (for total) and a set of positive integers S, I want to uniquely identify the subset of S that sums to T. All sets containing ...
1
vote
0answers
8 views

Start to Proof of bernoulli polynomials and sums

I need help starting this proof: For all integers k,l,m>=0 and not all equal to 0, (3.7) It says that that comparing the above equation (3.7) with the one discussed earlier in the paper(3.6) (shown ...
0
votes
1answer
32 views

Solutions of the Pell Equation $x^2-2y^2=-1$

I am assigned to find solutions to the Pell-type equation. $x^2-2y^2=-1$ So far, I only have $(7,5), (41,29)$ and $(239,169)$. My question is, is there a general formula to find all its solution? ...
3
votes
2answers
61 views

How to populate a $0-$line with $1$'s?

I have a line of $n$ $0$'s like this: Zeroth index -->$000...000$ I want to populate the line with $m$ $1$'s with the following rules: (1) They have to occur after the index ...
-3
votes
0answers
12 views

Generating function, coloring balls [on hold]

In how many ways can $n$ balls arrange in $k$ blocks and then the balls in each block paint with one of the two colors, balls in the same block paint with same color. Need to solve this using ...
0
votes
0answers
19 views

Conditioned Probability about drawing cards.

Let's have a stack of 52 cards, from which we'll take 26 cards (order doesn't matter) We can win bet $H$ if any (it could be also, more than one) of several card combinations is present on the cards ...
1
vote
0answers
13 views

Book recommendation on integer programming ? (in order to solve a set cover problem)

I'm trying to solve a set cover problem. To put it shortly, my problem is about covering a $N \times M$ grid, by using various rectangles which have associated cost depending on their shape and ...
2
votes
3answers
33 views

Probability of choosing subsets $A$, $B$ such that $A\cap \!\,B=\varnothing \!\,$ and $A\cup \!\,B=X$

I'm given a set $X={\{\ \!\,1,2,3,...,n\!\ \}} $, and I have to calculate the probability that, for two randomly chosen, different, non-empty sets $A, B$: $A,B\subseteq \!\,X$, we have $A\cap ...
0
votes
0answers
25 views

Possible areas within an integer grid

Given a 1x1 grid with 4 lattice points $[(0,0),(0,1),(1,0),(1,1)]$ (equivalent to a $2 \times 2$ grid of vertices), there are 2 shapes and areas that can be formed: a triangle and a square. There are ...
0
votes
1answer
13 views

Combining an outcome of a score

Hey I was wondering how many are the possibilities of combining the scored points of a result such $133:75$ from a basketball game? Considering that there are fouls($1$ point), normal($2$ points) and ...
0
votes
0answers
21 views

1 and multiplication form a group - Meaning?

I heard someone say this with respect to combinatorial mathematics, but I have no idea what they mean? Any ideas?
0
votes
2answers
53 views

A problem on pigeonhole principle

Following is a problem, which makes use of the pigeonhole principle. But How? "Let $A$ be a set of $n$ integers. Prove that $A$ contains a subset such that the sum of its elements is divisible by ...
0
votes
0answers
14 views

Number of permutations in a multiset

How many permutations of the multiset {$1^{a_{1}},2^{a_{2}},...,n^{a_{n}}$} have no $1$s placed consecutively? What inequality has to hold in order for there to be such permutations? What I have: ...
2
votes
1answer
24 views

Partitioning of Teams

In how many ways can we partition $2n$ people into $n$ teams with different names of two people each and assign to each team who plays position $A$ and who plays position $B$? (For instance, the ...
0
votes
1answer
32 views

Counting problem for seating in a circle

I am having a hard time understanding the answer to the following problem from Grimaldi: "At Professor Alfred's science camp, 17 students have lunch together each day at a circular table. They are ...
2
votes
2answers
59 views

find coefficient of $x^{50}$

Let $f(x)=\frac{1}{(1+x)(1+x^2)(1+x^4)}$then find the coefficient of term $x^{50}$ in $(f(x))^3$.I think that we can set $$(f(x))^3=\frac{a}{(1+x)^3}+\frac{b}{(1+x^2)^3}+\frac{c}{(1+x^4)^3}$$ and find ...
1
vote
1answer
32 views

How to complete this proof of the Orbit-Stabilizer Theorem?

Let $G$ be a group, $X$ a set, and $*$ and action of $G$ on $X.$ Let $x \in X$ and denote by $\operatorname{Orb} \left( x \right)$ the orbit of $x$ and by $\operatorname{Stab} \left( x \right)$ the ...
0
votes
2answers
18 views

How to find the number of words of length n with a specific rule.

I'm given the following problem: Consider a language that uses only {1, 2, 3}. The only rule this language has is that a '3' cannot follow a '3'. How many words of length n exist in this language? ...
4
votes
2answers
117 views

Number of rearrangements of the word “INDIVISIBILITY”

In how many ways can the word "INDIVISIBILITY" be rearranged, such that no two Is come close to each other? My attempt Total number of ways of rearranging the word = $\dfrac{14!}{6!}$ Number of ...
1
vote
1answer
32 views

Expected value problem with urns and balls

A total of $n$ balls, numbered $1,\ldots,n$, are put into $n$ urns, also numbered $1,\ldots,n$, in such a way that the $i$th ball is equally likely to go into any of the urns $1,\ldots,i$. What is ...
4
votes
1answer
36 views

I draw a hand of 13 from a deck of 52 cards. What is the probability that I do not have a card from every suit?

I draw a hand of 13 from a deck of 52 standard playing cards. What is the probability that I do not have a card from every suit? I count the number of ways I can draw 13 from 3 suits ...
2
votes
1answer
53 views

$\displaystyle\prod_{ p\leq x}p\leq 4^{x-1}$ for all real $x\geq2$

How yo prove this? I'm looking the Erdös proof from Bertrand Postulate and there are many things I don't get. Please don't hints, I'm newbie in combinatorics techniques. In the book I don't get how ...
3
votes
2answers
83 views

In how many ways can I sum integers from $1$ to $N-1$ to obtain $N$?

I'm looking for the exact formula for $f(N) =$ number of ways to sum $1, 2, ..., N-1$ to obtain $N$. $N$ is an integer $> 0$. Integers $1, 2, ..., N-1$ can be used $0$ or 1 time as an element in ...
1
vote
0answers
29 views

dimension of the span of all partial derivatives of a given polynomial $f$ and the polynomial $E(f)$

I need some help on the problem below. Let $d\geq 4$ and $f$ a symmetric polynomial, homogeneous of degree $d$, in $n$ variables $x_1,\dots,x_n$, with real coefficients. We set $$ ...
3
votes
1answer
34 views

Proving or disproving there is a sum of these digits to 100

I am shown that the sum $41+20+3+5+6+7+8+9=99$ and the sum uses each digit precisely once. I am asked to prove or disprove the possibility of a sum using each digit precisely once which results in ...
2
votes
2answers
44 views

Number of strings [on hold]

There are $2^{10} =1024$ possible $10$ -letters strings in which each letter is either an $A$ or a $B$. Find the number of such strings that do not have more than $3$ adjacent letters that are ...
1
vote
1answer
20 views

Generating Series and Recurrence Relation

We have the following recurrence relation: $b_n=6b_{n-1}-9b_{n-2}$ and initial conditions $b_0=1, b_1=6$ I use the generating series method to solve as following: Let ...
1
vote
1answer
33 views

A question on the Lagrange Inversion Formula

I have to use the L.I.F. for \begin{align*} s\left(x,y\right)=\frac{1}{2}\left(1-x-y-\sqrt{1-2x-2y-2xy+x^2+y^2}\right) \end{align*} to obtain that \begin{align*} s\left(x,y\right) = ...
4
votes
2answers
41 views

Number of ways in which a batsman can score 14 runs in 6 balls not scoring more than 4 runs in any ball.

Hello everybody my query is regarding the number of positive integral solution. In the sport of cricket, find the number of ways in which a batsman can score $14$ runs in $6$ balls not scoring ...
0
votes
0answers
30 views

How to find the no. Of non negative integral solutions of a equation

I want to find the no. Of non negative solutions of $X+2y+3z=n$ I know how to find the non negative integral solutions of the equations of type $X+y+z=n$ using dividers method that is assume that ...
1
vote
1answer
21 views

Find number of circular arrangements possible

If 20 persons were invited for a party, in how many ways will two particular persons be seated on either side of the host in a circular arrangement? According to me the answer should be $17!.2!$. But ...
0
votes
2answers
13 views

partial DAG and number of linear orders

Let $>$ be a linear order relation over a set $A$. Consider the graph $G$ that represent the transitive closure of $>$. Obviously $G$ is directed and acyclic. Given a set of edges ...
1
vote
1answer
26 views

Approximation of combination $ {n \choose k} = \Theta \left( n^k \right) $?

Is it a valid to say $$ {n \choose k} = \Theta \left( n^k \right) $$ for any $n$ and $k$? If so, how to prove it? Note: $k$ is not a function of $n$. Note: Observed it here (page 5): ...
-3
votes
0answers
26 views

Bivariate Discrete question [on hold]

Suppose we select with replacement n marbles from an urn containing 40 red marbles, 25 yellow marbles and 35 blue marbles. Let Y1 = the number of red marbles selected, Y2 = be the number of yellow ...
0
votes
1answer
14 views

How many different sets of 8 elements can I pick if I am picking from a bag of 1681 elements probability and counting [on hold]

I have 1681 points and trying to see how many different constellation of 8 points I can have to see if it is feasible to try out all possibilities to find the best. It's actually a Communication ...
2
votes
0answers
92 views
+100

Challenging recurrence relation problem

I am starting out with the following: $$ \frac{d^n}{dx^n}[g(x)^{f(x)}] = \sum_{c=0}^n g(x)^{f(x)-c}\lambda_{n,c}(x) $$ Therefore: $$ \frac{d^{n+1}}{dx^{n+1}}[g(x)^{f(x)}] = ...
2
votes
1answer
34 views

Expected number of trails to get $n$ heads in a row with an increasing biased coin.

Assume that we have a biased coin with probability $p_1$ of getting H and $1−p_1$ of getting T on the first trial, $p_2$ of getting H and $1−p_2$ of getting T on the second trial and so on such that ...
1
vote
1answer
22 views

How many $(r+1)$- subsets of $[n+1]$ have $(k+1)$ as their largest element?

Let $[n+1]$ be the set defined by $[n+1]=\{1,2,\ldots,n+1\}$. Call a subset of $[n+1]$ with $r+1$ distinct elements an $(r+1)$-subset. How many $(r+1)$-subsets of $[n+1]$ have $(k+1)$ as their ...
2
votes
0answers
22 views

Equation with $q$-binomial coefficients [migrated]

Let $d\ge2$, and let $q$ be a power of a prime. As usual, define $N(d,q)=\sum_{k=0}^d{d\choose k}_q$. I wonder if there are $d$ and $q$ as above such that $1+N(d,q)=q^{d+1}$. (If the answer is ...
2
votes
3answers
64 views

Combinatorics proof $\binom{2n}{2}=2\binom{n}{2}+n^2$

The problem is prove that $$\binom{2n}{2}=2\binom{n}{2}+n^2$$ by showing that each side counts the same collection of subsets. I am trying to study for a final exam and this is a question from a ...
3
votes
1answer
45 views

A fair die is rolled nine times. What is the probability that 1 appears three times, 2 and 3 each appear twice, 4 and 5 once and 6 not at all?

A fair die is rolled nine times. What is the probability that 1 appears three times, 2 and 3 each appear twice, 4 and 5 once and 6 not at all? My approach is fairly simple. The dice is fair, so we ...
0
votes
1answer
32 views

how many bit strings of length n are palindromes

While reading in a Discrete maths text book, there was this question : how many bit strings of length n are palindromes The answer is : $2^\frac{n+1}{2}$ for odd and $2^\frac{n}{2}$ for even ...
0
votes
0answers
15 views

scalar multiple of Young symmetriser

The following is a lemma on Fulton and Harris' book -Representation theory,a first course (page 53): Lemma: For all $x\in \mathbb{C}\mathfrak{S}_r$, $c_{\lambda}\cdot x\cdot c_{\lambda}= scalar ...
3
votes
1answer
40 views

Some unique representation of nonnegative integers

Let $\mathbb N$ be the set of nonnegative integers, that is $\mathbb N=\{0,1,2,3,\ldots\}$. Does there exist a subset $K\subset\mathbb N$ such that every $n\in\mathbb N$ has a unique ...
2
votes
1answer
30 views

Number of functions $f:\{1, 2, \ldots, n\} \to \{0, 1\}$ that assign $1$ to exactly one positive integer less than $n$

**I've seen this question is discrete maths text : How many functions are there from the set $\{1, 2, . . . , n\},$ where $n$ is a positive integer, to the set $\{0, 1\}.$ a) that assign to ...
0
votes
0answers
7 views

How many functions are there from the sets that assign 1 to exactly one of the positive integers less than n [duplicate]

I've seen this question is discrete maths text : How many functions are there from the set {1, 2, . . . , n}, where n is a positive integer, to the set {0, 1} a) that assign 1 to exactly ...
0
votes
1answer
27 views

Generating function for the number of ways to part an integer $n$ such that no summand will repeat more than 3 times

What is the generating function for the number of ways to part an integer $n$ such that no summand will repeat more than 3 times? For example: $n=6$ so we can part it like this: $1+1+1+3$ but ...
2
votes
1answer
29 views

Ways to place 3 red, 4 blue and 5 green wagons such that no 2 blue wagons were standing next to each other

As the title says I need to find the number of ways to to place 3 red, 4 blue and 5 green wagons such that no 2 blue wagons were standing next to each other. The wagons of the same color are ...
4
votes
1answer
24 views

Choosing n objects from k types of objects, each of which is in limited supply

Suppose I wanted to light my Christmas tree. In my basement, I find a cord that has $5$ sockets in which I can screw bulbs. I also locate $5$ red bulbs, $4$ green bulbs, and $3$ blue bulbs. How many ...