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
0answers
2 views

Is this permutations or combinations?

I am a bit confused. When we use the multiplicative principle are we finding the number of permutations or combinations. An example of using this principle is where I have 5 shirts 3 pairs of pants ...
0
votes
0answers
7 views

Combination formula?

I know there is a formula for finding the different combinations when you are dividing them in groups: C = n!/(n-r)! r! However, what if you just want to find the number of combinations for lets ...
0
votes
0answers
10 views

Other than the icosahedron in which each vertex has degree 5, is there any triangulation of the sphere that meets the following three conditions?

Every vertex has degree > 3. There is no separating triangle (a triangle with vertices of the graph both inside and outside the triangle). Every vertex-coloring using exactly four colors consists of ...
-3
votes
0answers
43 views

some amazing properties of combinatorial numbers [on hold]

I want to prove $$ C_{2^{i+1}-k-1}^k=\frac{(2^{i+1}-k-1)(2^{i+1}-k-2)\cdots(2^{i+1}-k-(k-1))(2^{i+1}-2k)}{k(k-1)\cdots 2\cdot 1} $$ is even, for all $k=1,2,3,\cdots, 2^i-1$. Here $i\geq 1$. How to ...
-2
votes
2answers
18 views

How many ways are there to arrange three of the letters chosen from the set ABCDE?

Please show your work. I've been looking at this problem for over an hour now and havn't been able to solve it. Thank you!
0
votes
1answer
32 views

Number of paths in a graph with infinite nodes

Does a graph with infinite nodes that is not fully connected have a countably infinite or a uncountably infinite number of paths originating from a single node? We are only concerned with paths that ...
0
votes
2answers
19 views

Prove that if $k\mid n$ then $p(A_k)={1\over k}$

Let $n$ be a natural number, $n=p_1^{a_1}\cdot...\cdotp_m^{a_m}$. Let us randomly choose a number between 1 and $n$ with a uniform, equal chance. Let us denote the event "The number chosen is ...
-5
votes
1answer
34 views

Need help in solving [on hold]

A group of $60$ children attend an after school club. Of these, $35$ children play football and $29$ play hockey. Three children do not play either football or hockey. Find the number of children ...
0
votes
1answer
23 views

Generating function of derangements

I am pretty new to the topic of generating functions and I would appreciate if someone could help me out with this problem I have. In the lecture we have proven the following generating function for ...
1
vote
1answer
43 views

What is the probability that you get $i$ on the $i^{th}$ trial?

What is the probability that you get $i$ on the $i^{th}$ trial? Match = Get result $i$ on $i^{th}$ trial. What is the probability of $M = 0,1,2,...,6$ matches when: Note: I'm not asking you to do ...
5
votes
3answers
97 views

Find the coefficient of $x^{30}$.

Find the coefficient of $x^{30}$ in the given polynomial $$ \left(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}+x^{12}\right)^5 $$ I don't know how to solve problems with such high degree.
1
vote
2answers
37 views

Combinatorics Recurrence relation

Let $h_n$ be a number sequence where $h_n = 3h_{n-1} - 2h_{n-2}$ with $h_0 = 0$ and $h_1 = 1$. Compute the ordinary generating function of $h_n$ and then using the generating function compute a ...
2
votes
2answers
17 views

Probability of Two Suits within Three cards, within 4 cards

