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
1answer
219 views

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

Question: How many 9 letter strings are there that contain at least 3 distinct vowels? I am studying and I was wondering if this answer could be an alternative answer to the question above: ...
0
votes
0answers
541 views

Probability of Obtaining A Particular Sum from Successive Dice Rolls

Suppose you have a regular die with 6 faces numbered 1 through 6, respectively, and roll the die 4 times. What is the probability that the sum of the 4 rolls is 14? This problem is equivalent to ...
1
vote
1answer
49 views

8 friends, 7 nights, invite 4 every night, all of the friends must be invited, how many options?

Assume I have 8 friends, I want to invite 4 friends each night for 7 night so everyone will be invited at least once. How many combinations are there to do it? I think I'm supposed to use the ...
0
votes
1answer
167 views

How many ways are there to sit $n$ couples on a bench when every couple sits together?

How many ways are there to sit $n$ couples on a bench with $2n$ sits, when every couple sits together? How many ways are there to sit the couples so that none of the couples will sit together?
3
votes
1answer
84 views

Evaluating Sums Combinatorially

Consider the following finite sums: (1) $\sum k(k!)$ for k from 1 to n (2) $\sum (k-1)(n-k)$ from 1 to n I am trying to determine how to evaluate these sums combinatorially. It seems the first is ...
-1
votes
1answer
58 views

What is the algorithm to permute a set of elements in to a fixed length? [closed]

for example {abc, d, e, f, xy} and fixed length 5 the output should be abced, abcef, abcdf, abcxy, xydef further is for multiple length 5 and 6 append the output list is abcedf, abcxyd, abcxye, ...
5
votes
1answer
372 views

Combinatorial puzzle

Let $\pi$ be a set of ordered pairs of natural numbers, $\pi = \lbrace (n_1,n_2) \dots (n_k ,n_{k+1})\rbrace$ (a "set of pairs"). Let $\cup \pi$ be the set $\lbrace n_1 n_2 \dots n_k ...
2
votes
2answers
136 views

Tricks to Solve Arbitrary Recursions

Consider two recursions: (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$ (2) $na_n = (n-2)a_{n-1} + n/2$ with $a_0 = 0$ When I look at the first recursion it suggests to me that I ...
1
vote
2answers
102 views

to get a MDS code from a hyperoval in a projective plane

explain how we can get a MDS code of length q+2 and dimension q-1 from a hyperoval in a projective plane PG2(q) with q a power of 2? HINT:a hyperoval Q is a set of q+2 points such that no three ...
37
votes
3answers
1k views

Solutions to $\binom{n}{5} = 2 \binom{m}{5}$

In Finite Mathematics by Lial et al. (10th ed.), problem 8.3.34 says: On National Public Radio, the Weekend Edition program posed the following probability problem: Given a certain number of ...
1
vote
2answers
77 views

A doubt in the derivation of a generating function

My question is related to a previous question asked here. It is really a very uninteresting sort of a doubt unfortunately. Let $S_n$ be the number of all possible final results at a competition where ...
0
votes
1answer
71 views

bijective mapping homework question

I have to answer a question which i don't really understand. The question is: Find an appropriate bijective mapping between a set of sequences and the set in question: 1. In how many ways can $k$ ...
0
votes
0answers
93 views

Inclusion-Exclusion Principle

I'm having a bit of trouble with this, and can't get my numbers to come out correctly. Here's an example: Get a maximum of n items, composed of the following: x burgers y hot dogs z fruit w napkins ...
2
votes
2answers
52 views

New to generating functions - how do I get the function from the sequence defined by $a_n= n$ for $n\geqslant 0$?

I'm given: $a_n= n$ for $n \geqslant 0$. I'm quite good at recursive generating functions, but I haven't came across a simpler one like this, so I'm sure I'm just overlooking something really basic.
4
votes
1answer
261 views

Partial sum of numbers

My TA gave today this question as a nice question to think about. He said its involves standard ideas of Probability theory and numbers. But, I don't even know how to start. Let $x_1, \ldots, x_n$ ...
3
votes
1answer
99 views

An identity related to Legendre polynomials

Let $m$ be a positive integer. I believe the the following identity $$1+\sum_{k=1}^m (-1)^k\frac{P(k,m)}{(2k)!}=(-1)^m\frac{2^{2m}(m!)^2}{(2m)!}$$ where $P(k,m)=\prod_{i=0}^{k-1} (2m-2i)(2m+2i+1)$, ...
5
votes
3answers
220 views

Calculate $\sum\limits_{k=801}^{849}{ \binom {2400} {k}} $

Is any formula which can help me to calculate directly the following sum : $$\sum_{k=801}^{849} \binom {2400} {k} \text{ ? } $$ Or can you help me for an approximation? Thanks :)
0
votes
1answer
88 views