I am trying to calculate what is the probability of the 3 random cards of 52-pack containing at least two of the same suit. I am also trying to do the same for the four card variant (so, the ...
0
votes
4answers
46 views

Combinatorial Proof of an Instance of the Binomial Theorem

Give a combinatorial proof of the following instance of the binomial theorem. For any positive integer $k$, $(k + 1)^{n}$ = $\sum\limits_{i=0}^{n}$ ${n}\choose{i}$$k^{i}$. I have looked at this for ...
-1
votes
0answers
25 views

Combinatorics: Password consisting of 13 characters. Must contain at least one odd digit, and at most two even digits. How many passwords?

I'm really trying here. I just need help where to go next. Each character is one of the 10 digits 0, 1, 2, ... , 9 What I have so far is that there are 10^13 possible passwords. I'd have to subtract ...
0
votes
0answers
27 views

Proving Crapo's Lemma

Let $L$ be a finite lattice with least and greatest elements $0, 1$, respectively, and let $X\subseteq L$. Let $n_k$ be the number of $k$-element subsets of $X$ with join $1$ and meet $0$. I want to ...
0
votes
0answers
13 views

Combinatorics Question for generating fuctions [on hold]

Any tips/helps would be greatly appreciated! Let h_n be a number sequence where h_n = 3h_(n-1) - 2h_(n-2) with h_0 = 0 and h_1 = 1. Compute the ordinary generating function of h_n, and then compute a ...
0
votes
1answer
17 views

All subsets of nonnegative integers such that $a+2b = n$ has one solution for every positive integer n

My friend tackled this problem awhile ago and gave it to me recently. To reiterate, I am trying to find all subsets $S$ of the nonnegative integers such that the equation $a+2b = n$, where $a$ and $b$ ...
-4
votes
1answer
29 views

Combinatorics Generating Functions [on hold]

Any tips/comments would be greatly appreciated! Compute the generating function of the number sequence $h_n = (-2)^n n^2$ where $n\geq 0$.
0
votes
0answers
6 views

Finding a permutation class that has a growth rate greater than 1 and less than 0?

In a permutation class, there is an upper growth rate such that $gr(C)=\limsup_{n\rightarrow \infty}=\sqrt[n]{|C_n|}$ and a lower growth rate such that $\liminf_{n\rightarrow \infty}=\sqrt[n]{|C_n|}$. ...
1
vote
0answers
28 views

Binomial Coefficients and Function Composition

I found a paper that stated the following without proof. I tried to prove it on my own, but so far to no avail. Define $\varphi^{+}: \mathbb{N}^2 \to \mathbb{N}$ by $\varphi^{+}(i,j) = i + j$. ...
2
votes
1answer
46 views

Combinatorics Question VS CS solution!

I was wondering for some conceptual understanding to a question of this form: In how many ways may we choose three distinct integers from [1, 2, ..., 80] so that one of them is the average of the ...
0
votes
1answer
17 views

Sets of non-complements elements in a lattice.

Let $L$ be a finite lattice with a least element $0$ and a greatest element $1$, where $0\neq 1$. Fix a $t\in L$, and let $X$ be the set of non-complements of $t$, i.e., the set of all $x$ such that ...
2
votes
0answers
31 views

Coupon collector variation (with deleterious coupons and tolerance)

Imagine the standard coupon collector's problem, with n coupons to be collected. However, the sample space also contains T bad coupons. Specifically, if during the collection, I collect more than t (t ...
1
vote
3answers
54 views

Prove that $x^2 - 2013^2 \le y \le 2013^2 - x^2$ has an odd number of solutions

$x$ and $y$ are integers. $N$ is the number of solutions $(x, y)$ of this inequation $x^2 - 2013^2 \le y \le 2013^2 - x^2$. Prove that N is odd.
1
vote
2answers
54 views

How many sequences of length 6 are formed from the 26 letters without repetition where the first or last letter (possibly both) must not be vowels?

How many sequences of length 6 are formed from the 26 letters without repetition where the first or last letter (possibly both) must not be vowels? I am so lost and confused, but here's my approach: ...
0
votes
0answers
13 views

Mobius function on posets

Let $A= \lbrace 1^{a_1},2^{a_2},...,n^{a_n} \rbrace $ and $B=\lbrace 1^{b_1},2^{b_2},...,n^{b_n} \rbrace $ multisets for which : $A\leq _P B \Leftrightarrow $ for all $i=1,2,...,n $ is $a_i\leq b_i$. ...
1
vote
1answer
35 views

What is number of p-point subgraphs in n-point graph with average t connections?

I don't know graph theory, but I want to study this specific question for a while. I have no idea if this is a well known and studied question or not. I found it very difficult, and I don't know where ...
0
votes
3answers
39 views

Product Rule Notation Meaning

Let $S_1,...,S_t$ be finite sets and let $S=S_1 \times ... \times S_t$. The product rule states that $$|S|= _{i=1}^t S_i$$ There is supposed to be some big pi symbol in between the limits which i ...
2
votes
0answers
16 views

Optimality of lower bounds for Max-cut on specific graphs

The Max-Cut problem asks to find a subset $S$ of the vertices of a graph (with $m$ edges) such that the number of edges from $S$ to it's complement is as large as possible. The size $|M|$ of a max cut ...
1
vote
0answers
31 views

Permutation Of 2 Groups

The Following question is from "A FIRST COURSE IN PROBABILITY" of Sheldon Ross A class in probability theory consists of 6 men and 4 women. An examination is given, and the students are ...
1
vote
1answer
23 views

Difference : subsequences and substrings [on hold]

What are the differences between subsequences and substrings?
1
vote
2answers
246 views

Number of ways to distribute 55 red balls and 3 green balls

Fifty-five identical red balls and three identical green balls are to be distributed among seven children. Each child must get at least five balls. In how many ways can this be done? What I have so ...
0
votes
0answers
6 views

On the interval minor extremal function of a j × k matrice.

I was going through papers by Marcus/Tardos and Fox and I have this small doubt. If L is a j×k matrix which has every entry equal to 1, what is the interval minor extremal function of L? Can someone ...
1
vote
1answer
21 views

Find all possible two-way associations/relations between four numbers

Given four numbers {1,2,3,4}, how to find all possible two-way associations/relations between them? I calculate them manually as in below (50 in total) but I would like to know whether a mathematical ...
1
vote
1answer
61 views

Simplifying Sum

How would one show that $$ \sum_{i=0}^n\binom{n}{i}(-1)^i\frac{1}{m+i+1}=\frac{n!m!}{(n+m+1)!} ? $$ Any hint would be appreciated. Note: I tried to recognize some known formula, but since I don't ...
1
vote
2answers
41 views

Probability that every player is dealt a heart

We've got a standard, 52-card deck. We're playing Bridge with 4 players, so every player is dealt 13 cards. There are $\frac{52!}{13!13!13!13!}$ ways to deal the cards to the four players. (Intuition ...
2
votes
1answer
57 views

Number of orbits of $G$ acting on $X$

This question comes from Algebraic Combinatorics: Walks , Trees, Tableaux, and More by Richard P. Stanley. It is written as follows: "Let $X$ be a finite set, and let $G$ be a subgroup of the ...
1
vote
0answers
45 views
+50

Product of Stirling Numbers of the first kind

I have been messing around with coefficients of various polynomials and was wondering if there was a way to reduce the following stuff. Let polynomial, ...
0
votes
2answers
32 views

Finding probability of intersection of events

I was reading First course in Probability by Sheldon Ross and am stuck at the understanding this simple problem [hence proved my maths is poor :( ]. Problem: Celine is undecided as to whether to ...
1
vote
2answers
33 views

Probabily of profit after n attempts in a game of chance

Given a game of chance where the probabily of winning is $1/3$ that the cost of playing is $1$ point, and in case of winning the earning is $2$ points, I am trying to find a mathamtical expression (as ...
0
votes
0answers
34 views

Proj of some ring.

Let $R= \mathbb C[x_1,x_2,x_3,x_4,x_5,y_1,y_2,y_3,y_4,y_5]$ be the polynomial ring and let $S$ be the subalgebra generated by $x_1x_2x_3x_4x_5, x_1x_2x_3x_4y_5, \cdots ,y_1y_2y_3y_4y_5$ (the ...
0
votes
0answers
20 views

Space of ternary codes

(Newbie question). Hamming space is the collection of all $2^N$ binary strings of length $N$. Is there a distinct name for the space of ternary codes? How about distinct names for the space ...
0
votes
3answers
58 views

Birthday problem with 3 people

I have the following problem. It is a simple birthday probability problem with 3 people but I can't crack it Annie, Boris, and Charlie have random and independent birthdays. (We ignore leap years, so ...
0
votes
0answers
14 views

Sequence with every kth term expressible by a polynomial

Is there a term to describe a sequence $a_n$ s.t. every $k^{th}$ term is described by a polynomial expression in $n$? For example, $0,2,0,4,0,6,\dots$ satisfies this with $k=2$ and the polynomials ...
2
votes
2answers
43 views

How many disjoint subsets?

I have a question about combinatorics. I have the following set: $$M = \{ 1,2,...,n \}$$ How many disjoint subsets $$A\subseteq M, \quad |A| = 2$$ are there? For the future, how do I approach ...
0
votes
1answer
40 views

Number of permutations of $A=\{1,2,3,\dots,n\}$ such that $|x_i-x_j|\ne|i-j|$ of every $i,j\in A$

Let $B$ be the permutation of $A=\{1,2,3,\dots,n\}$ such that $|x_i-x_j|\ne|i-j|$ of every $i,j\in A$ where $x_k$ is $k-th$ element of $B$. How many different $B$ exist? On first sight it doesn't ...
-4
votes
0answers
19 views

Summation of a series with a A.P [on hold]

what will be the summation of this series n-r+1C2 + n-2*r+1C2 + n-3*r+1C2+..... 1C2; where n and r are natural numbers.Can we derive a formula from this
5
votes
1answer
64 views

How many ways to order vectors in $\{0,1\}^n$?

How many different rankings can be produced for the vectors in $\{0,1\}^n$ that also respect the usual $\geqq$ ordering of vectors (defined below)? I want to produce a complete ordering where, for ...
0
votes
0answers
17 views

Spaces of visual patterns, but not recurse/chaos.

I'm looking for information on existing/notable, spaces of visual patterns, that do not rely on, or appear to make much use of, recursion/chaos to function, as a cellular automata or fractal would. ...