Weak Compositions with Size Restrictions

I have a number of elements and I'm trying to place them into boxes but one of the boxes has a restriction on the number of elements that can be placed into it, how do you account for that in the weak ...
7
votes
2answers
625 views

Lines in the plane and recurrence relation

I am trying to solve the following problem from Cohen's Basic Techniques of Combinatorial Theory: A collection of $n$ lines in the plane are are said to be in general position if no two are ...
1
vote
1answer
46 views

Number of different combinations while ordering pizza.

Say i wanna order a pizza, I order exactly 3 different types of additions on the pizza, From 10 different options (Black olives, Green Olives, Pepperoni, Cheese, Tuna, Chocolate, Bananas, Mushrooms, ...
0
votes
1answer
73 views

How many tiles can be made by us $2 * 5$

How many tiles can be made by us $2 * 5$
6
votes
1answer
181 views

What is the correspondence between combinatorial problems and the location of the zeroes of polynomials called?

In the wikipedia article on the Italian-born American mathematician and philosopher Gian-Carlo Rota, it is stated that the one combinatorial idea he would like to be remembered for "... is the ...
4
votes
2answers
929 views

Prove by Combinatorial Argument that $\binom{n}{k}= \frac{n}{k} \binom{n-1}{k-1}$

This is a question from my first proofs homework and I am confused about the combinatorial argument aspect. I already did the algebraic proof. I think I am supposed to put into words what both sides ...
0
votes
3answers
33 views

How do I solve this combination with variables included?

I am working with a combination and have the problem $_{v}C_{v-2} = \binom{v}{v-2} $ I know the combination formula but can't figure out how to simplify my answer to get the correct answer. How do i ...
3
votes
2answers
4k views

Number of triangles in a regular polygon

A regular polygon with $n$ sides. Where $(n > 5)$. The number of triangles whose vertices are joining non-adjacent vertices of the polygon is?
0
votes
1answer
665 views

How many seven letter sequences with no repeated letters contain all five vowels

I can't seem to get the right answer with this. How many seven letter sequences of English letters, with no repeated letters, contain all five vowels? So far I am doing $\dbinom{21}{2} \cdot ...
0
votes
2answers
661 views
1
vote
1answer
370 views

Triangle tiling proof

How to prove that the number of triangles in the tiling below can be found by the formula $$\left\lfloor\frac{n(n+2)(2n+1)}8\right\rfloor\;,$$ where $n$ is the number of vertical layers? (For the ...
2
votes
2answers
125 views

Conditional Expectations

Suppose we roll fair die until we obtain a score of $6$. Let $Y$ denote the number of rolls and let $X$ denote the number of rolls on which we get a score of $1$. I have to find $\mathbb{E}[X]$ and ...
0
votes
1answer
60 views

How i could find this three-digits

How I find this : Find the least three-digits number that is equal to : the sum of its digits plus twice the product of its digit? In how many ways i can write 12 as an ordered sum of integers ...
0
votes
1answer
119 views

41 different balls are drawn from a bag

41 different balls are drawn from a bag containing balls labelled 1,2,…,300. The probability that the number of balls drawn that are labelled with an odd number is larger than the number of balls ...
-1
votes
1answer
122 views

Prove that the edges of a connected undirected graph G…

Prove that the edges of a connected undirected graph G can be directed to create a strongly connected graph if and only if there is no bridge in G.
3
votes
1answer
466 views

graph theory: upper bound on edge number, given number of vertices and

thanks for letting me become a member. I have a rather basic question on graph theory. Suppose G is a finite graph, without loops, multiple edges or directed edges. Let n be the number of vertices, ...
1
vote
1answer
127 views

In A Cross Product Of Pairs, Find Elements Where Both Pairs Contain The Same Number

We have a set S1 consisting of pairs of numbers between 1 and 30, eg: { {1,3}, {2,5}, {1,8}, ...} This set may be all (30 choose 2) of the possibilities, or any ...
2
votes
1answer
45 views

Counting binary sequences with $S$ $0$'s and $T$ $1$'s where every pre-sequence contains fewer $1$'s than $0$'s

How many $S+T$-digit binary sequences with exactly $S$ $0$'s and $T$ $1$'s exist where in every pre-sequence the number of $1$'s is less than the number of $0$'s? Examples: the sequence $011100$, ...
0
votes
2answers
374 views

Selecting objects arranged in a circle - Solution Only By Counting

I'm trying to understand the following solution (based on http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.8324). Problem: What is the number of ways of selecting $k$ objects from $n$, ...
1
vote
2answers
102 views

Number of partitions of a set into even classes

Suppose I have a set containing $n$ elements and I consider the number of partitions of it in which all the constituent classes are even. I let $R_n$ denote this number ($R_0=1$) and proceed as ...
4
votes
4answers
111 views

Different ways of computing $\sum_{n=0}^{\infty}\binom{n+7}{n}\left(\frac{1}{3}\right)^{n}$

Calculate $\sum_{n=0}^{\infty}\binom{n+7}{n}\left(\frac{1}{3}\right)^{n}$ in various ways.$$$$ one more question: how about $\sum_{n=0}^{\infty}n\binom{n+7}{n}\left(\frac{1}{3}\right)^{n}$ ?
5
votes
2answers
100 views

Combinatorial problem: constructing certain subsets of a set of size eight.

I'd like to find eight subsets $S_1$, $S_2$,$\ldots$,$S_8$ of $\{1,2,3,\ldots,8\}$ with the following properties: 1) Each $S_i$ has size 3, and each $i$, $1\leq i\leq 8$, is in precisely three of the ...
3
votes
3answers
2k views

Counting 1:1 and onto functions

I'm faced with the following questions: 1) How many functions are there from a set of size 3 to a set of size 5? How many of them are 1-to-1? 2) How many functions are there from a set of ...
1
vote
0answers
191 views

Number of ways of distributing $k$ balls of different colors into $n$ bins with a certain requirements

I have a question that makes me very confused even if I consider both "block" technique and "twelvefold way" Suppose I have balls of $k$ different colours, $a(j)$ of each colour for $j \le k$. In ...
5
votes
1answer
203 views

A Question on the Young Lattice and Young Tableaux

Let: $\lambda \vdash n$ be a partition of $n$ $f^\lambda$ - number of standard Young Tableaux of shape $\lambda$ $\succ$ - be the covering in the Young Lattice (that is, $\mu \succ \lambda$ iff ...
0
votes
2answers
2k views

Probability in Keno

I've been trying to figure this out for a while now. In keno, 20 different numbers between 1 and 80 are chosen. I then choose 5 numbers between 1 and 80. What is the chance that those 20 numbers ...
73
votes
2answers
5k views

More than 99% of groups of order less than 2000 are of order 1024?

In Algebra: Chapter 0, the author made a remark (footnote on page 82), saying that more than 99% of groups of order less than 2000 are of order 1024. Is this for real? How can one deduce this result? ...
1
vote
1answer
124 views

Prove that the Iwata function is Submodular

The Submodularity property for $f: 2^V \rightarrow \mathbb{R}$ is defined as: $f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y)$ where $X, Y \subseteq V$ While the Iwata function is defined as: ...
4
votes
1answer
129 views

Classrooms and students puzzle

My school has many classes. Any two students share exactly one class. Any two classes share exactly one student. A class must have at minimum $3$ students, and there is at least one class with $17$ ...
1
vote
3answers
501 views

Inclusion and Exclusion Secret Santa

If I am having a "secret santa" gift exchange with 5 people, how many possibilities for gift exchanges are there if nobody ends up with the same gift? The answer could be $5!$ , but I don't think it ...
1
vote
2answers
54 views

Counting ordered triples of sets, with empty intersection.

I was recently asked this question which I couldn't solve. Give the number of ordered triples $(A_1, A_2, A_3)$ of sets which have the property that $A_1 \cup A_2 \cup A_3 = ...
0
votes
2answers
93 views

How to combine the fraction over the common denominator?

How to combine the fractions on the righthand side over the common denominator: $\frac{(n+1)!n!}{k!(k-1)!(n-k+1)!}=\frac{(n+k)n!(n-1)!}{k!(k-1)!(n-k)!}+\frac{n!(n-1)!}{(k-1)!(k-2)!(n-k+1)!}$
-1
votes
2answers
269 views

Distribution problems

In how many ways can you distribute six identical black notepads, seven identical red pencils and eight identical green markers to three students, so that each student gets at least one item of each ...